How to go about composing core functions, rather then using imperative style?

Question

I have translated this code, the snippet below, from Python to Clojure. I replaced Python's while construct with Clojure's loop-recur here. But this doesn't look idiomatic.

(loop [d 2 [n & more] (list 256)]
      (if (> n 1)
        (recur (inc d)
               (loop [x n sublist more]
                 (if (= (rem x d) 0)
                   (recur (/ x d) (conj sublist d))
                   (conj sublist x))))
        (sort more)))

This routine gives me (3 3 31), that is prime factors of 279. For 256, it gives, (2 2 2 2 2 2 2 2), that means, 2^8.

Moreover, it performs worse for large values, say 987654123987546 instead of 279; whereas Python's counterpart works like charm.

How to start composing core functions, rather then translating imperative code as is? And specifically, how to improve this bit?

Thanks.

[Edited]

Here is the python code, I referred above,

def prime_factors(n):
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
    return factors

Answer 1

A straight translation of the Python code in Clojure would be:

(defn prime-factors [n]
  (let [n       (atom n)  ;; The Python code makes use of mutability which
        factors (atom []) ;; isn't idiomatic in Clojure, but can be emulated
        d       (atom 2)] ;; using atoms
    (loop []
      (when (< 1 @n)
        (loop []
          (when (== (rem @n @d) 0)
            (swap! factors conj @d)
            (swap! n quot @d)
            (recur)))
        (swap! d inc)
        (recur)))
    @factors))

(prime-factors 279)                    ;; => [3 3 31]
(prime-factors 987654123987546)        ;; => [2 3 41 14389 279022459]
(time (prime-factors 987654123987546)) ;; "Elapsed time: 13993.984 msecs"
                                       ;; same performance on my machine
                                       ;; as the Rosetta Code solution

---

You can improve this code to make it more idiomatic:

• from nested loops to a single loop:

    (loop []
      (cond
        (<= @n 1)            @factors
        (not= (rem @n @d) 0) (do (swap! d inc)
                                 (recur))
        :else                (do (swap! factors conj @d)
                                 (swap! n quot @d)
                                 (recur))))))

• get rid of the atoms:

    (defn prime-factors [n]
      (loop [n       n
             factors []
             d       2]
        (cond
          (<= n 1)           factors
          (not= (rem n d) 0) (recur n factors (inc d))
          :else              (recur (quot n d) (conj factors d) d))))

• replace == 0 by zero?:

          (not (zero? (rem n d))) (recur n factors (inc d))

You can also overhaul it completely to make a lazy version of it:

(defn prime-factors [n]
  ((fn step [n d]
     (lazy-seq 
       (when (< 1 n)
         (cond
           (zero? (rem n d)) (cons d (step (quot n d) d))
           :else             (recur n (inc d)))))
   n 2))

---

I planned to have a section on optimization here, but I'm no specialist. The only thing I can say is that you can trivially make this code faster by interrupting the loop when d is greater than the square root of n:

    (defn prime-factors [n]
      (if (< 1 n)
        (loop [n       n
               factors []
               d       2]
          (let [q (quot n d)]
            (cond
              (< q d)           (conj factors n)
              (zero? (rem n d)) (recur q (conj factors d) d)
              :else             (recur n factors (inc d)))))
        []))

    (time (prime-factors 987654123987546)) ;; "Elapsed time: 7.124 msecs"

Answer 2

Not every loop unrolls cleanly into an elegant "functional" decomposition.

The Rosetta Code solution suggested by @edbond is pretty simple and concise; I would say it's idiomatic since no obvious "functional" solution is apparent. That solution runs noticeably faster on my machine than your Python version for 987654123987546.

More generally, if you're looking to expand your understanding of functional idioms, Bedra and Halloway's "Programming Clojure" (pp.90-95) presents an excellent comparison of different versions of the Fibonacci sequence, using loop, lazy seqs, and an elegant "functional" version. Chouser and Fogus's "Joy of Clojure" (MEAP version) also has a nice section on function composition.