(* from Paulson 5.12 *)
module Seq =
struct
  type 'a t = Nil | Cons of 'a * (unit -> 'a t)

  exception Empty
  let hd = function
      Cons(x,xf) -> x
    | Nil -> raise Empty

  let tl = function
      Cons(x,xf) -> xf ()
    | Nil -> raise Empty

  let empty = Nil

  let cons (x,xq) = Cons (x, function () -> xq)

  let fromList l =
    List.fold_right (fun leftarg rightarg -> cons (leftarg,rightarg) ) l Nil

  let rec toList = function
      Nil -> []
    | Cons(x,xf) -> x::(toList (xf ()))

  let rec from k =
    Cons (k, function () -> from (k+1) )

  (* return first n elements of sequence xq *)
  exception Subscript
  let rec take = function
      (xq,0) -> []
    | (Nil,n) -> raise Subscript
    | (Cons(x,xf),n) -> x::take (xf(),n-1)

  (* does Not evaluate all elements of the first argument xq *)
  let rec append (xq,yq) = match (xq,yq) with
      Nil,yq -> yq
    | (Cons (x,xf)),yq -> Cons(x,function () -> append ((xf ()),yq))

  let rec appendSpecial f (xq,yq) = match (xq,yq) with
      Nil,yq -> f yq
    | (Cons (x,xf)),yq -> Cons(x,function () -> appendSpecial f ((xf ()),yq))

  let rec map f s = match s with
      Nil -> Nil
    | Cons(x,xf) -> Cons(f x,function () -> map f (xf ()) )

  let rec multiply f s = match s with
      Nil -> Nil
    | Cons(x,xf) -> appendSpecial (multiply f) (f x, xf())

  let rec filter p s = match s with
      Nil -> Nil
    | Cons(x,xf) ->
	if p x
	then Cons(x, function () -> filter p (xf ())) (* include this guy, he passed *)
	else filter p (xf ()) (* skip this guy, he failed *)

  let rec count p = function
      Nil -> 0
    | Cons(x,xf) ->
	if p x
	then 1+(count p (xf()))
	else count p (xf())

  (* [x,f(x),f(f(x)),f(f(f(x))),...,f^k(x),...] *)
  let rec iterates f x = Cons(x, function () -> iterates f (f x))

end

(* example
let tripler = function x -> fromList [x;x;x]
take ((multiply tripler (from 0)),100);;
*)