(* Source code from                               *)
(*   Chris Okasaki                                *)
(*   "Functional Data Structures"                 *)
(*   Second International Summer School on        *)
(*     Advanced Functional Programming Techniques *)
(*   August, 1996                                 *)

open System.Unsafe.Susp  (* import lazy evaluation primitives *)

infixr 5 ++  (* define ++ to have same associativity and precedence as @ *)

signature STREAM =
sig
  type 'a Stream

  exception EMPTY

  val empty   : 'a Stream
  val isEmpty : 'a Stream -> bool

  val cons    : 'a * 'a Stream -> 'a Stream         (* strict cons *)
  val head    : 'a Stream -> 'a         (* raises EMPTY if stream is empty *)
  val tail    : 'a Stream -> 'a Stream  (* raises EMPTY if stream is empty *)

  val ++      : 'a Stream * 'a Stream -> 'a Stream  (* infix append *)
  val reverse : 'a Stream -> 'a Stream
end

structure S : STREAM =
struct
  datatype 'a StreamCell = Nil | Cons of 'a * 'a Stream
  withtype 'a Stream = 'a StreamCell susp

  exception EMPTY

  val empty = delay (fn () => Nil)
  fun isEmpty s = case force s of Nil => true | _ => false

  fun cons (x, s) = delay (fn () => Cons (x, s))
  fun head s = case force s of Nil => raise EMPTY | Cons (x, s) => x
  fun tail s = case force s of Nil => raise EMPTY | Cons (x, s) => s

  fun s ++ t = delay (fn () => case force s of
                                 Nil => force t
                               | Cons (x, s) => Cons (x, s ++ t))
  fun reverse s = let fun rev (Nil, t) = force t
                        | rev (Cons (x, s), t) = rev (force s, cons (x, t))
                  in delay (fn () => rev (force s, empty)) end
end