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

基本结论 Link to heading

haskell wiki

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

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

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

深入讨论 Link to heading

foldr Link to heading

比如：

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

forall x. c * x = c

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

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

foldl Link to heading

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

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

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

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

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

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

交换半群 Link to heading

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

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

如果是同一个类型呢？

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

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