OCaml一人勉強会 - 遅延ストリーム

前々回に遅延評価の例として無限リストを出しましたが、今回は実際にフィボナッチ数列のリストを実装してみましょう。
まずは lazy を使わずに実装してみましょう。
始めに、無限リストを表すデータ構造を考えます。当然そのままリストを使うわけにはいきません。正解は「先頭の値」と「残りのリストを返す関数」のペアです。これにはタプルが適しています。

# type 'a seq = Cons of 'a * (unit -> 'a seq);;
type 'a seq = Cons of 'a * (unit -> 'a seq)

では非常にいい加減に実装してみましょう。

# let rec fib n =
  let head (Cons (x, _)) = x in
  if n < 3 then
    Cons(1, fun () -> fib(n+1))
  else
    Cons(head(fib(n-1)) + head(fib(n-2)), fun() -> fib(n+1));;
val fib : int -> int seq = <fun>
# let f = fib 30;;
val f : int seq = Cons (832040, <fun>)

とてもいい加減なので皆こんなコードを書いてはいけません。というかボクの感覚ではこれは遅延ストリームとは呼びたくないんですが…
さて、上のコードを適当に lazy 使ってこんな風に書き換えても当然メモ化とか働くはずがないわけですね。

type 'a seq = Cons of 'a * ('a seq Lazy.t);;
let rec fib n =
  let head (Cons (x, _)) = x in
  if n < 3 then
    Cons(1, lazy(fib(n+1)))
  else
    Cons(head(fib(n-1)) + head(fib(n-2)), lazy(fib(n+1)));;

これは酷い。えーと簡単に説明すると関数呼び出しのたびに新しいオブジェクト作ってるはずで、それだと遅延オブジェクトのメモ化は働かない、と。
仕方がないので少し真面目に書きました。第 1000 項目とか余裕でオーバーフローしちゃうので Int64 モジュール使ってます。名前のとおりのモジュールです。float でもなんでもよかった。まああんまり意味ないです。

type 'a seq = Cons of 'a * ('a seq Lazy.t);;
let head (Cons (x, _)) = x;;
let tail (Cons (_, t)) = Lazy.force t;;
let rec fib =
  let rec add x y = Cons(Int64.add(head(x))(head(y)), lazy(add(tail(x))(tail(y)))) in
  Cons(Int64.one, lazy(
              Cons(Int64.one, lazy(
                          add(tail(fib))(fib)
                          )
                   )
             )
      );;
let rec at n s = if n = 1 then head(s) else at (n-1)(tail(s));;
# at 1000 fib;;
- : int64 = 817770325994397771L

ちょっぱやでちゃんと計算されました。やったー。どこの Lisp だという感じのコードですがまあいいでしょう。
何か解説だるいので省略したいと思います！眠いしね！
実は括弧の対応関係に悩んで30分くらい困ったりしました。初心者なもので…！

追記：別にこれでいい

let fib = let rec fibgen n0 n1 = Cons(n0, lazy(fibgen(n1)(n0+n1))) in fibgen 1 1;;