OCamlで無限リスト。

OCamlのLazyモジュールで遊んでみました。
とりあえず、lazy (OCamlの予約語) と Lazy.force だけ覚えておけばよさそうです。

lazy

'a -> 'a lazy_t *1。 'a lazy_t なる、文字通りlazyな型を作り出す。

Lazy.force

'a Lazy.t -> 'a。 Lazy.t (=lazy_t) の皮をひっぺがす。

単純ですね。

こいつを使って、Haskell御用達の無限リストを作ってみましょー。

(* 無限リスト *)
module InfList : sig
  type 'a t
  val from : int -> int t
  val head : 'a t -> 'a
  val tail : 'a t -> 'a t
  val take : int -> 'a t -> 'a list
  val map  : ('a -> 'b) -> 'a t -> 'b t
  val nth  : int -> 'a t -> 'a
  val primes : int t
end
  =
struct
  type 'a t = Cons of 'a * ('a t lazy_t)

  (* n, n+1, n+2, ... *)
  let rec from n = Cons (n, lazy (from (n+1)))

  let head (Cons (x, _)) = x
  let tail (Cons (_, xs)) = Lazy.force xs

  (* 先頭の n 個の要素からなる只のリストを返す *)
  let take n s =
   let rec take' m (Cons (x, xs)) l =
     if m = 0 then List.rev l
     else take' (m-1) (Lazy.force xs) (x :: l)
   in
     take' n s []
 
  let rec map f (Cons (x, xs)) =
    Cons (f x, lazy (map f (Lazy.force xs)))

  let rec nth n (Cons (x, xs)) =
    if n = 1 then x
    else nth (n-1) (Lazy.force xs)

  (* 無限リストから、n の倍数を取り除いた無限リストを返す *)
  let rec sift n (Cons (x, xs)) =
    if x mod n <> 0 then Cons (x, lazy (sift n (Lazy.force xs)))
    else sift n (Lazy.force xs)

  let rec sieve (Cons (x, xs)) =
    Cons (x, lazy (sieve (sift x (Lazy.force xs))))

  let primes = sieve (from 2)
end

リストの先頭要素と、それ以降のlazyな無限リストのペアとして InfList.t を実装しています。
この無限リストはこちらの例をちょこっと改造したものです。

ぶっちゃけ、t の定義を Cons of 'a * (unit -> 'a t) にして「lazy 〜 と Lazy.force f」 を 「fun () -> 〜 と f ()」に変えるだけでシグネチャそのままでごっそりInfListの実装を切り替えることができます。まぁ、Lazy 使った方が効率良いのですが。

とりあえず手元の計算機で

# InfList.nth 15000 InfList.primes  (* 15000th 素数 *);;
- : int = 163841

くらいまではそれなりの時間で出ました。

*1:実際には関数ではない