Programming Praxis: Hamming Numbers

Today's problem is to generate the first 1000 numbers in the sequence of Hamming numbers. More information on Hamming numbers can be found at the Programming Praxis blog post.

When I first saw this problem my mind jumped right to an imperative way of solving it. Start building up a list of numbers, keep checking to see if I had a 1000, and then print the list. Although this would work, it didn't seem very Clojureish.

That's when I remebered lazy sequences. A lazy sequence will generate the numbers as I need them. Then I can just ask for a 1000 and it will generate a 1000 numbers (maybe a few more, but we'll never see these). Here's the code:

;;Hamming Numbers

(defn hamming-generator
  ([] (hamming-generator (sorted-set 1)))
  ([some-set] (let [n (first some-set)
                    s (disj some-set n)]
                (cons n
                      (lazy-seq (hamming-generator
                                 (conj s (* n 2) (* n 3) (* n 5))))))))

(def hamming-numbers (take 1000 (hamming-generator)))

The first line in the function is there to seed the function with a "1". The real meat of the function goes like this: I bind the first value in the sorted set to n and then I remove n from the sorted set and bind the new set to s. From there I create a seq with n at the front and a lazy-seq representing the future values at the end. I don't get a stack overflow with the recursive call because lazy-seq only calls hamming-generator when a new number is needed. lazy-seq caches the values from the previous calls to hamming-generator and passes the last generated set to hamming-generator to get the next value in the sequence. Nice and elegant and it does all the book keeping work for you!

gist