soutaroのHaskellにっき

ひさびさ。

■ Haskellの型推論は完全？

MLの型推論は完全である。

エラーなく実行できるプログラムは、必ず型推論できる

というのが「型推論が完全」の意味。

OCamlの型推論も完全。

Haskellはどうなんだろ？

Polymorphic Recursionは完全じゃなかったはず(型推論が止まらなくなることがある)なので、Haskellは完全じゃないのかな。

■ Polymorphic Recursionの例

data Seq a = Nil | Cons a (Seq (a,a))
size :: Seq a -> Int
size Nil = 0
size (Cons a b) = 1 + 2 * size b

ghciに食わせてみる。

  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4.2, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Compiling Main             ( pr.hs, interpreted )
Ok, modules loaded: Main.

大丈夫。

OCamlだと…

        Objective Caml version 3.09.2

# type 'a seq = Nil | Cons of 'a * ('a * 'a) seq;;                                                                                       
type 'a seq = Nil | Cons of 'a * ('a * 'a) seq
# let rec size = function                                                                                                                
    Nil -> 0                                                                                                                             
  | Cons(a,b) -> 1 + 2 * size b;;                                                                                                        
This expression has type ('a * 'a) seq but is here used with type 'a seq

確かにダメ。

ふむふむ。