Unknown / Ambiguous / Incomplete

Recently I've been playing with programming in Clojure. It's the first time I've played with lazy evaluation. Example: calculating prime numbers with the sieve of Eratosthenes algorithm.

Producing a sequence of natural numbers is trivial. (1 is a special case of a number that is neither prime nor composite. I've skipped it intentionally.)

(def numbers (iterate inc 2))
(take 5 numbers)
=> (2 3 4 5 6)


Note: all examples were tested with clojure release 20081217. I don't know if things work the same in version 1.0. Also, please excuse lame code formatting. I'm working on it.

Sieve of Eratosthenes is quite a simple algorithm. Eliminate multiplies of prime numbers until only prime numbers are left.

The first prime number is 2. We can eliminate all even numbers with the following statement:

(filter
odd?
numbers)
=> (3 5 7 9 11...)


The odd? predicate is a part of the standard library. If it weren't provided by the clojure standard library, we could have had it defined as follows:

(defn odd? [x]
(not= 0 (rem x 2)))


We also need indivisibility by 3, by 5 etc. We can produce all the necessary predicates with this factory method (functional programmers probably have some different name for this design pattern).

(defn indivisible-by [p]
(fn [x]
(not= 0 (rem x p))))


So (indivisible-by 2) and odd? are semantically equal.

(filter
(indivisible-by 2)
numbers)
=> (3 5 7 9 11...)


We can chain several of those filters together:

(filter
(indivisible-by 3)
(filter
(indivisible-by 2)
numbers))
=> (5 7 11 13 17...)


For brevity we will define a sieve-by filtering operation:

(defn sieve-by [p candidates]
(filter
(indivisible-by p)
candidates))


As we eliminate the composite numbers, we need a way to gather the prime numbers. A prime numbers is on the beginning of the sequence just prior to the application of sieve-by function.

(defn get-primes [primes candidates]
(let [p (first candidates)]
(recur
(lazy-cons p primes)
(sieve-by p
candidates))))


Unfortunately the compiler can't figure out how to get out the result of this infinite recursion. Lazy evaluation definitely can't return a sequence of natural numbers filtered to nothing! We need a termination condition. For example we can calculate only prime numbers not greater than n:

(defn get-primes [primes candidates n]
(let [p (first candidates)]
(if (> p n)
primes
(recur
(lazy-cons p primes)
(filter (indivisible-by p)
candidates)
n))))


We can hide some implementation details:

(defn get-primes [n]
((fn [primes candidates]
(let [p (first candidates)]
(if (> p n)
primes
(recur
(lazy-cons p primes)
(filter (indivisible-by p)
candidates)))))
'()
(iterate inc 2)))


It works as expected, with one minor drawback -- lazy-cons appends new values at the beginning of a list, rather than at the end.

(get-primes 100)
=> (97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2)