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
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!