Created
October 18, 2010 14:34
-
-
Save unclebob/632303 to your computer and use it in GitHub Desktop.
Prime factors Kata in Clojure
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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) |
Author
unclebob
commented
Feb 28, 2012
via email
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!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment