手続き的なアルゴリズム

リストの長さを求めるプログラムは，次のようにして記述できる．

int list_length(list *l) {
  list l2 = *l;      /* 1 /*
  int len=0;         /* 2 /*

  while ! is_empty(l2) {
    len++;
    remove_top(l2);
  }

  return len;
}

これをOCamlでは，どうやって書いたらいいだろうか？迷うのは，1と2だと思う．僕は困った．

let list_length l = 
 let l2 = ref l;
 let len = ref 0;
 ...

と，することはできない．「;」で繋げて，逐次実行ができるのは，unitを返す関数だけだから．

答えは，これ．

let list_length l =
 let l = ref l in       (* 1 *)
 let res = ref 0 in     (* 2 *)
 while !l <> [] do
  incr res;
  l := List.tl !l
 done;
 !res;;

上のプログラムは，InriaのProgramming guide linesに載っていた，悪い例である*1．

ポイントは，1と2で，let...inを利用することによって，最初に示したCっぽい手続き的なプログラムの1,2と素直に対応が取れている．見方を変えれば，let...inを利用することによって，OCamlではできない代入文のシーケンシャルな実行が可能になっている．

let...inを使えば，スコープの外側から内側へ順に評価されることが保証されているため，逐次的にlet文を実行することができる．命令的な言語の変数宣言・変数への代入と似たセマンティクスのプログラムを，記述することができる．

*1:普通，再帰使って書くし，そもそも自分で書いてはいけない．List.lengthを使おう．