撰写concat和map来获取concatMap：为什么f？

Question

这些是我在Haskell的第一次探索，所以请原谅我，如果它应该是明显的。

我一直在和哈斯克尔一起玩，使用我自己的列表类型（典型的缺点）筛选教程99 questions on HaskellWiki。我继续添加了“显而易见”的功能，并且尽力使它们尽可能简洁（尽可能使用免注释符号）

第12个问题是关于解码运行长度编码列表，那就是：

> decode [Multiple 5 'a', Single 'b', Multiple 2 'c'] 
"aaaaabcc" 

我想过使用map每个元素进行解码，然后concat结果（感谢谷歌在此），终于记起我曾见过类似的东西在我的读数，这GHCI很快证实concatMap ：

> :t map 
map :: (a -> b) -> [a] -> [b] 
> :t concat 
concat :: [[a]] -> [a] 
> :t concatMap 
concatMap :: (a -> [b]) -> [a] -> [b] 

它看起来像这将是显而易见的重新实现concatMap：

concatMap :: (a -> [b]) -> [a] -> [b] 
concatMap = concat . map 

除GHCI颇为抱怨：

List.hs:110:15: 
    Couldn't match expected type `[a] -> [b]' 
       with actual type `[a0]' 
    Expected type: [[a0]] -> [a] -> [b] 
     Actual type: [[a0]] -> [[a0]] 
    In the first argument of `(.)', namely `concat' 
    In the expression: concat . map 

我想不出来，所以我抬起头，在网络上，和Prelude中引用的定义其实是：

concatMap f = concat . map f 

我不太明白为什么这个f是必须的，因为它的类型显然是a -> [b]按照签名规定...

那么为什么f这里需要？

Answer 1

与标准的定义出发，

concat . map f 
≡ concat . (map f) 
≡ \x -> concat ((map f) x) 

你的第一个定义，为您提供：

(concat . map) f 
≡ (\x -> concat (map x)) f 
≡ concat (map f) 

不类型检查，因为(map f) :: [a] -> [b]，而concat需要[[a]]，列出清单。

请注意问题中显示的特定错误消息没有描述上述类型检查失败。给定的消息来自声明返回类型concatMap为[a] -> [b]，这与[a0]不一致，返回类型为concat。如果你省略类型签名，响应是：

 
    Couldn't match type ‘[a1] -> [b]’ with ‘[[a]]’ 
    Expected type: (a1 -> b) -> [[a]] 
     Actual type: (a1 -> b) -> [a1] -> [b] 
    Relevant bindings include 
     concatMap :: (a1 -> b) -> [a] (bound at :49:5) 
    Probable cause: ‘map’ is applied to too few arguments 
    In the second argument of ‘(.)’, namely ‘map’ 
    In the expression: concat . map 

这里，协调的map与参数类型的concat返回类型时出现错误类型。事实证明，这种情况对于调试更有用，因为它包含为什么类型检查失败的提示。