2016/02/15

OCamlの無名関数は再帰を定義できない?

わたろーです.
プログラミングの基礎 (Computer Science Library)を読んでいます.
これはOCamlとデザインレシピでプログラミングの基礎を学ぶという内容なのですが,
名前のない関数という節で気になる文章がありました.
14.4 名前のない関数 p145

名前のない関数で定義できるのは再帰をしていない関数だけです.

OCamlラムダ計算を元にしていると思っていたので驚きました.
Yコンビネータ使って再帰出来ないのって思ったので試してみました.
Yコンビネータ計算機プログラムの構造と解釈 第2版p233 問題4.21に載っていたものを使います.

;;; SICP
;;; 階乗計算
(lambda (n)
  ((lambda (fact)
     (fact fact n))
   (lambda (ft k)
     (if (= k 1)
         1
         (* k (ft ft (- k 1)))))))

実行すると

gosh> ((lambda (n)
         ((lambda (fact)
            (fact fact n))
          (lambda (ft k)
            (if (= k 1)
                1
                (* k (ft ft (- k 1)))))))
       5)
120

 
これをOCamlで書いてみます.

# (fun n->
  (fun fact ->
    fact fact n)
    (fun ft k ->
      if k = 1
      then 1
      else k * (ft ft (k - 1)))) 5;;
            Characters 33-37:
      fact fact n)
           ^^^^
Error: This expression has type 'a -> 'b -> 'c
       but an expression was expected of type 'a
       The type variable 'a occurs inside 'a -> 'b -> 'c

エラーですね.
型が解決されていないのでしょうか.
ググッてみると -rectypesを使ってインタプリタを起動すれば出来るようです.

不動点演算子ふたたび - sumiiの日記

# (fun n->
    (fun fact ->
      fact fact n)
      (fun ft k ->
        if k = 1
        then 1
        else k * (ft ft (k - 1)))) 5;;

            - : int = 120

おお,動いた.
再帰型っていうのが必要になるわけなんですね.
まだまだわからないことだらけですが,型もおもしろそうです.
この辺探すのに行き着いたこのページのTaPLのまとめがすごくおもしろそうです.

mint.hateblo.jp

おもしろそう.読みたい.すごく読みたい. でもまだ自分には厳しそう.

その前にプログラミング言語の基礎概念 (ライブラリ情報学コア・テキスト)を読みたい.
しかしその時間を作れるか.
そろそろお仕事探しのために動かないといけないかもって思ってきています.
勉強だけしていたい.


© 2022 wat-aro