(* Chris Okasaki
   School of Computer Science
   Carnegie Mellon University
   Pittsburgh, PA 15213
   cokasaki@cs.cmu.edu *)

functor Stream() : STREAM =
struct

  open System.Unsafe.Susp
    (* type 'a susp                                                 *)
    (* val delay : (unit -> 'a) -> 'a susp                          *)
    (* val force : 'a susp -> 'a                                    *)
    (*                                                              *)
    (* Do not be concerned by the word "Unsafe" above.  Suspensions *)
    (* only appear in the Unsafe structure because of a historical  *)
    (* accident -- there is actually nothing unsafe going on here.  *)
    (* If it really bothers you, you can write your own version of  *)
    (* suspensions using refs, but then the type of lcons will be   *)
    (* only weakly polymorphic.                                     *)

    
  datatype 'a Stream = Nil 
                     | Cons of 'a * 'a Stream
                     | LCons of 'a * 'a Stream susp

  exception Empty

  val empty = Nil

  val cons = Cons

  fun lcons (x,xs) = LCons (x,delay xs)

  fun head Nil = raise Empty
    | head (Cons (x,_)) = x
    | head (LCons (x,_)) = x

  fun tail Nil = Nil
    | tail (Cons (_,xs)) = xs
    | tail (LCons (_,xs)) = force xs

  fun isempty Nil = true
    | isempty _ = false

  fun size Nil = 0
    | size (Cons (_,xs)) = 1 + size xs
    | size (LCons (_,xs)) = 1 + size (force xs)
end