为什么foldl有时比foldr慢？ 我有一个列表的列表“一”像foldl with（++）比foldr慢很多
a = [[1],[2],[3]]
，并希望通过折叠
foldr (++) [] a
将其更改为一个列表，它工作正常（时间复杂度为O（n））。但是如果我使用foldl，它会很慢（时间复杂度是O（n^2））。
foldl (++) [] a
如果与foldl只是折叠从左侧的输入列表中，
(([] ++ [1]) ++ [2]) ++ [3]
和foldr相似是从右侧，
[1] ++ ([2] ++ ([3] ++ []))
计算的次数（++）在两种情况下应该是相同的。为什么foldr这么慢？根据时间复杂度，foldl看起来好像将输入列表扫描多倍于foldr一样。我用下面的计算机时间
length $ fold (++) [] $ map (:[]) [1..N] (fold is either foldl or foldr)
这是因为如何++作品。请注意，它的第一个参数是由归纳定义的。
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
递归调用的数量仅取决于length xs。
正因为如此，在xs ++ ys比其他方式有一个小的xs和一个大的ys更方便。
注意，折叠右侧达到这样的：
[1] ++ ([2] ++ ([3] ++ ...
我们只有很短（O（1） - 长度）上的++左侧，使得折成本为O（n）名单。
不是折叠左边是坏：
((([] ++ [1]) ++ [2]) ++ [3]) ++ ...
左侧的参数变得越来越大。因此，我们在这里得到O（n^2）的复杂性。
考虑输出列表是如何被要求的，这个参数可以做得更精确。可以观察到foldr以“流式”方式产生其结果，其中要求例如第一个输出列表单元格只强制输入的一小部分 - 只需要执行第一个输入列表++，实际上只需要执行其第一个递归步骤！即使只有foldl结果中的第一项会强制要求所有调用++，这使得它非常昂贵（即使每个调用只需要一个递归步骤，都有O（n）调用）。
'（++）'的*结果*在两种情况下应该是相同的。这并不意味着计算的数量是相同的。 –
（大列表）++（小列表）慢于（小列表）++（大列表） – immibis
我看到你在这里待了很长时间，并且在不接受问题的情况下问了很多问题。如果答案对您有帮助，请考虑[接受]（https：// stackoverflow。com/help/accepted-answer）它。请花2分钟做一个[旅游]（https://stackoverflow.com/tour）了解这个网站的工作原理 –