Woo hoo — half way through. Well, not yet, but at the end of this entry.
Yesterday, we saw sequences. Now, here’s a way to use them: the Prime Sieve of Eratosthenes. Here it is in Scheme from the SICP lectures:
(define (sieve s)
(cons-stream (head s)
(sieve (filter
(lambda (x)
(not
(divisible? x (head s))))
(tail s)))))
(define primes
(sieve (integers-from 2)))
And here is a complete clojure program (all undefined functions are defined as part of the seq interface)
(defn sieve [s]
(lazy-cons (first s)
(sieve (filter
(fn [x]
(not
(= (rem x (first s)) 0)))
(rest s)))))
(defn primes []
(sieve (iterate inc 2)))
(prn (take 10 (primes)))
Here’s how it works. The function sieve is a sequence and takes a sequence (in this case we pass in all numbers greater than or equal to two).
Working from the inside, this filter:
(filter
(fn [x]
(not
(= (rem x (first s)) 0)))
(rest s))
Filters the rest of the passed in stream based on whether the items are divisible by the first, so only the ones not divisible are passed. So for (iterate inc 2) we get a stream of all numbers not divsible by two.
The first of that stream is 3, and it is passed into sieve, so the resulting stream is all those not divisible by two (already filtered) or three. Once the stream is returned (lazily), the heads are lazy-cons’d on (that means that you get a stream with a given first and the rest set to the given stream). The first head was 2, the second was 3, the next one is 5 (the first number not divisible by 2 and 3), and so on.
(clojure day (March 20) in Northampton, MA is coming soon)
Update: It may look like sieve is an infinitely recursive function, but it’s not. lazy-cons is a macro that doesn’t evaluate its argument until rest is called on its return value. I haven’t looked at the implementation, but I imagine its implemented similarly to how cons-stream in the SICP lecture is.