Last night on #clojure Lau_of_DK asked for a way to define the sequence of prime numbers.
Having helped Lou Franco in his effort to parallelize primes computation and solved the fourth question of Google Treasure Hunt using Clojure, I thought I knew pretty well how to produce primes in Clojure but I stumbled accross some Haskell code that was far smarter. Here it is, now ported to Clojure:
(def primes (lazy-cons 2 ((fn this[n] (let [potential-divisors (take-while #(<= (* % %) n) primes)] (if (some #(zero? (rem n %)) potential-divisors) (recur (inc n)) (lazy-cons n (this (inc n)))))) 3)))
It’s interesting to note that the seq is seeded with 1 and 2 because Clojure’s lazy seqs have a off by one evaluation (when one asks for the nth value, the nth+1 is computed — to know if the end of the seq is reached). No, no, no! I was plain wrong: if I need to seed with [1 2] 2 it’s because of the take-while whose predicate must return at least one false.
Update: In comments, Cale Gibbard points out that my definition of prime numbers is loose: 1 isn’t a prime. I fixed the code.