(* 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