情况是这样的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
因为,在真正病态的情况下,后者建议两个单独的递归。然而,由于懒惰,不太可能执行两次递归,那么会出现什么情况呢?
真正的原因是有更复杂的聚变定律可供编译器使用,例如组合两个顺序的编译器foldr
s 或 定义之间的相互作用foldr
and unfoldr
。这些使用起来有点挑剔,因为它们依赖于能够查看代码片段的表面语法并检测可能的简化。 Alot制定持续发射聚变定律的工作量很大。
但我们可以做的一件事是鼓励人们使用预先应用优化定律的高阶组合器。自从foldr (++) [] . map f
永远不会比foldr ((++) . f) []
我们可以走捷径,预先应用普遍法则简化。这将提高融合法则在其他地方启动的可能性,以最好地优化列表生成管道。
[0] 这条法律为何有效?粗略地说,普遍规律是foldr
指出如果你有任何功能q
这样q [] = z
and q (a:as) = f a (q as)
然后q
must be and is foldr f z
. Since q = foldr g z . map f
可以证明有q [] = z
and q (a:as) = g (f a) (q as)
然后它must be像折叠一样foldr (g . f) z
就像我们想要的那样。