concatMap f xs和concat $ map f xs之间有什么区别？

Question

假设它们做的事情完全相同，concatMap f xs和concat $ map f xs。为什么我要选择其中一个？

我想这可能是一种优化。如果是这样，那么在GHC 7.8中是否仍然是这种情况呢？

- user1002430

---

可能是 concatMap 做什么？ 的重复问题。 - Konstantine Rybnikov

是的，它们在概念上是相同的，这可以通过简单的定义写出来证明 https://gist.github.com/k-bx/e2001663ec755aea4a42。然而，我认为 concatMap 被定义为与 concat . map f 不同的原因是为了融合优化，使其在线性空间中运行。 - Konstantine Rybnikov

@KonstantineRybnikov 这个问题的表述更好，答案更深入，可以学到更多东西，这就是为什么我把重复的部分放在了另一个方向上。 - AndrewC

Answer 1

正如你所怀疑的，concatMap f xs = concat (map f xs)是正确的。因此，为了保证正确性，你应该考虑它们是可以互换的。虽然我们可以检查它们的定义来学习更多信息。

concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []

concat :: [[a]] -> [a]
concat = foldr (++) []

特别地，这意味着 concat . map f 展开成了 foldr (++) [] . map f。现在使用所谓的“fold 的通用属性”，我们可以看到对于任何 (g, z, f)，如上面使用的选择 ((++), f, [])，都有 foldr g z . map f = foldr (g . f) z。这证明了我们想要的 concatMap f = concat . map f。

那么它们为什么要被不同地定义呢？因为 foldr ((++) . f) [] 总是比 foldr (++) [] . map f 更快，因为在一个非常病态的情况下，后者暗示着两个独立的递归。但由于惰性求值，很少会执行两个递归，那它到底怎么回事呢？

真正的原因是编译器有更复杂的 融合定律，例如将两个连续的 foldr 合并的定律，或者定义 foldr 与 unfoldr 之间的交互。这些定律有点棘手，因为它们依赖于能够查看代码片段的表面语法并检测可能的简化。需要大量的工作才能获得一致性的融合定律。

但我们可以做的一件事是鼓励人们使用预应用了优化定律的高阶组合子。因为 foldr (++) [] . map f 永远不会比 foldr ((++) . f) [] 快，所以我们可以采取捷径并预先应用通用定律的简化。这将提高融合定律在其他地方触发以最佳化列表生成流水线的可能性。

[0] 这个定律为什么有效？粗略地说，foldr 的通用定律规定，如果你有任何函数 q，使得 q [] = z 和 q (a:as) = f a (q as)，那么该 q 必须是 foldr f z。由于可以证明 q = foldr g z . map f 具有 q [] = z 和 q (a:as) = g (f a) (q as)，那么它必须是我们想要的像 foldr (g . f) z 的折叠。

- J. Abrahamson

---

谢谢。如果我要总结原因，那就是很难编写优化规则，让编译器可靠地应用它们，所以让我们通过一些手动优化来帮助编译器。 - user1002430

我不明白的是，为什么不制定一个规则，将 concat $ map f xs 转换为 concatMap f xs，这样就不必公开 concatMap，它可以保持作为仅用于优化的内部函数使用。 - letmaik

有一大堆类似的法律被谨慎地应用于GHC的基本代码库。你甚至可以使用RULES编译指示来编写自己的规则。棘手的问题是，这些规则在一般情况下非常难以应用，而且弄清楚如何正确应用它们是一门大师级的技艺(!)。一般而言，你还必须完全确定没有任何可能在这些规则的性能下改变的语义细节。如果它们要完全透明，那么等式推理的抽象绝对不能出现破裂，这需要进行深入审查。 - J. Abrahamson