编写concat和map来获取concatMap：为什么f？ [英] Composing concat and map to get concatMap: why the f?
问题描述
我一直在和Haskell一起玩，在教程关于HaskellWiki的99个问题，使用我自己的列表类型（典型的缺点）。我继续添加了显而易见的功能，并且尽力使它们尽可能简洁（尽可能使用免提符号）。
第12问题在于解码运行长度编码列表，即：
>解码[Multiple 5'a'，Single'b'，Multiple 2'c']
aaaaabcc
我想过使用 map 来解码每个元素，然后 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]） - > code>： [a] - > [b]
concatMap = concat。 map
除GHCi相当抱怨：
List.hs：110：15：
无法匹配预期的类型`[a] - > [b]'
，实际类型为'[a0]'
预期类型：[[a0]] - > [a] - > [b]
实际类型：[[a0]] - > [[a0]]
在`（。）'的第一个参数中，即`concat'
在表达式：concat中。 map
我找不到它，所以我查了一下网页， Prelude实际上是：
concatMap f = concat。 map f
我不太明白为什么这个f是必须的，因为它的类型显然是 a - > [b] ，如签名中所指定的那样...
那么为什么 f 需要在这里吗？
从标准定义开始，
concat。地图f
≡concat。 （图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 。如果您放弃了类型签名，则回复为：
无法匹配类型'[a1] - > [b ''['a]]'
预期类型：（a1 - > b） - > [[a]]
实际类型：（a1 - > b） - > [a1] - > [b]
相关绑定包括
concatMap ::（a1 - > b） - > [a]（绑定在：49：5）
可能的原因：'map'也适用几个参数
在'（。）'的第二个参数中，即'map'
在表达式：concat中。 map
这里，在协调 map ，参数类型为 concat 。事实证明，这种情况对于调试更有用，因为它包含提示类型检查失败的提示。
Those are my first explorations in Haskell, so pardon me if it should be obvious.
I have been playing all afternoon with Haskell, sifting through the tutorial 99 questions on HaskellWiki, using my own list type (typical Cons). I've added "obvious" functions as I went on, and I have tried to make them as concise as possible (employing point-free notation whenever possible)
The 12th problem is about decoding a run-length encoded list, that is:
> decode [Multiple 5 'a', Single 'b', Multiple 2 'c']
"aaaaabcc"
And I thought about using map to decode each element, then concat the result (thanks Google on this), and finally remembered that I had seen something like concatMap in my readings, which GHCi quickly confirmed:
> :t map
map :: (a -> b) -> [a] -> [b]
> :t concat
concat :: [[a]] -> [a]
> :t concatMap
concatMap :: (a -> [b]) -> [a] -> [b]
It looked like it would be obvious to reimplement concatMap:
concatMap :: (a -> [b]) -> [a] -> [b]
concatMap = concat . map
Except that GHCi quite complains:
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
I could not figure it out, so I looked up on the web, and the definition referenced in Prelude is actually:
concatMap f = concat . map f
And I don't quite understand why this f is necessary, since it's type is obviously a -> [b] as specified by the signature...
So why is f necessary here ?
Starting with the standard definition,
concat . map f
≡ concat . (map f)
≡ \x -> concat ((map f) x)
Your first definition gives you:
(concat . map) f
≡ (\x -> concat (map x)) f
≡ concat (map f)
which doesn't type check because (map f) :: [a] -> [b], while concat takes [[a]], a list of lists.
Note the particular error message shown in the question doesn't describe the above type-check failure. The given message arises from declaring the return type concatMap as [a] -> [b], which isn't reconcilable with [a0], the return type of concat. If you leave off the type signature, the response is:
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
Here, the type error occurs when reconciling the return type of map with the argument type of concat. It turns out this case is more useful for debugging as it contains a hint why the type check failed.
这篇关于编写concat和map来获取concatMap：为什么f？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
