fold and unfold

Haskell里面有两个著名的fold函数:foldr/foldl，这两个函数非常具有函数式编程的特点(递归)，几户所有的Haskell教程都会使用foldr/foldl来完成一些命令式语言的循环语句。还有个更少见的unfoldr函数,可以完成一些匪夷所思的操作。

1 fold

几乎所有的函数式语言都有类似的函数，如Javascript的对应是reduce[^1]reduceRight();Haskell的fold有两个版本，分别是foldr和foldl，两个函数主要区别在后缀上，一个从右折叠，一个从左折叠，位于Data.List,常见的教程里面定义的简单版本如下：

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr step zero (x:xs) = step x (foldr step zero xs)
foldr _ zero []        = zero

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl step zero (x:xs) = foldl step (step zero x) xs
foldl _ zero []        = zero

fold的参数依次为step函数、初始值、列表，返回值为一个和初始值类型一样的值。注意foldr和foldl的step函数都是二元函数，foldr的step参数顺序为列表元素、折叠变量,foldl的刚好反过来！这点很容易搞混淆。一般我们直接使用预定义的就行，当然对于Data.Tree等可折叠的类型，foldr/foldl也可以适用，方法类似。

众所周知，Haskell构造列表只能向头部插入元素：1:[2,3],连接链表也可以使用concat函数或者++：[1..5]++[6..10] & concat [[1..5],[6..10]],但是没有向尾部插入元素的函数(insert只能向已排序的插入值)，我们希望构造一个函数，调用方式为append list newElem，这个函数需要从尾部开始折叠，需要使用foldr:

1 2	append:: Foldable t => t a -> a -> [a] append xs x = foldr (\r e -> r:e) [x] xs

运行一下：

1 2	Prelude> append [1..3] 5 [1,2,3,5]

上述例子只是为了说明fold的应用方式，其运行效率不是很高，生产环境一般不会直接这样做(使用Array等代替)。基本上，使用foldr/foldl可以完成对列表元素的遍历+归一求值,下面的例子给出一个翻转字符串的函数,使用foldl实现：

reverse' = foldl (\r e-> e:r) []
main = do 
	print$reverse' [1..10]
	print$reverse' "welcome to hell!"

2 unfold

unfoldr^2是Haskell独有的函数，是foldr反向的操作，即从一个源构造一个列表，定义比foldr难一点:unfoldr :: (b -> Maybe (a, b)) -> b -> [a],接受一个迭代函数和一个初始值，产生一个列表，这个迭代函数的定义是b-> Maybe(a,b),可以预见此函数第一步从初始值生成一个Maybe Monad，内涵类型是(a,b)，即一个元组，fst为新的元素，snd为下次迭代使用变量(初始值类型)。使用例子如下：

1	unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10 =>[10,9..1]

当然这个例子用语法糖[10,9..1]更容易理解。我们下面举一个比较复杂也很实用的例子：将某些值如timestamp、字节数转换为可读性较高的字符串。timestamp是一个长整型，大部分人类更容易理解”x小时y分钟z秒”这种可读性更好的字符串，类似字节数，1234567890Byte可能会给人造成困惑，而”1G,153M,384KB,722Byte”更容易用来和硬盘容量做对比。可以看到上面的字符串是由一个列表和单位混合而成,如[x,y,z] [‘小时’,’分钟’,’秒’]；为了获取[x,y,z]我们需要一个函数，将大整数k按照某进制分解为一个列表：

$$K=\sum_{i=0}^n{U^i*x_i}$$

其中$K$为需要分解的数，$U$是进制（两个相邻单位进制一样没有，考虑特殊的如天数-小时-分钟这种），$x_i$为第$i$个单位下的数量。观察上述公式，很明显可以对$K$取$U$的余数来获取$x_0$，递归求值得到：
$$
\frac{K_i}{U}=K_{i+1} \cdots\cdots x_i，i = 0,..n\\
specially,K_0=K
$$
结合unfoldr的递归函数，先给出对应分解函数依次求出$x_0…x_n$：

digits :: Integral p => p -> p -> [p]
digits n = unfoldr f where
    f 0 = Nothing -- terminate
    f r = Just . swap $ r `divMod` n -- divMod will generate (temp-result and x_i),x_i will be inserted to result

其中参数$n$为进制，由于unfoldr向右方生成元素，$x_0$将被放置在第一个元素。下面我们写几个例子看看效果：

Predule> digits 10 123
[3,2，1]
Predule> digits 1024 2500
[452，2]

完成上述分解之后，需要将单位和值整合为字符串，需要传入一个值、单位进制和单位描述：

1
2
3

conv_units_humansize :: Int -> Int -> [String] -> String
conv_units_humansize x n units = intercalate "," $ map (\a->show (fst a) ++ (snd a)) k where
    k = reverse $ zip(digits n x) units

我们没有一开始将digits函数加上reverse，是为了方便zip自动适配两个列表长度，数量不够大单位时会自动截断右侧大单位。实际使用例子：

units_conv = do 
    print $ conv_units_humansize 61 60 ["Second","Minute","Hour"] -- "1Minute,1Second"
    print $ conv_units_humansize 1234567890 1024 ["Byte","K","M","G","T"]-- 1G,153M,384K,722Byte
    print $ conv_units_humansize 1717194 1000 ["g","Kg","t"] -- 1t,717Kg,194g

思考:利用fold如何进行反向转换?

3 More…

下面我们来尝试使用unfoldr来实现一个整数分解的函数，即将任意正整数分解为素数乘积的列表，如10分解为[2,5],因为任意整数都包含1因子，所以1不应进行分解，可设为终止条件.另外，素数只可分解为自身，即5->[5]。

$$
\forall x>1,x \in \mathbb{N}^+:x=\prod_{i=1}^n{p_i^{t_i}},p_i \in \phi;t_i,n\in \mathbb{N}^+
$$

首先，我们需要得到一个素数列表$\phi$来辅助计算.目前比较高效的方法是利用Haskell的惰性计算，通过Eratosthenes筛法获得一个无限列表^3，然后再根据实际需要获取前N个素数。代码如下:

1
2
3

-- Eratosthenes筛法
sieve (p:xs) = p : sieve [x| x <- xs , x `mod` p /=0 ]
primes = sieve [2..] -- maxBound::Int

对primes列表使用take，可获取前100个素数：take 100 primes；也可以使用takeWhile函数获取小于100的所有素数:takeWhile (< 100) primes：

*Main> print $ take 10 primes
[2,3,5,7,11,13,17,19,23,29]
*Main> print $ takeWhile (< 100) primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

分解的算法也很简单，假设迭代函数处理整数$x$，如果$x=1$则返回Nothing终止迭代；否则从小于$\sqrt x$的素数集合查找第一个可以整除$x$的素数，如果找到此素数$y$，$x\equiv 0\mod{y}$，就将$y$放入分解结果，并设置$x=x/y$，进入下次迭代；还有一种情况，即$x$本身就是素数，那么素数集合中必然找不到$y$将其整除，这种情况可将$x$放入分解结果，并设置$x=1$，下次分解会自动终止。代码如下：

-- 任意整数的因数分解
decompose :: Integer -> [Integer]
decompose x = unfoldr f x where
    f 1 = Nothing
    f t = case find (\j -> t `mod` j == 0) (takeWhile (\y-> y ^2 <= t) primes) of
        Nothing -> Just (t, 1)
        Just a -> Just (a, t `div` a)

测试结果如下：

*Main> decompose 1
[]
*Main> decompose 5
[5]
*Main> decompose 55
[5,11]
*Main> decompose 550
[2,5,5,11]

利用素数相互互斥的性质:$\forall i\neq j: p_i \equiv 1\mod{p_j}$，我们在迭代函数里可一次取出多个素数因子，以提高效率：

decompose x = concat $ unfoldr f x where
    f 1 = Nothing
    f t = case [y | y<-takeWhile (\y-> y ^2 <= t) primes, t `mod` y == 0] of
        [] -> Just ([t], 1)
        xs -> Just (xs, foldl div t xs)

不过这个函数对于多重因子($t_i>1$)是多次迭代获取的,如decompose 12$\rightarrow$[2,3,2]。可以在获取结果之后再进行一次排序，获得和原来函数一致的结果:decompose = sort.concat$unfoldr...，当然你也可以使用group将相同的因子合并一下:group decompose 12--[[2,2,2],[3]]