撰寫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返回類型時出現錯誤類型。事實證明，這種情況對於調試更有用，因爲它包含爲什麼類型檢查失敗的提示。