(************************************************************
   letrec.ml		Created      : Sat Jun 21 23:35:55 2003
  			Last modified: Sun Jun 22 13:32:09 2003
  Compile: ocamlopt.opt letrec.ml -o letrec #
  FTP Directory: sources/ocaml #
************************************************************)
(**
scheme では以下のプログラムは許容される。静的に型をつけないから。

(define fib-rec 
  (lambda (f n) 
    (if (or (= n 0) (= n 1))
	1
      (+ (f f (- n 1)) (f f (- n 2))))))
(fib-rec fib-rec 10)

  fib-recの型を考えてみよう。 引数の f の型は自分の型とおんなじ型の
関数と整数をとって整数を返す関数であるから

  \mu\alpha.(\alpha \rightarrow int \rightarrow int)

  という再帰型で表せる (\mu\alphaは \alpha をそれ以降の式全体で置き換える
ことを表している) が再帰型が許されていないので書けない。(型推論
の中の単一化 (unify) の仮定で、片方が型変数の場合、もう一方が型の
式の形でその式の中にその型変数が現れていたら、単一化に失敗する (occur check)

e.g.
  unify 'a 'a は ok
  unify ('a -> 'b -> 'c) 'a は前者の中に後者 'a が現れるのでエラー

# let fib_rec = fun f n -> if n = 0 || n = 1 then 1 else (f f (n-1)) + (f f (n-2));;
Characters 58-59:
  let fib_rec = fun f n -> if n = 0 || n = 1 then 1 else (f f (n-1)) + (f f (n-2));;

This expression has type 'a -> 'b -> 'c but is here used with type 'a

これは

let rec fib n = if n = 0 || n = 1 then 1 else (fib (n-1)) + (fib (n-2));;

に相当する。

  @author Takashi Masuyama <mamewo@dk9.so-net.ne.jp>

*)


let fib_rec = fun f n -> if n = 0 || n = 1 then 1 else (f f (n-1)) + (f f (n-2))