performance - Haskell - foldl' 在 foldr 和性能问题方面

Question

学习期间fold深入与A tutorial on the universality and expressiveness of 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] 这样的表达式。可以优化为从不分配 (:)构造函数。我们都知道绝对最快的垃圾收集是在没有垃圾要收集的时候。

见 http://www.joachim-breitner.de/publications/CallArity-TFP.pdf有关 GHC 7.10 中新优化的信息，以及为什么需要它。