日: 2007年12月16日

プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~ p.57より。

if式を OCaml の関数で表現することはできません。次の関数はそれを試みたものですが，fact 4 の計算の評価ステップを考え，なぜうまく計算できないのか説明しなさい。

# let cond (b, e1, e2) : int = if b then e1 else e2;;
val cond : bool * int * int -> int = <fun>
# let rec fact n = cond ( (n = 1), 1, n * fact (n-1) );;
val fact : int -> int = <fun>
# fact 4;;
Stack overflow during evaluation (looping recursion?).

式の評価戦略の説明のところ（pp.46-48）ではわかりにくいけど，要するに OCaml は関数の引数を先に評価する。fact 4 を評価することは cond ( (4=1), 1, 4 * fact (4-1) )を評価するってことで，fact 4 の値を確定する前に fact (4-1)，つまり fact 3 の値を確定しなけりゃならない。同様に fact 3 の前に fact 2 を，fact 2 の前に fact 1 を，fact 1 の前に fact 0 を，fact 0 の前に fact (-1) を･･････(以下略）となって，いつまでたっても値を確定できない。結局スタックオーバフローになった，というわけだ。

ここら辺は Haskell とは違うところだな。遅延評価する Haskell では何の問題も無く動く。

Prelude> let cond (b, e1, e2) = if b then e1 else e2
Prelude> let fact n = cond ((n == 1), 1, n * fact (n - 1))
Prelude> fact 4
24

本文中で与えられた再帰的な定義で n個の中からm個を選ぶ場合の数 を求める関数 comb を定義せよ，という問題。再帰的な定義は本文（p.51）をみること（書くのが面倒なので)。

# let rec comb n m =
if m = 0 then 1
else if n = m then 1
else comb (n-1) m + comb (n-1) (m-1)
;;
val comb : int -> int -> int = <fun>
# comb 5 3;;
# comb 2 1;;
- : int = 2

末尾再帰的関数を使ってフィボナッチ数を計算する iterfib

# let iterfib n =
let rec fibn (x, y) i =
if i = n then y
else fibn (y, x + y) (i+1)
in
fibn (0, 1) 1
;;
val iterfib : int -> int = <fun>
# iterfib 1;;
- : int = 1
# iterfib 2;;
- : int = 1
# iterfib 3;;
- : int = 2
# iterfib 4;;
- : int = 3
# iterfib 5;;
- : int = 5
# iterfib 6;;
- : int = 8

ちゃんと末尾再起になってるよね？