Reading material

Additional material

(* finite and infinite sequences *)
datatype 'a seq = Nil
                | Cons of 'a * (unit -> 'a seq)

(* operations on sequences *)
signature SEQUENCE =
  sig

  (* returns the head of the sequence *)
  val hd : 'a seq -> 'a

  (* returns the tail of the sequence *)
  val tl : 'a seq -> 'a seq

  (* tests if the sequence is empty *)
  val null : 'a seq -> bool

  (* returns the sequence obtained by combining the head and the tail
     sequence *)
  val cons : 'a * 'a seq -> 'a seq

  (* returns the sequence consisting of the first n elements of the 
     sequence *)
  val take : 'a seq * int -> 'a seq

  (* returns the sequence obtained by dropping the first n elements
     of the sequence *)
  val drop : 'a seq * int -> 'a seq

  (* returns the sequence with the elements of the list *)
  val fromList : 'a list -> 'a seq

  (* returns the list with the elements of the sequence *)
  val toList : 'a seq -> 'a list

  (* returns the concatenation of the sequences *)
  val @ : 'a seq * 'a seq -> 'a seq

  (* returns the interleaving of the sequences *)
  val || : 'a seq * 'a seq -> 'a seq

  (* returns the sequence obtained by applying the function f to all its
     elements *)
  val map : ('a -> 'b) -> 'a seq -> 'b seq

  (* returns the sequence of all elements of the sequence which satisfy
     the predicate *)     
  val filter : ('a -> bool) -> 'a seq -> 'a seq

  (* returns the initial segment of the sequence which satisfies the
     predicate *)
  val takewhile : ('a -> bool) -> 'a seq -> 'a seq

  (* returns the sequence obtained by dropping the initial segment of 
     the sequence which satisfies the predicate *)
  val dropwhile : ('a -> bool) -> 'a seq -> 'a seq

  (* tests if there exists an element in the sequence which satisfies 
     the predicate *)
  val exists : ('a -> bool) -> 'a seq -> bool

  (* tests if all elements in the sequence satisfy the predicate *)
  val all : ('a -> bool) -> 'a seq -> bool

  (* given a function which associates to every element of the sequence 
     a string, prints the elements of the sequence *)
  val print : ('a -> string) -> 'a seq -> unit
  end

structure Sequence : SEQUENCE =
  struct

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

  fun tl (Cons(_, xf)) = xf()
    | tl Nil           = raise Empty

  fun null Nil = true
    | null _   = false

  fun cons (x, xq) = Cons(x, fn () => xq)

  fun take (xq, 0)          = Nil
    | take (Nil, _)         = raise Subscript
    | take (Cons(x, xf), n) = Cons(x, fn () => take(xf(), n - 1))

  fun drop (xq, 0)          = xq
    | drop (Nil, _)         = raise Subscript
    | drop (Cons(x, xf), n) = drop(xf (), n - 1)

  fun fromList []        = Nil
    | fromList (x :: xs) = Cons(x, fn () => fromList xs)

  fun toList Nil           = []
    | toList (Cons(x, xf)) = x :: toList(xf())

  infix @
  fun (Nil           @ yq) = yq
    | ((Cons(x, xf)) @ yq) = Cons(x, fn () => (xf() @ yq))

  infix ||
  fun (Nil           || yq) = yq
    | ((Cons(x, xf)) || yq) = Cons(x, fn () => (yq || xf()))

  fun map f Nil           = Nil
    | map f (Cons(x, xf)) = Cons(f x, fn () => map f (xf()))

  fun filter pred Nil           = Nil
    | filter pred (Cons(x, xf)) =
        if pred x then Cons(x, fn () => filter pred (xf()))
        else filter pred (xf())

  fun takewhile pred Nil           = Nil
    | takewhile pred (Cons(x, xf)) =
        if pred x then Cons(x, fn () => takewhile pred (xf()))
        else Nil

  fun dropwhile pred Nil           = Nil
    | dropwhile pred (Cons(x, xf)) =
        if (pred x) then dropwhile pred (xf())
        else xf()

  fun exists pred Nil           = false
    | exists pred (Cons(x, xf)) = (pred x) orelse (exists pred (xf()))

  fun all pred Nil           = true
    | all pred (Cons(x, xf)) = (pred x) andalso (all pred (xf()))

  fun print toString Nil           = (TextIO.print "\n"; ())
    | print toString (Cons(x, xf)) = (TextIO.print(toString(x)); print toString (xf()))

  end