fold是合并列表等重要的操作,其中主要有foldr和foldl,也即从右向左和从左向右。一般来说,后者会优于前者。但在haskell中,并不是这样。

基本结论

haskell wiki

主要内容都写在上面的wiki里了,这里仅做一个简单的小结。

  1. 由于惰性求值的关系,在haskell中foldl并不比foldr性能更好。
  2. foldl'是立即求值版本,效率效高,但没有惰性的关系无法配合haskell的部分特性,如无穷列表。
  3. foldr在haskell中也意义着right method。
  4. foldr相较于foldl可以更好的适用于惰性特性,如无穷列表。特别地,其可以应用短路求值,而foldl不可。

关于第四条的短路求值,是默认使用foldr的一个主要理由。

深入讨论

foldr

比如:

[ .., c, .., b, a,]

forall x. c * x = c

(.. * (c * (.. * (b * (a * x)))))

这里从左至右计算(即右侧惰性),所以当一开始遇到了c,就直接停止。特别应用在haskell的类型匹配方面。可以带来一些通过无穷列表实现的trick。

foldl

那么,引入了一个新的问题,如果我左侧惰性,即优先根据右侧返回结果,是不是可以使用foldl呢?

[c, b, a, ...]
forall x. x * c = c

((((x * c) * b) * a) * ...)

最里层的确实可以匹配到,但这之后,其从右值变成了左值。就不可以匹配了。

那如果是在最外层有个可以匹配到的呢?比如(((x * a) * b) * ...) * c。首先foldl根本不能展开到c处。因为这是一个无穷列表。而如果c是处在列表中间,那么和最开始的情况是一样的。

这里还需要明确一点,匹配的顺序,是按参数顺序进行的。左侧哪怕是匹配_,也会把参数展开。即,从foldl的性质和ghc的实现上,就必然不可能使用惰性带来的一些优势。

交换半群

如果我们的操作符合交换半群呢?

显然,这不可能啊!因为我们的类型是,(a -> b -> b) -> b -> t a -> b或者反过来啊!数据根本不是一个集合内的,没有讨论的价值。

如果是同一个类型呢?

答案是不一定可以。因为对于匹配,是有优先顺序的,比如c * _写在前面而_ * c写在后面,对于foldr就可以和正常一样的操作,但如果两者定义顺序反过来,当尝试匹配_ * c的时候,就会对第二个参数进行展开,因为要确定是否可以进行匹配。从而进入了与foldl一样的无穷展开。

对于foldl,如果先尝试匹配_ * c的话,同样会进入无穷展开。因为,匹配是按参数顺序进行的。如上文foldl所述。