haskell - 带(++)的foldl比foldr慢很多

Question

为什么有时foldl 比foldr 慢？我有一个列表“a”的列表，例如

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)

Answer 1

这是因为 ++ 的工作原理。请注意，它是通过第一个参数的归纳来定义的。

[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

递归调用的次数仅取决于长度xs。

因此，在xs++ ys中，使用较小的xs和较大的ys比其他方式更方便周围。

请注意，向右折叠可以实现此目的:

[1] ++ ([2] ++ ([3] ++ ...

我们在 ++ 左侧只有短(O(1)-长度)列表，使得折叠成本为 O(n)。

相反，向左折叠是不好的:

((([] ++ [1]) ++ [2]) ++ [3]) ++ ...

左边的参数变得越来越大。因此，我们在这里得到 O(n^2) 复杂度。

考虑到输出列表的需求方式，可以使该参数更加精确。人们可以观察到 foldr 以“流式”方式产生结果，其中要求较高，例如第一个输出列表单元仅强制输入的一小部分——仅需要执行第一个 ++，并且实际上只需要其第一个递归步骤!相反，即使只要求 foldl 结果中的第一项，也会强制所有 ++ 调用，从而使其非常昂贵(即使每个调用仅需要一个递归步骤，有 O(n) 次调用)。