Skip to content

Instantly share code, notes, and snippets.

@honda0510
Created January 14, 2013 03:18
Show Gist options
  • Save honda0510/4527544 to your computer and use it in GitHub Desktop.
Save honda0510/4527544 to your computer and use it in GitHub Desktop.
reverse' はコンパイルエラーにならないのに reverse'' はコンパイルエラーになるのはなぜだろう
reverse' :: [a] -> [a]
reverse' = foldl (flip (:)) []
reverse'' :: [a] -> [a]
reverse'' = foldl (:) []
@haiiro-shimeji
Copy link

文字で説明すると。。

:t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a

なので、foldlに与えた第2引数 []の型 と、「第1引数に与えた関数の第1引数、戻り値の型」が合ってないといけません。

:t (:)
(:) :: a -> [a] -> [a]

なので、与える関数の第1引数と戻り値を合わせるために

:t (flip (:))
(flip (:)) :: [a] -> a -> [a]

とする、というところでしょうか。。

@haiiro-shimeji
Copy link

ghciのエラーメッセージを訳すとこんな感じですかね(適当

Couldn't match type `a' with `[a]'
  `a' is a rigid type variable bound by
      the type signature for reverse'' :: [a] -> [a]
      at ../test/hs/reverse.hs:5:1
Expected type: [a] -> a -> [a]
  Actual type: [a] -> [[a]] -> [[a]]
In the first argument of `foldl', namely `(:)'
In the expression: foldl (:) []

Couldn't match type `a' with `[[a]]'
  `a' is a rigid type variable bound by
      the type signature for reverse'' :: [a] -> [a]
      at ../test/hs/reverse.hs:5:1
Expected type: [a] -> a -> [a]
  Actual type: [a] -> [[a]] -> [[a]]
In the first argument of `foldl', namely `(:)'
In the expression: foldl (:) []

なんてこった。型aが欲しいところで型[a]が来ちゃったよ。
fold (:) [] の (:) だけどさ、[a]型 と a型 を与えたら[a]型が返ってきて欲しいじゃん? (Excepted Type)
でも、この(:)って、[a]型を与えてみたら次に[[a]]型を受け取って [[a]]を返すやつじゃないの? (Actual Type)
あ、aってのは型引数(a rigid type variable)ね。関数宣言でそう書いてるでしょ。

-- 追記
2回同じようなメッセージを出してますけど、”Could't match type”の部分だけが違いますね。。ここは何を言わんとしてるのかよくわからないです。2パターンで推論してみたけどダメだった、ってことなのかな。

@honda0510
Copy link
Author

今の僕の解釈

foldlとしては

(a -> b -> a) -> a

こういう型で渡さなければいけないのに、

(a -> [a] -> [a]) -> [a]

こういう型で渡そうとしていたってことですね。
aと[a]の型不一致が2つあるから、エラーメッセージも2つあったんですね。

@haiiro-shimeji
Copy link

あーなるほど、そういうことなのかな

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment