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を使ってインタプリタを起動すれば出来るようです.
# (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のまとめがすごくおもしろそうです.
おもしろそう.読みたい.すごく読みたい. でもまだ自分には厳しそう.
その前にプログラミング言語の基礎概念 (ライブラリ情報学コア・テキスト)を読みたい.
しかしその時間を作れるか.
そろそろお仕事探しのために動かないといけないかもって思ってきています.
勉強だけしていたい.