3
\$\begingroup\$

I just finished this Merge Sort in Clojure, structured according to ex. 22-26 of this workshop.

The main question I have can be answered without spending time understanding the code: halve is called twice in merge-sort, is this still \$\mathcal{O}(n \log n)\$? (last lines in the code sample) Since it's functional programming, I can't think of a way to avoid calculating halve twice (can't stash the result into a variable).

I followed the structure set out in the exercises, but I think this code is bloated and hard to read. How would you improve the individual functions while maintaining the general structure?

(defn my-take-r [a-list n coll]
  (if (or
        (= 1 n)
        (singleton? coll))
     (concat
      a-list
      (list (first coll)))
     (recur
      (concat a-list (list (first coll)))
      (dec n)
      (rest coll))))

(defn my-take [n coll]
   (if (empty? coll)
    `()
    (my-take-r `() n coll)))

(defn my-drop [n coll]
  (if (or (zero? n) (empty? coll))
    (concat `() coll)
    (my-drop (dec n) (rest coll))))

(defn halve [a-seq]
  (let [i (int (/(count a-seq) 2))]
     (vec (list
           (concat `() (seq (subvec (vec a-seq) 0 i)))
           (concat `() (seq (subvec (vec a-seq) i)))))))

(defn seq-merge-r [output a-seq b-seq]
  (cond (and
          (empty? a-seq)
          (empty? b-seq)) output
        (empty? a-seq) (concat output b-seq)
        (empty? b-seq) (concat output a-seq)
        (<
          (first a-seq)
          (first b-seq)) (seq-merge-r (conj output (first a-seq)) (rest a-seq) b-seq)
        :else            (seq-merge-r (conj output (first b-seq)) a-seq (rest b-seq))))

(defn seq-merge [a-seq b-seq]
  (seq-merge-r [] (seq a-seq) (seq b-seq)))

(defn merge-sort [a-seq]
  (cond
    (empty? a-seq) a-seq
    (singleton? a-seq) a-seq
    :else (seq-merge
            (merge-sort (first  (halve a-seq)))
            (merge-sort (second (halve a-seq))))))
\$\endgroup\$
3
  • \$\begingroup\$ Of course you can stash the result, calculate halve once and bind it to a local using let. Functional programming does not mean you need to copy each expression. \$\endgroup\$
    – Yuri Steinschreiber
    Jul 28, 2016 at 6:59
  • \$\begingroup\$ Isn't it executed twice even if I bind the function to some shorthand using let? \$\endgroup\$
    – bkoodaa
    Jul 28, 2016 at 11:23
  • 1
    \$\begingroup\$ No, you are not binding a function to a shorthand. You are evaluating an expression (which in turn calls a function) and binding the result to a local. Then you are referring to that local which is the same as referring to the value it is bound to. Clojure, like any Lisp, is eagerly evaluated, so binding a local to an expression does not defer its evaluation. But even in real lazy languages like Haskell binding an expression to a local this way will still evaluate the expression only once - these languages usually use "call by need" evaluation strategy. \$\endgroup\$
    – Yuri Steinschreiber
    Jul 28, 2016 at 15:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.