Let us study the implementation of a stream of prime numbers. We use
the Sieve algorithm which basically works by filtering out
numbers which are multiples of the primes found so far. We assume we
have a means of constructing streams. We denote this by
where
is the head of the stream and
is the
rest (possibly not yet evaluated) of the stream.
First, we construct a stream of integers that starts at a given value.
int_starting_at(k) = = stream_cons(k, int_starting_at(k + 1))
We aim to filter from this stream all the numbers that are not
primes. We can do this by defining a function Filter which takes in as
parameters a stream and a predicate and returns a stream whose
elements satisfy the predicate.
Filter(P, s) = if empty?(s) then
s
else
if P(hd(s)) then
stream_cons(hd(s), Filter(P, tl(s)))
else
Filter(P, tl(s))
The stream of primes can then be produced by a function Sieve which
takes in a stream of integers as parameter, assumes the head of the
stream is a prime, filters out all multiples of this from the rest of
the stream and calls itself again on the new stream formed.
Sieve(s) = stream_cons(hd(s),
Sieve(Filter(.x(not (x|hd(s))),tl(s))))
``|'' represents the predicate ``is divisible by''.
Primes = Sieve(int_starting_at(2))