欢迎来到懒惰评估的世界。
当您从严格的求值Angular 考虑时，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)

因为由map定义的f可以只使用第一个参数返回结果列表的第一项，所以fold可以在常量空间中惰性地操作。
现在，惰性求值确实会反咬一口。例如，尝试运行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，这些thunk必须被强制得到一个数字。堆栈溢出发生在这个求值过程中，因为它必须深度递归才能求值所有的thunk。
幸运的是，Data.List中有一个名为foldl'的特殊函数，它严格地操作。foldl' (+) 0 [1..1000000]不会发生堆栈溢出。（注意：我在测试中尝试用foldl'替换foldl，但实际上这会使它运行得更慢。）

再看这个问题，我觉得目前所有的解释都有些不足，所以我写了一个更长的解释。
不同之处在于foldl和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'完成之前保持不可用，所以结果仍然比foldr慢。
我使用以下规则来确定fold的最佳选择

• 对于 * 约简 * 的折叠，使用foldl'（例如，这将是唯一/最终遍历）
• 否则使用foldr。
• 不要使用foldl。

在大多数情况下foldr是最好的fold函数，因为遍历方向对于列表的惰性求值是最优的。它也是唯一一个能够处理无限列表的函数。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的最后一次求值才对其求值，在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 no. foldr为每次调用记住一个整数，并在每次调用中执行加法。
记住foldr和foldl并不总是等价的，这一点很重要。例如，试着用hugs来计算下面的表达式：

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是一个纯函数语言），所以编译器可以自由地重用这个值，中间值，比如[99999, 100000]，甚至可以是指向扩展的[0.. 100000]列表的指针，而不是单独的列表。
对于B，查看中间值：

[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]

每一个中间列表都不能被重用，因为如果你改变了列表的结尾，那么你就改变了指向它的所有其他值，所以你创建了一堆额外的列表，这些列表需要时间在内存中构建，所以在这种情况下，你花了更多的时间来分配和填充这些中间值列表。
因为你只是复制了一个列表，所以a运行的更快，因为它从展开整个列表开始，然后只是不断地将指针从列表的后面移动到前面。

foldl和foldr都不是尾部优化的，它只是foldl'。
但在您的情况下，将++与foldl'一起使用并不是一个好主意，因为连续计算++将导致一次又一次地遍历增长的累加器。

好吧，让我重写一下你的函数，让它们的区别变得显而易见-

a :: a -> [a] -> [a]
a = (:)

b :: [b] -> b -> [b]
b = flip (:)

你可以看到B比a更复杂。如果你想精确，a需要一个缩减步骤来计算值，但b需要两个步骤。这就产生了你测量的时间差，在第二个例子中，必须执行两倍的缩减。
//edit：但是时间复杂度是一样的，所以我不会太在意它。