强大的 fold

fold 是重要的操作符（ruby 里面叫 inject）

基本定义（Prelude.foldr）：

-- 从右往左卷
foldl f z [] = z
foldl f z (x : xs) = foldl f (f z x) xs
-- 从左往右卷
foldr f z [] = z
foldr f z (x : xs) = f x (foldr f z xs)

另一种定义方式是通过 CPS 。

令 z = 第一个元素，就得到变种 foldl1, foldr1。

注意 foldl 虽然是尾递归，但是消耗内存和 foldr 一样：
延迟求值使 f z x 不会马上被计算出来，依然会产生很大的调用栈。

省内存（strict 版本， Data.List.foldl'）的定义如下：

foldl' f z []     = z
foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs

--------------------------------------------------------------------------
很多常用的函数都可以通过 fold 产生：

sum = foldl (+) 0
product = foldl (*) 1
and = foldl1 (&&)
or = foldl1 (||)
(++) ys = foldr (:) ys
length = foldl (\n x -> 1 + n) 0
reverse = foldl (\ys x -> x : ys) []
map f = foldr (\x ys -> f x : ys) []
filter p = foldr (\x ys -> if p x then x : ys else ys) []

下面，let fold = foldr，看看还能玩什么花样。

---------------------------------------------------------------------------
“融”定理（the fusion property of fold）
如果 h (g x z) = f x (h z)
那么 h . fold g z = fold f (h z)

应用举例：
(* 3) . sum = (* 3) . fold (+) 0
所以这里 h = (* 3)， g = (+)

令 f x y = x * 3 + y，则有
h (g x z) = f x (g z)

再根据上面的定理
(* 3) . sum = fold f (h 0) = fold (\x y -> x * 3 + y) 0
也就是说，列表中所有元素的和乘以 3 ，等于每个元素乘 3 再求和。

这个结论人脑想很浅显，但机器想就不是这回事了。
fold 的这个性质给机器推理提供了新的方法。

一些算法写出来简单易读，但是运行效率很低。利用这个性质进行变换，可以在不影响可读性的前提下优化算法。
ghc 里面就有不少这样的优化。

----------------------------------------------------------------------------
“切香蕉”性质（banana split property of fold）
梅姐 good job！

假设我们要计算和、平方和、立方和

sum'squareSum'cubicSum l = (sum l, squareSum l, cubicSum l)

这样我们要遍历这个 list 3 遍。（这个问题在 C++ 模板编程中也经常遇到呢）

但是用 fold 就不一样了:

sum'squareSum'cubicSum =
  foldr (\x (s1, s2, s3) -> (s1 + x, s2 + x ^ 2, s3 + x ^ 3)) (0, 0, 0)

----------------------------------------------------------------------------
源生递归 = fold
在递归神教的教义中可以找到源生递归（primitve recursion）的通用模式：

h y [ ] = f y
h y (x : xs) = g y x xs (h y xs)

假定递归函数如上式定义，取出 f 和 g，然后用 fold 定义 k 如下：

k y = fold i j
  where
    i x (z, xs) = (g y x xs z, x : xs)
    j = (f y, [])

最后，我们得到的 k 是这么一个东西，它满足：

k y xs == (h y xs, xs)

于是…… 万物至 fold …… （也不尽然，像 Ackman 函数那样的高阶递归就不能轻易的写成 fold）

由于 fold 已经自带边界条件，所以用 fold 表达的函数不用写两行：

--组合 list 内的所有函数
compose = foldr (.) id

foldl 也可以用 foldr 表示：

foldl f v xs = fold (\x g -> (\a -> g (f a x))) id xs v

可惜如果不引入递归，foldr 没法用 foldl 表示——这也体现了命令式的循环的弱点。

-----------------------------------------------------------------------------
推荐 paper：
http://www.cs.nott.ac.uk/~gmh/fold.pdf