The Prime Factors Kata in Clojure

I've again had the pleasure of preparing a classic programming kata for your viewing enjoyment. Today I present to you the Prime Factors kata, implemented in Clojure:

The Kata

The Prime Factors Kata should hold a special place in every TDD practitioner's heart. It's a wonderful manifestation of the following principle:

As the tests get more specific, the code gets more generic! --Robert C. Martin

That principle is at the foundation of what Martin termed "The Transformation Priority Premise", which currently enjoys the elevated station of having its own wikipedia article.

Using Clojure, I found it a bit more awkward to bring out the transformations demonstrated in the original Java and Ruby implementations of this kata, but there are still a few nice sequences.

A potentially difficult sequence presents itself when approaching the case of 4 being factored to [2 2]. The programmer must transform this simple code:

(defn prime-factors-of [n]
  (if (> n 1) [n] []))

...into something that will factor out the number 2 multiple times, requiring recursion:

(defn prime-factors-of [n]
  (loop [n n, factors []]
    (if (> n 1)
      (if (zero? (mod n 2))
        (recur (/ n 2) (conj factors 2))
        [n]
    factors)))

It's not too difficult to see all of the elements from the first example in the second, but boy, that was a giant leap! Here's how I approached it more incrementally:

Step 1

Our starting point, at which all tests pass:

; Tests: {1 [], 2 [2], 3 [3]}

(defn prime-factors-of [n]
  (if (> n 1) [n] []))

Step 2

We introduce a let statement to initialize the collection and reformat the code:

; Passes: {1 [], 2 [2], 3 [3]}

(defn prime-factors-of [n]
  (let [factors []]
    (if (> n 1)
      [n]
      [])))

Step 3

We now use the collection introduced in the last step for the 'else' and re-introduce the 4 test case, which still fails, but we are in a better position to deal with it in the next steps:

; Passes: {1 [], 2 [2], 3 [3]}
; Fails: {4 [2 2]} -> [4]

(defn prime-factors-of [n]
  (let [factors []]
    (if (> n 1)
      [n]
      factors)))

Step 4

We check for even numbers and conj a 2 which still fails, but this failure is actually an incrementally 'better' kind of failure:

; Passes: {1 [], 2 [2], 3 [3]}
; Fails: {4 [2 2]} -> [2]

(defn prime-factors-of [n]
  (let [factors []]
    (if (> n 1)
      (if (zero? (mod n 2))
        (conj factors 2)
        [n])
      factors)))

Step 5

We introduce the transformation from let to loop/recur to pass the test, which is somewhat like going from if to while in the original presentation:

; Passes: {1 [], 2 [2], 3 [3], 4 [2 2]}

(defn prime-factors-of [n]
  (loop [n n, factors []]
    (if (> n 1)
      (if (zero? (mod n 2))
        (recur (/ n 2) (conj factors 2))
        [n])
      factors)))

This code also gets us past the 5 case and on to the 6 case, and it's 'smooth sailing' from there.

The final Clojure solution, as Robert Martin has already pointed out, differs from a typical solution in a more procedural language like Ruby or Java in that we didn't use a doubly-nested loop, we employed a single recursive loop with two recursion points.

The Music

For some time now I've imagined providing my own recorded music for a kata, but the longer the song, the more opportunities for mistakes in performance, and the longer the kata, the longer the song has to be. So, this shorter kata seemed like my best opportunity. So, I'm at both keyboards in this performance. I hope the quality of the music doesn't detract from the coding (which isn't perfect either).

The musical selections were, IMO, good choices, not just because of their limited difficulty and length, but because they are also standard repertoire from some of the greatest composers of all time, the "three 'B's"*. So, they complement this kata, which really should be part of the programmer's standard repertoire. Here are the musical selections in order of appearance:

1. Minuet in G Major, BWV Anh. 114
2. Minuet in G Minor, BWV Anh. 115
   • Assumed until recently to have been composed by Johann Sebastian Bach, but both were actually composed by Christian Petzold*.
3. Sonota No. 8 in C Minor, Adagio Cantabile (opening theme)
   • by Ludwig van Beethoven
4. Intermezzo in A Major from 'Six Piano Pieces', Op. 118, No. 2 (opening theme)
   • by Johannes Brahms

The Conclusion

IMO, despite the final solution being very few lines of code, the Prime Factors kata is nuanced and somewhat difficult to master. The principles it introduces are extremely important. If you haven't tried it yet, what are you waiting for?

---

* So, it was literally yesterday that I discovered that the two minuets referenced above were actually composed by Christian Petzold, not Bach! They were included in his 1725 Notebook for Anna Magdalena Bach, hence the long-standing albeit incorrect attribution. Honestly, I'm still in shock! (Sort of like when I found out Pluto didn't get to be a planet anymore...but I guess that is still up for debate...whatever.) How have I never known this???

Beyond the shock and surprise, it really throws off my whole "yeah, wouldn't it be great to record music by the three 'B's?" idea. Kind of dissappointing. Oh, well...

-Michael Whatcott