concatMap f xs和concat $ map f xs之间的区别？ [英] Difference between concatMap f xs and concat $ map f xs?

问题描述

推测它们完全一样， concatMap f xs 和 concat $ map f xs 。为什么我会选择另一个？

我想它可能是一个优化。如果是这样，GHC 7.8仍然是这样的情况吗？

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（++）[]。地图f 。现在使用一种称为通用属性 fold ，我们可以看到 foldr gz。对于任何（ g ， z ），映射f = foldr（g。f）z ， （++）， f f c>， [] ）。这表明 concatMap f = concat。 map f 就像我们想要的那样。[0]

那么为什么它们的定义不同呢？因为 foldr（（++）。f）[] 总是比 foldr（++）[]更快。 map f ，因为在一个真正的病例中，后者提出了两个单独的递归。由于懒惰，不可能有两次递归会被执行，所以给出了什么？

真正的原因是存在更复杂的融合律可用于编译器，例如那些将两个顺序 foldr s组合或定义 foldr 和 unfoldr 。由于他们依赖于能够查看代码片段的表面语法并检测可能的简化，因此这些使用起来都很挑剔。很多工作都是为了获得持续的射频融合法。但是我们可以做的一件事就是鼓励人们使用更高阶的combinator来优化法律预先适用。由于 foldr（++）[]。 map f 永远不会比 foldr（（++）。f）[] 更快，我们可以采取快捷方式并预先应用普遍法律的简化。这将改善融合法在其他地方开火的可能性，以最佳地优化清单生产管道。

[0]为什么此法律有效？粗略地说， foldr 的通用定律表明，如果您有任何函数 q ，例如 q [] = z 和 q（a：as）= fa（q as）那么 q 必须是，是 foldr fz 。由于 q = foldr g z。 （a：as）= g（fa）可以显示出映射f q [] = z 和 （q as），那么它必须像我们想要的那样像 foldr（g。f）z 那样折叠。 / p>

Presumably they do exactly the same thing, concatMap f xs and concat $ map f xs. Why would I choose one over another?

I imagine it may be an optimization. If so, is this still the case with GHC 7.8?

解决方案

It is the case that concatMap f xs = concat (map f xs) as you suspect. Thus, for correctness purposes you should consider them interchangeable. We can examine their definitions to learn a little more, though.

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

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

In particular, this means that concat . map f expands to foldr (++) [] . map f. Now using a thing known as the "universal property of fold" we can see that foldr g z . map f = foldr (g . f) z for any (g, z, f) such as the choice ((++), f, []) we use above. This demonstrates that concatMap f = concat . map f like we want.[0]

So why are they defined differently? Because foldr ((++) . f) [] is always going to be faster than foldr (++) [] . map f since, in a really pathological case, the latter suggests two separate recursions. Due to laziness, it's unlikely that two recursions would ever be performed, though, so what gives?

The real reason is that there are more complex fusion laws available to the compiler such as those which combine two sequential foldrs or which define interactions between foldr and unfoldr. These are kind of finicky to use as they depend upon being able to look at the surface syntax of a fragment of code and detect possible simplifications. A lot of work goes into getting consistently firing fusion laws.

But one thing we can do is encourage people to use higher order combinators with optimization laws pre-applied. Since foldr (++) [] . map f is never going to be faster than foldr ((++) . f) [] we can take a shortcut and pre-apply the universal law simplification. This will improve the likelihood of fusion laws firing elsewhere to best optimize a list production pipeline.

[0] Why does this law work? Roughly, the universal law of foldr states that if you have any function q such that q [] = z and q (a:as) = f a (q as) then that q must be and is foldr f z. Since q = foldr g z . map f can be shown to have q [] = z and q (a:as) = g (f a) (q as) then it must be a fold like foldr (g . f) z like we want.

这篇关于concatMap f xs和concat $ map f xs之间的区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！