Haskell - foldl'在折叠和性能问题方面

Question

fold在深入研究折叠的普遍性和表现力的教程时, 我发现了一个惊人的foldl使用定义foldr:

-- I used one lambda function inside another only to improve reading
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z xs = foldr (\x g -> (\a -> g (f a x))) id xs z

在了解了正在发生的事情后,我想我甚foldr至可以用来定义foldl',这将是这样的:

foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' f z xs = foldr (\x g -> (\a -> let z' = a `f` x in z' `seq` g z')) id xs z

这与此平行:

foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' f z (x:xs) = let z' = z `f` x 
                    in seq z' $ foldl' f z' xs 
foldl' _ z _     = z

在这样的简单情况下,它们似乎都在恒定的空间(不创建thunk)中运行:

*Main> foldl' (+) 0 [1..1000000]
500000500000

我可以foldl'在性能方面考虑两种等价的定义吗？

Answer 1

在GHC 7.10+中,foldl并且foldl'都是根据foldr.它们之前没有的原因是GHC没有很好地优化foldr定义以参与foldr/build融合.但GHC 7.10引入了一项新的优化,专门用于foldr/build在使用foldl'或foldl'定义这种方式时使融合成功.

这里的最大胜利是,表达式foldl' (+) 0 [1..10]可以优化到永远不会分配(:)构造函数.我们都知道,绝对最快的垃圾收集是在没有垃圾收集的时候.

有关GHC 7.10中新优化的信息,以及为什么有必要,请参见http://www.joachim-breitner.de/publications/CallArity-TFP.pdf.