Gav*_*vin 2 performance haskell functional-programming fold
我从读FOLDR与foldl与foldl"那foldl'是因为严格财产的长期有限名单更有效.我知道它不适合无限列表.
因此,我只限制长期有限列表的比较.
concatMap使用foldr,实现懒惰.但是,根据文章,使用长有限列表将构建一个长的未减少的链.
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
concatMap f xs = build (\c n -> foldr (\x b -> foldr c b (f x)) n xs)
因此,我提出了以下使用的实现foldl'.
concatMap' :: Foldable t => (a -> [b]) -> t a -> [b]
concatMap' f = reverse . foldl' (\acc x -> f x ++ acc) []
我已经构建了以下两个函数来测试性能.
lastA = last . concatMap (: []) $ [1..10000]
lastB = last . concatMap' (: []) $ [1..10000]
但是,我对结果感到震惊.
lastA:
(0.23 secs, 184,071,944 bytes)
(0.24 secs, 184,074,376 bytes)
(0.24 secs, 184,071,048 bytes)
(0.24 secs, 184,074,376 bytes)
(0.25 secs, 184,075,216 bytes)
lastB:
(0.81 secs, 224,075,080 bytes)
(0.76 secs, 224,074,504 bytes)
(0.78 secs, 224,072,888 bytes)
(0.84 secs, 224,073,736 bytes)
(0.79 secs, 224,074,064 bytes)
concatMapconcatMap'在时间和记忆上都胜过我.我想知道我在concatMap'实施中犯了错误.
因此,我怀疑陈述善良的文章foldl'.
是否有任何黑魔法concatMap使其如此高效？
foldl'对长期有限列表更有效是真的吗？
使用foldr长有限列表是否会构建一个长的未减少的链并影响性能？
在concatMap中是否有任何黑魔法使其如此高效？
不,不是真的.
foldl'对长期有限列表更有效是真的吗？
不总是.这取决于折叠功能.
关键是,foldl并且foldl'必须在生成输出之前扫描整个输入列表.相反,foldr并不总是如此.
作为极端情况,请考虑
foldr (\x xs -> x) 0 [10..10000000]
10立即评估- 仅评估列表的第一个元素.减少就像是
foldr (\x xs -> x) 0 [10..10000000]
= foldr (\x xs -> x) 0 (10 : [11..10000000])
= (\x xs -> x) 10 (foldr (\x xs -> x) 0 [11..10000000])
= (\xs -> 10) (foldr (\x xs -> x) 0 [11..10000000])
= 10
并且由于懒惰而没有评估递归调用.
通常,在计算时foldr f a xs,重要的是检查在评估之前是否f y ys能够构造输出的一部分.例如ys
foldr f [] xs
where f y ys = (2*y) : ys
产生一个列表单元格_ : _评估之前2*y和ys.这使它成为一个很好的候选人foldr.
我们可以再次定义
map f xs = foldr (\y ys -> f y : ys) [] xs
运行得很好.它消耗一个元素xs并输出第一个输出单元格.然后它消耗下一个元素,输出下一个元素,依此类推.foldl'在处理整个列表之前,使用不会输出任何内容,从而使代码效率非常低.
相反,如果我们写的话
sum xs = foldr (\y ys -> y+ys) 0 xs
然后我们在xs消耗第一个元素后不输出任何内容.我们建立了一长串的thunk,浪费了大量的内存.foldl'相反,它会在恒定的空间中工作.
使用
foldr长有限列表是否会构建一个长的未减少的链并影响性能？
不总是.它在很大程度上取决于调用者如何消耗输出.
作为一个拇指规则,如果输出是"原子的",意味着输出消费者不能只观察它的一部分(例如Bool, Int, ...),那么最好使用它foldl'.如果输出由许多独立值(列表,树,......)"组合",则可能foldr是更好的选择,如果f能够以"流"方式逐步产生其输出.