カリー化された高階関数の型

SOE の Exercise 5.2 は、部分適用済み高階関数の型を問う問題。

map map
foldl foldl
map foldl

公式サイトの Errata に foldl foldl は principal type がなかったごめんという訂正があったので実質二問。いずれにせよ、さらっと流せない難しい問題と感じた。

というわけで思考の過程を書きつづってみる。
map の型はこう:

map :: (a -> b) -> [a] -> [b]

だから、これの第一引数を与えると [a] -> [b] という型の高階関数になる。一方与えた引数を (a -> b) でマッチングすることで a と b の型が決まる。

map を与えた場合 a が (a -> b) に、 b が残りの [a] -> [b] にマッチするので:

map map :: [a -> b] -> [[a] -> [b]]

(引数として与える map の型を (a -> b) -> ([a] -> [b]) だと考える)

foldl を与えた場合、 a が (a -> b -> a)、 b が残りの a -> [b] -> a にマッチするから:

map foldl :: [a -> b -> a] -> [a -> [b] -> a]

(引数として与える foldl の型を (a -> b -> a) -> (a -> [b] -> a) だと考える)