我想测试 foldl 与 foldr。从我所看到的情况来看，由于尾递归优化，您应该尽可能使用 foldl 而不是 foldr。
这是有道理的。但是，运行此测试后，我很困惑：
foldr（使用 time 命令时需要 0.057 秒）：
a::a -> [a] -> [a]
a x = ([x] ++ )
main = putStrLn(show ( sum (foldr a [] [0.. 100000])))
foldl（使用 time 命令时需要 0.089s）：
b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])
main = putStrLn(show ( sum (foldl b [] [0.. 100000])))
很明显，这个例子是微不足道的，但我对为什么 foldr 击败 foldl 感到困惑。这不应该是 foldl 获胜的明显案例吗？
欢迎来到懒惰评估的世界。
当您从严格评估的角度考虑它时， foldl 看起来“好”而 foldr 看起来“坏”，因为 foldl 是尾递归的，但是 foldr 必须在堆栈中构建一个塔，以便它可以首先处理最后一项。
然而，懒惰的评估扭转了局面。以map函数的定义为例：
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
如果 Haskell 使用严格的评估，这不会太好，因为它必须先计算尾部，然后添加项目（对于列表中的所有项目）。似乎唯一有效的方法是反向构建元素。
但是，由于 Haskell 的惰性求值，这个 map 函数实际上是高效的。Haskell 中的列表可以被认为是生成器，这个 map 函数通过将 f 应用于输入列表的第一项来生成它的第一项。当它需要第二个项目时，它只是再次做同样的事情（不使用额外的空间）。
事实证明，map可以用以下方式描述foldr：
map f xs = foldr (\x ys -> f x : ys) [] xs
很难通过观察来判断，但是惰性求值会起作用，因为 foldr 可以f立即给出它的第一个参数：
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
因为f定义的 bymap可以仅使用第一个参数返回结果列表的第一项，折叠可以在恒定空间中惰性操作。
现在，惰性评估确实会反击。例如，尝试运行 sum [1..1000000]。它会产生堆栈溢出。为什么要呢？它应该只是从左到右评估，对吧？
让我们看看 Haskell 是如何评估它的：
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) 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)
Haskell 懒得执行添加。取而代之的是，它以一堆未经评估的笨拙而告终，不得不被迫获得一个数字。在此评估期间会发生堆栈溢出，因为它必须深度递归才能评估所有 thunk。
幸运的是，Data.List 中有一个特殊的函数被称为foldl'严格操作。 foldl' (+) 0 [1..1000000]不会堆栈溢出。（注意：我尝试在您的测试中替换foldl为foldl'，但实际上它使其运行速度变慢。）
编辑：再次查看这个问题时，我认为所有当前的解释都有些不足，所以我写了一个更长的解释。
不同之处在于如何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])
...
我省略了列表连接的细节，但这就是减少的过程。重要的部分是所有内容都得到处理以最小化列表遍历。唯一遍历列表一次，foldr连接不需要连续遍历列表，sum最终一次性消耗列表。至关重要的是，列表的头部从foldr立即可用到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才能开始工作。这总体上效率要低得多。运行这两个版本+RTS -s显示了 foldl 版本的垃圾收集性能很差。
这也是foldl'无济于事的情况。增加的严格性foldl'不会改变中间列表的创建方式。在 foldl' 完成之前，列表的头部仍然不可用，因此结果仍然会比 with 慢foldr。
我使用以下规则来确定最佳选择fold
foldl'（例如，这将是唯一/最终遍历）foldr.foldl.在大多数情况下foldr是最好的折叠函数，因为遍历方向对于列表的惰性求值是最优的。它也是唯一能够处理无限列表的。在某些情况下，额外的严格性foldl'可以使其更快，但这取决于您将如何使用该结构以及它有多懒惰。
我认为还没有人真正说出这个问题的真正答案，除非我遗漏了一些东西（这很可能是真的并且受到反对票的欢迎）。
我认为在这种情况下最大的不同是foldr构建这样的列表：
[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))
而foldl像这样构建列表：
((([0] ++ [1]) ++ [2]) ++ ... ) ++ [999888]) ++ [999999]) ++ [1000000]
细微的差别，但请注意，在foldr版本中++始终只有一个列表元素作为其左参数。在该foldl版本中，左参数中最多有 999999 个元素++（平均约为 500000），但右参数中只有一个元素。
但是，++所花费的时间与左参数的大小成正比，因为它必须查看整个左参数列表到最后，然后将最后一个元素重新指向右参数的第一个元素（充其量，也许它实际上需要做一个副本）。正确的参数列表没有改变，所以不管它有多大。
这就是foldl版本慢得多的原因。在我看来，这与懒惰无关。
问题是尾递归优化是内存优化，而不是执行时间优化！
尾递归优化避免了记住每个递归调用的值。
所以， foldl 实际上是“好”，而 foldr 是“坏”。
例如，考虑 foldr 和 foldl 的定义：
foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs
foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)
这就是表达式“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...，而是将整个表达式 (((0+1)+2)+3) 作为参数懒惰地传递，并且在最后一次评估之前不评估它foldl，它到达基本情况并返回作为第二个参数（z）传递的值，但尚未评估。
另一方面，这就是 foldr 的工作方式：
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 在最后一次调用中评估整个表达式，避免需要返回来达到记住的值， foldr 没有。foldr 为每个调用记住一个整数，并在每个调用中执行一个加法。
重要的是要记住 foldr 和 foldl 并不总是等价的。例如，尝试在拥抱中计算以下表达式：
foldr (&&) True (False:(repeat True))
foldl (&&) True (False:(repeat True))
foldr 和 foldl 仅在此处描述的某些条件下是等效的
（对不起，我的英语不好）
对于 a，[0.. 100000]列表需要立即展开，以便 foldr 可以从最后一个元素开始。然后当它把东西折叠在一起时，中间结果是
[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list
因为不允许任何人更改此列表值（Haskell 是一种纯函数式语言），所以编译器可以自由地重用该值。中间值，like[99999, 100000]甚至可以只是指向扩展[0.. 100000]列表的指针，而不是单独的列表。
对于 b，查看中间值：
[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]
这些中间列表中的每一个都不能重复使用，因为如果您更改列表的末尾，那么您已经更改了指向它的任何其他值。因此，您正在创建一堆额外的列表，这些列表需要时间来构建内存。因此，在这种情况下，您会花费更多时间来分配和填写这些中间值列表。
由于您只是制作列表的副本，因此 a 运行得更快，因为它首先展开整个列表，然后不断地将指针从列表的后面移动到前面。
尾部也foldl没有优化。foldr它只是foldl'.
但是在您的情况下，使用++withfoldl'并不是一个好主意，因为连续评估++会导致一次又一次地遍历不断增长的累加器。
好吧，让我以一种明显不同的方式重写你的函数 -
a :: a -> [a] -> [a]
a = (:)
b :: [b] -> b -> [b]
b = flip (:)
您会看到 b 比 a 更复杂。如果要精确，a需要一个减少步骤来计算值，但b需要两个。这使得您正在测量的时间差，在第二个示例中，必须执行两倍的减少。
//编辑：但是时间复杂度是一样的，所以我不会太在意。