(* Lazy prime number generation in Standard ML *) datatype 'a seq = Nil | Cons of 'a * (unit -> 'a seq); fun from k = Cons(k, fn()=> from(k + 1)); fun filterq pred Nil = Nil | filterq pred (Cons(x, xf)) = if pred x then Cons(x, fn()=> filterq pred (xf())) else filterq pred (xf()); fun sift p = filterq (fn n => n mod p <> 0); fun sieve (Cons(p, nf)) = Cons(p, fn()=>sieve(sift p (nf()))); fun upto(0, _) = [] | upto(_, Nil) = [] | upto(n, Cons(x, xf)) = if n < x then [] else x :: upto(n, xf()); fun primes(n) = upto(n, sieve(from 2)); |