(**** LECTURE 9: Sequences, or Lazy Lists ****) datatype 'a seq = Nil | Cons of 'a * (unit -> 'a seq); fun head (Cons(x,_)) = x; fun tail (Cons(_,xf)) = xf(); fun from k = Cons(k, fn()=> from(k+1)); (*if n<0, converts entire sequence to a list; else does n forces*) fun get (0, xq) = [] | get (n, Nil) = [] | get (n, Cons(x,xf)) = x :: get (n-1, xf()); (** joining two sequences: concatenation or fair interleaving*) fun appendq (Nil, yq) = yq | appendq (Cons(x,xf), yq) = Cons(x, fn()=> appendq(xf(), yq)); fun interleave (Nil, yq) = yq | interleave (Cons(x,xf), yq) = Cons(x, fn()=> interleave(yq, xf())); (** functionals for sequences **) fun mapq f Nil = Nil | mapq f (Cons(x,xf)) = Cons(f x, fn()=> mapq f (xf())); fun filterq p Nil = Nil | filterq p (Cons(x,xf)) = if p x then Cons(x, fn()=> filterq p (xf())) else filterq p (xf()); fun iterates f x = Cons(x, fn()=> iterates f (f x)); (*** Simple applications ***) (*Random numbers *) get (15, mapq (truncto 10) (iterates nextrandom 1.0)); (** Hughes/MIT example: Numerical computations **) fun nextapprox a x = (a/x + x) / 2.0; get(7, iterates (nextapprox 9.0) 1.0); fun within (eps:real) (Cons(x,xf)) = let val Cons(y,yf) = xf() in if abs(x-y) <= eps then y else within eps (Cons(y,yf)) end; fun root a = within 1E~6 (iterates (nextapprox a) 1.0); fun non_divides m n = (n mod m <> 0); fun sieve (Cons (x, xq)) = Cons (x, fn () => filterq (non_divides x) (sieve (xq()))); sieve (from 2);