为有限列表使用 foldl' 实现 concatMap 的性能提升？
Performance gain implementing concatMap with foldl' for finite list?
我从 Foldr Foldl Foldl' 了解到 foldl' 由于严格性 属性 对于长的有限列表更有效。我知道它不适合无限列表。
因此，我只对长的有限列表进行比较。
concatMap
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)
后续问题
concatMap 在时间和记忆力上都胜过我的 concatMap'。我想知道我在 concatMap' 实施中犯了错误。
因此，我怀疑文章是否能说明 foldl' 的优点。
concatMap是不是有什么黑魔法让它如此高效？
foldl'对于长的有限列表更有效是真的吗？
使用 foldr 长有限列表是否会建立一个长的未缩减链并影响性能？
Are there any black magic in concatMap to make it so efficient?
不，不是真的。
Is it true that foldl' is more efficient for long finite list?
不总是。这取决于折叠功能。
重点是，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是否能够在评估[=]之前构造输出的一部分 22=]。例如
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' 会以常量 space.
工作
Is it true that using foldr with long finite lists will build up a long unreduced chain and impact the performance?
不总是。这在很大程度上取决于调用者如何使用输出。
作为一个经验法则，如果输出是"atomic"，意味着输出消费者不能只观察到它的一部分（例如Bool, Int, ...）那么最好使用foldl'.如果输出是 "composed" 许多独立值（列表，树，...）可能 foldr 是更好的选择，如果 f 可以逐步产生它的输出，在"streaming" 时尚。
我从 Foldr Foldl Foldl' 了解到 foldl' 由于严格性 属性 对于长的有限列表更有效。我知道它不适合无限列表。
因此，我只对长的有限列表进行比较。
concatMap
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)
后续问题
concatMap 在时间和记忆力上都胜过我的 concatMap'。我想知道我在 concatMap' 实施中犯了错误。
因此，我怀疑文章是否能说明 foldl' 的优点。
concatMap是不是有什么黑魔法让它如此高效？foldl'对于长的有限列表更有效是真的吗？使用
foldr长有限列表是否会建立一个长的未缩减链并影响性能？
Are there any black magic in concatMap to make it so efficient?
不，不是真的。
Is it true that
foldl'is more efficient for long finite list?
不总是。这取决于折叠功能。
重点是，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是否能够在评估[=]之前构造输出的一部分 22=]。例如
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' 会以常量 space.
Is it true that using
foldrwith long finite lists will build up a long unreduced chain and impact the performance?
不总是。这在很大程度上取决于调用者如何使用输出。
作为一个经验法则，如果输出是"atomic"，意味着输出消费者不能只观察到它的一部分（例如Bool, Int, ...）那么最好使用foldl'.如果输出是 "composed" 许多独立值（列表，树，...）可能 foldr 是更好的选择，如果 f 可以逐步产生它的输出，在"streaming" 时尚。