stream.sml

signature STREAM = sig
  type 'a stream
  val mkseq: 'a -> ('a -> 'a) -> 'a stream
  val car: 'a stream -> 'a
  val cdr: 'a stream -> 'a stream
  val nth: 'a stream -> int -> 'a
  val toList: 'a stream -> int -> 'a list
end

structure Seq :> STREAM = struct
  datatype 'a elem = Materialized of 'a | Promise of unit -> 'a
  datatype 'a stream = Stream of 'a elem list * ('a -> 'a)
  exception WTF

  fun mkseq z succ =
    let
      val next = fn () => succ z
    in
      Stream ([Materialized z, Promise next], succ)
    end
  
  fun car (Stream (((Materialized x)::xs), _)) = x
    | car _ = raise WTF

  fun cdr (Stream (((Materialized x)::xs), succ)) =
    let
      val cur = hd xs
    in
      case cur of
           Promise p => 
              let
                val newVal = p()
              in
                Stream ([Materialized newVal, (Promise (fn () => succ newVal))], succ)
              end
         | _ => raise WTF
    end
    | cdr _ = raise WTF
  
  fun nth s 0 = car s
    | nth s n = nth (cdr s) (n - 1)

  fun toList s 0 = []
    | toList s n = [(car s)] @ toList (cdr s) (n - 1)
end


(* Test code *)
val seqNum = Seq.mkseq 0 (fn x => x + 1)
val seqStr = Seq.mkseq "a" (fn x => x ^ (String.extract (x, 0, SOME 1)))