Guarded streams.

stream.ml

module type STREAM =
sig
  type 'a delay
  type 'a stream

  val delay     : 'a -> 'a delay
  val next      : ('a -> 'b) -> 'a delay -> 'b delay
  val fix       : ('a delay -> 'a) -> 'a
  val unzip     : ('a * 'b) delay -> 'a delay * 'b delay
  val zip       : ('a delay * 'b delay) -> ('a * 'b) delay
  val tl        : 'a stream -> 'a stream delay
  val hd        : 'a stream -> 'a
  val cons      : 'a -> 'a stream delay -> 'a stream
  val sample    : int -> 'a stream -> 'a list
end

module Stream : STREAM =
struct
  type 'a delay         = unit -> 'a
  let delay x           = fun () -> x
  let next f d          = fun () -> f (d ())
  let rec fix f         = f (fun () -> fix f)
  let unzip x           = ((fun () -> fst (x ())), (fun () -> snd (x ())))
  let zip (x, y)        = fun () -> (x (), y ())

  type 'a stream        = S of 'a * 'a stream delay
  let tl (S (_, x))     = x
  let hd (S (x, _))     = x
  let cons x y          = S (x, y)

  let rec sample n s =
    match n with
      | 0 -> []
      | _ -> hd s :: sample (n - 1) (tl s ())
end

module S = Stream

let nats =
  S.fix
    (fun t k -> S.cons k (S.next (fun f -> f (k + 1)) t))
    0

let fibs =
  S.fix
    (fun t (n, m) -> S.cons m (S.next (fun f -> f (m, m + n)) t))
    (1, 1)

Playing with guarded recursion ideas from Neel's blog and paper.