为有限列表使用 foldl' 实现 concatMap 的性能提升？

Question

我读自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)

---

跟进问题

concatMap 在时间和内存方面都胜过我的 concatMap'。我想知道我在 concatMap' 实现中犯了错误。

因此，我怀疑那些描述foldl'优点的文章。

1. concatMap 是不是有什么黑魔法让它如此高效？

2. foldl' 对于长的有限列表更有效是真的吗？

3. 使用带有长有限列表的 foldr 是否真的会建立一个长的未缩减链并影响性能？

Answer 1

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是否能够在 评估 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' 将改为在恒定空间中工作。

Is it true that using foldr with long finite lists will build up a long unreduced chain and impact the performance?

并不总是。这在很大程度上取决于调用者如何使用输出。

作为一个经验法则，如果输出是“原子的”，意味着输出消费者不能只观察到它的一部分(例如 Bool, Int, ...)那么最好是使用 foldl'。如果输出是由许多独立值(列表、树等)“组成”的，如果 f 可以逐步生成其输出，则 foldr 可能是更好的选择-step，以“流式”方式。