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

omiel · Accepted Answer

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"

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

Answers (2)

Related Questions