signature STREAM =
    (* a very limited signature for streams (i.e. lazy lists) *)
sig
    type 'a T                    (* type of streams *)

    exception EMPTY              (* raised by head(empty) or tail(empty) *)

    val empty   : 'a T                (* the empty stream *)
    val isempty : 'a T -> bool        (* return true if queue is empty *)

    val cons    : 'a * 'a T -> 'a T   (* add element to front of stream *)
    val head    : 'a T -> 'a          (* return front element of stream *)
    val tail    : 'a T -> 'a T        (* remove front element of stream *)

    val append  : 'a T * 'a T -> 'a T (* lazily append two streams *)
    val reverse : 'a T -> 'a T        (* lazily reverse a stream *)
end


structure Stream : STREAM =
    (* A very limited implementation of streams (i.e. lazy lists).        *)
    (* The only operations that are actually lazy are append and reverse. *)
struct
    datatype 'a StreamNode = Nil | Cons of 'a * 'a Stream
    withtype 'a Stream = 'a StreamNode Delay.T

    type 'a T = 'a Stream

    exception EMPTY

    val empty = Delay.trivial Nil

    fun isempty s = case Delay.force s of Nil => true
                                        | Cons (_,_) => false

    fun cons (x,s) = Delay.trivial (Cons (x,s))

    fun head s = case Delay.force s of Nil => raise EMPTY
                                     | Cons (x,s) => x

    fun tail s = case Delay.force s of Nil => raise EMPTY
                                     | Cons (x,s') => s'

    fun append (s,t) =
          Delay.delay (fn () => case Delay.force s of
                                  Nil => Delay.force t
                                | Cons (x,s') => Cons (x,append (s',t)))

    fun reverse s =
      let fun rev (s,r) = case Delay.force s of
                            Nil => r
                          | Cons (x,s') => rev (s',Cons (x,Delay.trivial r))
      in
          Delay.delay (fn () => rev (s,Nil))
      end
end