编写concat和map来获取concatMap:为什么f？

Question

这是我在Haskell的第一次探索,所以请原谅我是否应该是显而易见的.

我整个下午一直在玩Haskell ,使用我自己的列表类型(典型的缺点)在HaskellWiki上查阅99个问题的教程.我继续添加"明显"的功能,并且我尽可能地使它们尽可能简洁(尽可能使用无点表示法)

第12个问题是关于解码游程编码列表,即:

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

我考虑使用map解码每个元素,然后concat结果(感谢谷歌),最后记得我concatMap在读数中看到过类似的东西,GHCi很快证实:

> :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.事实证明,这种情况对调试更有用,因为它包含一个提示,为什么类型检查失败.