foldl是尾递归的,那么foldr如何比foldl运行得更快呢？

Question

我想测试foldl vs foldr.从我所看到的,你应该使用foldl over foldr,因为尾部递归优化.

这是有道理的.但是,运行此测试后,我很困惑:

foldr(使用时间命令时需要0.057秒):

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

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

foldl(使用time命令时需要0.089s):

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

很明显,这个例子很简单,但我很困惑为什么foldr击败foldl.这不应该是foldl获胜的明显案例吗？

Answer 1

欢迎来到懒惰评价的世界.

当您从严格评估的角度考虑它时,foldl看起来"好"而且foldr看起来"糟糕",因为foldl是尾递归的,但是foldr必须在堆栈中构建一个塔,以便它可以先处理最后一个项目.

但是,懒惰的评估会转变表格.以地图函数的定义为例:

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)

因为f定义的map可以仅使用第一个参数返回结果列表的第一项,所以折叠可以在恒定空间中懒惰地操作.

现在,懒惰的评估会咬回来.例如,尝试运行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.

幸运的是,Data.List中有一个特殊的函数,它被foldl'严格操作. foldl' (+) 0 [1..1000000]不会堆叠溢出.(注:我想更换foldl用foldl'在您的测试,但它实际上使它运行速度较慢.)

Answer 2

编辑:再次看到这个问题,我认为目前所有的解释都有些不足,所以我写了更长的解释.

所不同的是如何foldl和foldr应用他们的降噪功能.看一下这个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,最好的折叠函数是因为遍历方向对于列表的惰性评估是最佳的.它也是唯一能够处理无限列表的人.foldl'在某些情况下,额外的严格性可以使它更快,但这取决于你将如何使用该结构以及它是多么懒惰.

Answer 3

我认为没有人真正说过这个问题的真正答案,除非我遗漏了一些东西(这可能是真的,并且可以通过downvotes欢迎).

我认为在这种情况下最大的不同之处在于foldr构建如下列表:

[0] ++([1] ++([2] ++(... ++ [1000000])))

而foldl建立这样的列表:

((([0] ++ [1])++ [2])++ ...)++ [999888])++ [999999])++ [1000000]

微妙的区别,但请注意在foldr版本中++始终只有一个列表元素作为其左参数.对于该foldl版本,++左侧参数中最多有999999个元素(平均大约500000个),但右侧参数中只有一个元素.

但是,++需要时间与左参数的大小成比例,因为它必须查看整个左参数列表到最后,然后将最后一个元素重新指向右参数的第一个元素(充其量,也许它实际上需要做一份).正确的参数列表没有变化,所以它有多大并不重要.

这就是foldl版本慢得多的原因.在我看来,这与懒惰毫无关系.

Answer 4

问题是尾递归优化是内存优化,而不是执行时优化!

尾递归优化避免了记住每个递归调用的值的需要.

因此,foldl实际上是"好"而折叠是"坏".

例如,考虑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,它到达基本情况并返回作为第二个参数(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为每个调用记住一个整数,并在每次调用中执行添加.

重要的是要记住,foldr和foldl并不总是等价的.例如,尝试在拥抱中计算这个表达式:

foldr (&&) True (False:(repeat True))

foldl (&&) True (False:(repeat True))

foldr和foldl仅在此处描述的某些条件下是等效的

(对不起,我的英语不好)