foldl是尾recursion，那么foldr怎么比foldl跑得快呢？
我想testingfoldl vs foldr。 从我看到你应该使用foldl在任何时候都可以由于尾巴reccursion优化。
这是有道理的。 但是，运行这个testing后，我很困惑：
（使用时间命令需要0.057s）：
a::a -> [a] -> [a] ax = ([x] ++ ) main = putStrLn(show ( sum (foldr a [] [0.. 100000]))) foldl（使用时间命令时需要0.089s）：
b::[b] -> b -> [b] b xs = ( ++ xs). (\y->[y]) main = putStrLn(show ( sum (foldl b [] [0.. 100000])))
很显然，这个例子是微不足道的，但是我为什么会打败foldl而感到困惑。 这不是一个明确的情况下foldl胜利吗？
欢迎来到懒惰评价的世界。
当你严格评估时，foldl看上去是“好的”，foldr看起来“不好”，因为foldl是尾recursion的，但是foldr将不得不在堆栈中build立一个塔，所以它可以先处理最后一个项目。
然而，懒惰的评估变成了表格。 以例如地图function的定义为例：
map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = fx : map f xs
如果Haskell使用严格的评估，这将不会太好，因为它必须先计算尾部，然后预先计算该项目（对于列表中的所有项目）。 看起来，有效地做到这一点的唯一方法就是反向构build元素。
但是，由于Haskell的懒惰评估，这个map函数实际上是有效的。 Haskell中的列表可以被认为是生成器，并且这个映射函数通过将f应用于input列表的第一项来生成它的第一项。 当它需要第二个项目时，它只是再次做同样的事情（不使用额外的空间）。
事实certificate， map可以用foldr来描述：
map f xs = foldr (\x ys -> fx : ys) [] xs
看着它很难说，但懒惰的评价踢，因为foldr可以马上给出第一个说法：
foldr fz [] = z foldr fz (x:xs) = fx (foldr fz xs)
因为由map定义的f可以仅使用第一个参数返回结果列表的第一个项目，所以fold可以在不变的空间中懒散地操作。
现在，懒惰的评价反了。 例如，尝试运行总和[1..1000000]。 它会产生堆栈溢出。 为什么要这样？ 它应该从左到右进行评估，对吧？
让我们看看Haskell如何评估它：
foldl fz [] = z foldl fz (x:xs) = foldl f (fzx) xs sum = foldl (+) 0 sum [1..1000000] = foldl (+) 0 [1..1000000] = foldl (+) ((+) 0 1) [2..1000000] = foldl (+) ((+) ((+) 0 1) 2) [3..1000000] = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000] ... = (+) ((+) ((+) (...) 999999) 1000000)
哈斯克尔懒得去执行添加。 相反，它结束了一个不被评估的thunk的塔，必须被迫获得一个数字。 在这个评估过程中发生堆栈溢出，因为它必须深入recursion来评估所有的thunk。
幸运的是，Data.List中有一个称为foldl'的特殊函数，严格操作。 foldl' (+) 0 [1..1000000]不会堆栈溢出。 （注意：我试过在你的testing中用foldl'replacefoldl ，但实际上它使得它运行得更慢。）
编辑：再次看到这个问题，我认为所有目前的解释都有些不足，所以我写了一个更长的解释。
区别在于foldl和foldr如何应用其还原函数。 看看foldr情况，我们可以把它扩展为
foldr (\x -> [x] ++ ) [] [0..10000] [0] ++ foldr a [] [1..10000] [0] ++ ([1] ++ foldr a [] [2..10000]) ...
这个列表是用sum来处理的，消耗它如下：
sum = foldl' (+) 0 foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000])) foldl' (+) 0 (0 : [1] ++ ... ++ [10000]) -- get head of list from '++' definition foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000]) -- add accumulator and head of list foldl' (+) 0 (1 : [2] ++ ... ++ [10000]) foldl' (+) 1 ([2] ++ ... ++ [10000]) ...
我省略了列表连接的细节，但这是如何进行的。 最重要的部分就是一切都得到处理，以尽量减less列表遍历。 foldr只遍历列表一次，连接不需要连续的列表遍历， sum最后一次消耗列表。 重要的是，列表的头可以立即从sum ， sum可以立即开始工作，值可以gc'd生成。 借助融合框架（如vector ，甚至中间列表也可能会被融合。
对比这个foldl函数：
b xs = ( ++xs) . (\y->[y]) foldl b [] [0..10000] foldl b ( [0] ++ [] ) [1..10000] foldl b ( [1] ++ ([0] ++ []) ) [2..10000] foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000] ...
请注意，直到foldl完成之后，列表的头部才可用。 这意味着在sum可以开始工作之前，整个列表必须在内存中build立。 总体来说这效率低得多。 使用+RTS -s运行这两个版本显示foldl版本的可悲垃圾收集性能。
这也是foldl'不起作用的情况。 foldl'增加的严格性不会改变中间列表的创build方式。 在foldl'结束之前，列表头仍然不可用，所以结果仍然比foldr慢。
我使用以下规则来确定fold的最佳select
- 对于折叠是一个减less ，使用
foldl'（例如，这将是唯一的/最终的遍历） - 否则使用
foldr。 - 不要使用
foldl。
在大多数情况下， foldr是最好的折叠函数，因为遍历方向对列表的懒惰评估是最佳的。 它也是唯一一个能够处理无限列表的程序。 在某些情况下， foldl'的额外的严格性可以使它更快，但是这取决于你将如何使用这个结构以及它是多么的懒惰。
我不认为有人真的在这个问题上说出了真正的答案，除非我错过了一些东西（这可能是真实的，而且是值得赞赏的）。
我认为在这种情况下最大的不同在于， foldrbuild立这样的列表：
[0] ++（[1] ++（[2] ++（… ++ [1000000]）））
而foldlbuild立像这样的列表：
（（（[0] ++ [1]）++ [2]）++ …）++ [999888]）++ [999999]）++ [1000000]
微妙之处不同，但注意到在foldr版本中， ++总是只有一个列表元素作为左边的参数。 使用foldl版本，在++的左边参数（平均大约500000）中有多达999999个元素，但是右边参数中只有一个元素。
然而， ++需要的时间与左侧参数的大小成正比，因为它必须查看整个左侧参数列表到最后，然后将最后一个元素重新指向右侧参数的第一个元素（最好，也许它实际上需要做一个副本）。 正确的参数列表是不变的，所以不pipe它有多大。
这就是为什么foldl版本要慢得多。 在我看来，这与懒惰没有任何关系。
问题是尾recursion优化是一个内存优化，而不是执行时间的优化！
尾recursion优化避免了需要记住每个recursion调用的值。
所以，foldl实际上是“好”，foldr是“坏”。
例如，考虑foldr和foldl的定义：
foldl fz [] = z foldl fz (x:xs) = foldl f (z `f` x) xs foldr fz [] = z foldr fz (x:xs) = x `f` (foldr fz xs)
这就是如何评估expression式“foldl（+）0 [1,2,3]”：
foldl (+) 0 [1, 2, 3] foldl (+) (0+1) [2, 3] foldl (+) ((0+1)+2) [3] foldl (+) (((0+1)+2)+3) [ ] (((0+1)+2)+3) ((1+2)+3) (3+3) 6
请注意，foldl不记住值0,1,2 …，但将整个expression式（（（0 + 1）+2）+3）作为参数进行延迟，直到最后一次评估foldl，它到达基本情况，并返回作为第二个参数（z）传递的值，但尚未评估。
另一方面，这是多么工作：
foldr (+) 0 [1, 2, 3] 1 + (foldr (+) 0 [2, 3]) 1 + (2 + (foldr (+) 0 [3])) 1 + (2 + (3 + (foldr (+) 0 []))) 1 + (2 + (3 + 0))) 1 + (2 + 3) 1 + 5 6
这里的重要区别在于，foldl在最后一次调用中评估整个expression式，避免需要返回以达到记住的值， 请记住每个呼叫一个整数，并在每个呼叫中执行一个加法。
重要的是要记住，foldr和foldl并不总是等价的。 例如，尝试在拥抱中计算这个expression式：
foldr (&&) True (False:(repeat True)) foldl (&&) True (False:(repeat True))
foldr和foldl只有在这里描述的某些条件下才是等价的
（对不起，我的英语不好）
对于a，需要立即扩展[0.. 100000]列表，使得foldr可以从最后一个元素开始。 然后，当它们合在一起时，中间结果是
[100000] [99999, 100000] [99998, 99999, 100000] ... [0.. 100000] -- ie, the original list
因为没有人允许改变这个列表值（Haskell是一个纯粹的函数式语言），所以编译器可以自由地重用这个值。 像[99999, 100000]这样的中间值甚至可以简单地指向扩展的[0.. 100000]列表而不是单独的列表。
对于b，看一下中间值：
[0] [0, 1] [0, 1, 2] ... [0, 1, ..., 99999] [0.. 100000]
这些中间列表中的每一个都不能被重用，因为如果你改变列表的结尾，那么你已经改变了任何指向它的值。 所以你正在创build一堆额外的列表，需要时间来build立内存。 所以在这种情况下，你花了很多时间分配和填写这些中间值的列表。
由于您只是制作了一个列表副本，所以a运行速度更快，因为它首先展开整个列表，然后继续将列表后面的指针移到最前面。
foldl和foldr都不是尾部优化的。 它只是foldl' 。
但是在你的情况下，使用++与foldl'不是好主意，因为连续的++评估将导致遍历不断增长的累加器。
那么，让我以一种差别应该是显而易见的方式重写你的function –
a :: a -> [a] -> [a] a = (:) b :: [b] -> b -> [b] b = flip (:)
你看到b比a更复杂。 如果你想精确a需要一个减less价值的计算步骤，但是需要两个。 这使得你正在测量的时间差，在第二个例子中必须执行两倍的减less量。
//编辑：但时间复杂度是一样的，所以我不会为此烦恼。
