練習問題 1.6.3

以下の関数
strange
および
stranger
に対して多相型を割り当てられるか.


strange  f g = g (f g)
stranger f   = f f

strange
の型


  • strange
    の定義より
    f
    g
    は関数である
  • f :: a -> b
    g :: c -> d
    を仮定する
  • 直前の仮定より
    strange :: (a -> b) -> (c -> d) -> d
    である
  • f g
    がきちんと定義された型をもつならa = c -> d
  • したがって,
    f :: (c -> d) -> b
    g :: c -> d
    f g :: b
    strange :: ((c -> d) -> b) -> (c -> d) -> d
    である.
  • g (f g)
    がきちんと定義された型をもつなら,
    c = b
    である.
  • したがって,
    f :: (c -> d) -> c
    g :: c -> d
    strange :: ((c -> d) -> c) -> (c -> d) -> d
    である.
stranger
の型


  • f
    は型
    f :: a -> b
    とする
  • stranger :: (a -> b) -> c
    である
  • f f
    がきちんと定義された型をもつなら
    c = b
    かつ
    a = a -> b
    である
  • しかし,
    a = a -> b
    はきちんと型付けできない
strange ::  ((a -> b) -> a) -> (a -> b) -> b
strange f g = g (f g)