foldl with(++)比foldr慢很多

Question

为什么foldl有时比foldr慢？我有一个列表"a"之类的

a = [[1],[2],[3]]

并希望使用fold将其更改为列表

foldr (++) [] a

它工作正常(时间复杂度为O(n)).但是,如果我使用foldl,它非常慢(时间复杂度为O(n ^ 2)).

foldl (++) [] a

如果foldl只是从左侧折叠输入列表,

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

和折叠是从右侧,

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

在两种情况下,计算次数(++)应该相同.为什么折叠这么慢？根据时间复杂度,foldl看起来好像扫描输入列表的次数是foldr的两倍.我用下面的电脑来计算时间

length $ fold (++) [] $ map (:[]) [1..N]   (fold is either foldl or foldr)

Answer 1

这是因为++工作原理.注意,它是由第一个参数的归纳定义的.

[]     ++ 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)的调用).