(* An infinite sequence of numbers is represented as a pair of components:
the first component is a number and the second component is a function,
which when called generates the rest of the infinite sequence. *)
datatype InfiniteSequence = Seq of int * (unit -> InfiniteSequence)
(* The function filterSeq takes a predicate "pred" and an infinite sequence
and returns a new infinite sequence which consists of only those elements
that satisfy the predicate *)
fun filterSeq pred (Seq(i,g)) =
if (pred i) then Seq(i, (fn () => filterSeq pred (g())))
else filterSeq pred (g())
(* "take k seq" returns a list of the first k elements of an infinite sequence
*)
fun take 0 (Seq(i,g)) = []
| take k (Seq(i,g)) = i :: (take (k-1) (g()))
(* Here is a simple infinite sequence of all numbers starting from 2 *)
fun makeNats i = Seq (i, fn () => makeNats (i+1))
val nats = makeNats 2
(* Primes are another infinite sequence generated as follows *)
fun notMultiple i = (fn j => (j mod i) <> 0)
fun makePrimes (Seq(i,g)) = Seq (i, fn () =>
(makePrimes
(filterSeq (notMultiple i) (g()))))
val primes = makePrimes nats
(* You can test the program by typing:
take 10 primes
which should generate the first 10 primes.
*)