在大多数资源中，建议使用 foldl'，但是在 concat 中使用 foldr 而不是 foldl' 的原因是什么？
luq*_*qui 14
编辑我在这个答案中谈到了懒惰和生产力，在兴奋中我忘记了 jpmariner 在他们的答案中关注的一个非常重要的点：左关联(++)是二次时间！
foldl'当您的累加器是严格类型时适用，例如大多数小型类型，例如Int，甚至是大型脊椎严格数据结构，例如Data.Map。如果累加器是严格的，那么在给出任何输出之前必须消耗整个列表。 foldl'在这些情况下使用尾递归来避免炸毁堆栈，但foldr不会并且会表现得很差。另一方面，foldl' 必须以这种方式消耗整个列表。
foldl f z [] = z
foldl f z [1] = f z 1
foldl f z [1,2] = f (f z 1) 2
foldl f z [1,2,3] = f (f (f z 1) 2) 3
需要列表的最后一个元素来评估最外层的应用程序，因此无法部分使用列表。如果我们用 展开它(++)，我们将看到：
foldl (++) [] [[1,2],[3,4],[5,6]]
= (([] ++ [1,2]) ++ [3,4]) ++ [5,6]
^^
= ([1,2] ++ [3,4]) ++ [5,6]
= ((1 : [2]) ++ [3,4]) ++ [5,6]
^^
= (1 : ([2] ++ [3,4])) ++ [5,6]
^^
= 1 : (([2] ++ [3,4]) ++ [5,6])
（我承认，如果您对缺点列表没有很好的感觉，这看起来有点神奇；不过，值得弄脏细节）
看看我们如何在冒泡到前面之前在下降的过程中评估每个 (++)（标^^有评估时间）1？在那之前，它1是“隐藏”在功能应用程序下的。
foldr，另一方面，对于像列表这样的非严格累加器有好处，因为它允许累加器在整个列表被消耗之前产生信息，这可以将许多经典的线性空间算法降低到恒定空间！这也意味着，如果您的列表是无限的，foldr则是您唯一的选择，除非您的目标是使用 CPU 为房间供暖。
foldr f z [] = z
foldr f z [1] = f 1 z
foldr f z [1,2] = f 1 (f 2 z)
foldr f z [1,2,3] = f 1 (f 2 (f 3 z))
foldr f z [1..] = f 1 (f 2 (f 3 (f 4 (f 5 ...
我们可以毫不费力地表达最外层的应用程序，而无需查看整个列表。foldr以与我们相同的方式扩展foldl：
foldr (++) z [[1,2],[3,4],[5,6]]
= [1,2] ++ ([3,4] ++ ([5,6] ++ []))
= (1 : [2]) ++ (3,4] ++ ([5,6] ++ []))
^^
= 1 : ([2] ++ ([3,4] ++ ([5,6] ++ [])))
1立即产生，而无需评估(++)除第一个之外的任何s。因为这些(++)s 都没有被评估，而且 Haskell 是懒惰的，所以在消耗更多输出列表之前甚至不必生成它们，这意味着concat可以在恒定空间中运行这样的函数
concat [ [1..n] | n <- [1..] ]
这在严格的语言中需要任意长度的中间列表。
如果这些缩减看起来有点太神奇，并且如果您想更深入，我建议检查其来源(++)并根据其定义进行一些简单的手动缩减以了解它。（请记住[1,2,3,4]是 的符号1 : (2 : (3 : (4 : [])))）。
一般来说，以下似乎是提高效率的强有力的经验法则：foldl'当您的累加器是一个严格的数据结构时使用，foldr当它不是时使用。如果你看到一个朋友经常使用foldl并且不阻止他们，你是什么样的朋友？
在 concat 中使用 foldr 而不是 foldl' 的原因？
如果您[1,2,3] ++ [6,7,8]在命令式编程思维中考虑，您所要做的就是将节点 3 处的下一个指针重定向到节点 6，当然假设您可以更改左侧操作数。
这是 Haskell，您不能更改左侧操作数，除非优化器能够证明它++是其左侧操作数的唯一用户。
缺少这样的证明，其他指向节点 1 的 Haskell 表达式完全有权假设节点 1 永远位于长度为 3 的列表的开头。在 Haskell 中，纯表达式的属性在其生命周期内不能改变。
因此，在一般情况下，操作符++必须通过复制其左侧操作数来完成其工作，然后可以将节点 3的副本设置为指向节点 6。 另一方面，右侧操作数可以按原样.
因此，如果从右侧开始折叠 concat 表达式，则串联的每个组件都必须精确复制一次。但是如果你从左边开始折叠表达式，你就会面临很多重复的重复工作。
让我们试着定量地检查一下。为了确保没有优化器会通过证明任何事情来妨碍，我们将只使用ghci解释器。它的强项是交互性而不是优化。
那么让我们介绍一下ghci的各种候选，并打开统计模式：
$ ghci
?>
?> myConcat0 = L.foldr (++) []
?> myConcat1 = L.foldl (++) []
?> myConcat2 = L.foldl' (++) []
?>
?> :set +s
?>
我们将通过使用数字列表并打印它们的总和来强制进行全面评估。
首先，让我们通过从右侧折叠来获得基线性能：
?>
?> sum $ concat [ [x] | x <- [1..10000::Integer] ]
50005000
(0.01 secs, 3,513,104 bytes)
?>
?> sum $ myConcat0 [ [x] | x <- [1..10000::Integer] ]
50005000
(0.01 secs, 3,513,144 bytes)
?>
其次，让我们从左边折叠，看看这是否有所改善。
?>
?> sum $ myConcat1 [ [x] | x <- [1..10000::Integer] ]
50005000
(1.26 secs, 4,296,646,240 bytes)
?>
?> sum $ myConcat2 [ [x] | x <- [1..10000::Integer] ]
50005000
(1.28 secs, 4,295,918,560 bytes)
?>
所以从左边折叠会分配更多的瞬态内存并花费更多的时间，可能是因为这种重复的复制工作。
作为最后的检查，让我们将问题规模扩大一倍：
?>
?> sum $ myConcat2 [ [x] | x <- [1..20000::Integer] ]
200010000
(5.91 secs, 17,514,447,616 bytes)
?>
我们看到，将问题规模加倍会导致资源消耗乘以大约 4。在 的情况下，从左侧折叠具有二次成本concat。
看看 luqui 的精彩回答，我们看到两者都关注：
碰巧以相同的方式投票，即赞成从右边折叠。
因此 Haskell 库concat函数使用foldr.
在使用带有 -O3 选项而不是 ghci 的 GHC v8.6.5 运行一些测试之后，似乎我对优化器混淆测量的先入为主的想法是错误的。
即使使用 -O3，对于 20,000 的问题大小，基于 foldr 的 concat 函数也比基于 foldl' 的函数快 500 倍。
因此，要么优化器无法证明可以更改/重用左操作数，要么根本不尝试。