Prime factors Kata in Clojure

prime_factors_test.clj

(ns prime-factors-test
  (:use clojure.test midje.sweet))

(defn factors-starting-at [f n]
  (cond
    (> f (Math/sqrt n)) (if (= n 1) [] [n])
    (= 0 (mod n f)) (cons f (factors-starting-at f (/ n f)))
    :else (recur (inc f) n)))

(defn prime-factors-of [n]
  (factors-starting-at 2 n))

(defn mersenne [n]
  (int (dec (Math/pow 2 n))))

(deftest prime-factors
  (fact (prime-factors-of 1) => [])
  (fact (prime-factors-of 2) => [2])
  (fact (prime-factors-of 3) => [3])
  (fact (prime-factors-of 4) => [2 2])
  (fact (prime-factors-of 5) => [5])
  (fact (prime-factors-of 6) => [2 3])
  (fact (prime-factors-of 7) => [7])
  (fact (prime-factors-of 8) => [2 2 2])
  (fact (prime-factors-of 9) => [3 3])
  (fact (prime-factors-of 10) => [2 5])
  (fact (prime-factors-of 12) => [2 2 3])
  (fact (prime-factors-of 18) => [2 3 3])
  (fact (prime-factors-of 25) => [5 5])
  (fact (prime-factors-of 1369) => [37 37])
  (fact (prime-factors-of (* 2 3 5 7 11 17 37)) => [2 3 5 7 11 17 37])
  (fact (prime-factors-of (mersenne 17)) => [(mersenne 17)])
  (fact (prime-factors-of (mersenne 19)) => [(mersenne 19)])
  (fact (prime-factors-of (mersenne 31)) => [(mersenne 31)])
  )

(run-tests)

I would use (zero? foo) instead of (= 0 foo). IMVHO it's more readable, and according to Rich Hickey it also performs better.

I would also be interested what you think about the non-stack-smashing version:

(defn factors-starting-at
  ([f n] (factors-starting-at f n []))
  ([f n result]
    (cond
      (> f (Math/sqrt n)) (if (= n 1) [] (conj result n))
      (zero? (mod n f)) (recur f (/ n f) (conj result f))
      :else (recur (inc f) n result))))

Does the extra argument hurt readability so bad that the non-tail-recursive version should be preferred for small numbers?

Good point on the (zero?), I had forgotten about that.

I chose the non-tail version because it only pushes the stack for prime factors that are repeated. So it could blow the stack for n**b where b is very large; but for most numbers it's pretty safe.

In general, though, tail-recursion should be preferred (of course) despite the extra arg.

Hi @unclebob,

I was attempting a version that didn't require the call-out to factors-starting-at, but instead applied a default starting factor. I came up with the following:
(I'm not using (cond), which is way neater; instead what is below reflects the structure of your original PrimeFactors kata in java)

(defn prime-factors-of
  ([n] (prime-factors-of 2 n))
  ([f n]
    (if (> n 1)
      (if (= 0 (mod n f))
        (cons f (prime-factors-of f (/ n f)))
        (recur (inc f) n)
      )
      ()
    )
  )
)

What is your opinion of the default value form versus extracting the factors-of function? I'm on the fence - SRP and clear names versus the simplicity of a single recursive call.

This is pretty straight forward Clojure, I'm not sure extracting a method is worth it. BTW, there may be a way to get rid of that non-tail call by using a let-form in the if…

…

On Feb 28, 2012, at 8:02 , James Hood wrote: Hi @unclebob, I was attempting a version that didn't require the call-out to factors-starting-at, but instead applied a default starting factor. I came up with the following: (I'm not using (cond), which is way neater; instead what is below reflects the structure of your original PrimeFactors kata in java) ``` clojure (defn prime-factors-of ([n] (prime-factors-of 2 n)) ([f n] (if (> n 1) (if (= 0 (mod n f)) (cons f (prime-factors-of f (/ n f))) (recur (inc f) n) ) () ) ) ) ``` What is your opinion of the default value form versus extracting the factors-of function? I'm on the fence - SRP and clear names versus the simplicity of a single recursive call. --- Reply to this email directly or view it on GitHub: https://gist.github.com/632303

--- Robert C. Martin (Uncle Bob) | unclebob@cleancoder.com Uncle Bob Consulting LLC. | @unclebobmartin 847.922.0563 | cleancoder.com

@hoodja: although it might seem strange when seen from a curly-brace-language-background, lispers like to put all closing parens on a single line (they feel lonely otherwise):

(defn prime-factors-of
  ([n] (prime-factors-of 2 n))
  ([f n]
    (if (> n 1)
      (if (= 0 (mod n f))
        (cons f (prime-factors-of f (/ n f)))
        (recur (inc f) n))
      [])))

I replaced () by [] to make the empty list stand out more clearly from all those parens.

To repeat my comment from above: (zero? num) is more readable than (= 0 num) IMHO, and it also has performance benefits (nice combo).

@unclebob:
I think that you really need an extra (accumulator) argument to make the function tail-recursive. But I'd be delighted if you can prove me wrong!