函数式编程里面的fold

第一：基本概念

fold在函数式编程里面的基本含义是遍历数据结构，最后产生一个聚合值。最简单的例子是sum list = foldl (+) 0 list

fold抽象了两个动作，一个是遍历数据结构本身，一个是累积值和元素之间的关系。用了fold后就只需要关心聚合的初始值是什么，每个元素和累积值如何产生下一个累积值。

比如上面的sum的例子，初始值是0， 步进函数+， 也就是每个元素和累计值相加产生下一个累计值。

第二：foldl 和 foldr

foldl :: (acc -> e -> acc) -> acc -> [e] -> acc

e:element 数据结构中的其中一个元素，acc:accumulator 累积值

(acc->e->acc) 步进函数

foldl 的遍历是从第一个元素开始，到最后一个元素结束。累积值首先和第一个元素应用步进函数。

foldr :: (e -> acc -> acc) -> acc -> [e] -> acc

(e->acc->acc) 步进函数

foldl 的遍历是从最后一个元素开始，到第一个结束。累积值首先和最后一个元素应用步进函数。

两个的步进函数的签名是有区别的。

第三：惰性求值

假定数据结构为列表 [x1,x2,x3]

在scala里面，foldl是尾递归的，因为step 函数产生的下一个accumulator作为下一次step的函数的参数，因此每个accumulator都会被先求值出来。这样迭代就只需要两个状态，一个是上一次的accumulator，一个是当前的元素，这样直接覆盖就可以了。

但是如果是惰性求值的语言，step函数的两个参数之一的accumulator被保持为表达式，并未求值，那么这个表达式一直在stack上保存step函数，因此最后的表达式是

step(step(step(init,x1),x2),x3)。如果数据结构的深度很大，必然造成堆栈溢出。

在非惰性求值的语言里面，foldr是可能造成堆栈溢出的。因为foldr最后生成的表达式是step(x1,step(x2,step(x3,init))),只有当表达式完全展开之后，step(x3,init)开始得到求值结果之后才会一级一级的退栈。

但是在惰性求值的语言里面，foldr是否会造成堆栈溢出和step函数本身关系很大。如果step函数在步进的过程中因为判断元素的属性而提前退出，不需要继续求值后面的step(x2,step(x3,init))，那么就可能不会堆栈溢出（看提前退出前的数据量的大小了）。

对于sum这个函数，在惰性求值语言语言如Haskell里面foldr，foldl在列表元素够大的情况下都会溢出，在scala语言里面，foldl不会溢出，而foldr会溢出。

第四：惰性数据结构

foldr在惰性数据结构的配合下可以做到效率和模块化的完美分离。

对于表达式List(1,3,5,7).map(_+2).filter(_ % 2==1).sum，可能对效率要求比较高的人就不能接受，因为会遍历列表3次。但是不得不承认的是这个代码的易读和可理解性是很好的。如果为了效率把遍历减少到一次，可能需要读完整个代码才能理解这段代码做了什么事情。

但是利用惰性数据结构来说，是完全可以做到鱼与熊掌兼得的。

第五：总结

fold是典型的函数式语言里面的抽象再抽象的例子，有了fold之后比如list函数基本都可以构建在他之上了（对于消费list的函数）。

对于产生list的函数来说，对应的也有unfold。（待续了）