concatMap f xs和concat $ map f xs之间的区别？

Question

据推测,他们完全一样,concatMap f xs并且concat $ map f xs.为什么我会选择一个而不是另一个？

我想这可能是一个优化.如果是这样,GHC 7.8仍然如此吗？

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",我们可以看到,foldr g z . map f = foldr (g . f) z对于任何(g,z,f),如选择((++),f,[])我们上面使用.这证明了concatMap f = concat . map f我们想要的.[0]

那他们为什么定义不同呢？因为foldr ((++) . f) []总是比foldr (++) [] . map f以前更快,在真正的病态情况下,后者建议两个单独的递归.由于懒惰,不太可能执行两次递归,那么是什么给出了？

真正的原因是编译器可以使用更复杂的融合法,例如组合两个序列foldrs或定义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像我们想要的那样折叠.