1
\$\begingroup\$

In "The Joy of Clojure", 2nd edition, code for quicksort is introduced on page 133 that I found hard to digest. I have rewritten it to make it clearer (at least to myself).

Here is the original:

(defn sort-parts-joc [work]
  (lazy-seq
    (loop [[part & parts] work]
      (if-let [[pivot & xs] (seq part)]
        (let [smaller? #(< % pivot)]
          (recur (list*
                  (filter smaller? xs)
                  pivot
                  (remove smaller? xs)
                  parts)))
        (when-let [[x & parts] parts]
            (cons x (sort-parts-joc parts)))))))

Here is the rewritten code:

(defn sort-parts-explicit-lazy [work]
   (lazy-seq        
      (loop [loopwork work]
         (let [[ part & partz ] loopwork ]
            (if-let [[pivot & valuez] (seq part)]
                  (let [ smaller? #(< % pivot)
                         smz      (filter smaller? valuez)
                         lgz      (remove smaller? valuez)
                         nxxt     (list* smz pivot lgz partz) ]
                        (recur nxxt))
                  (if-let [[oldpivot & rightpartz] partz]
                          (cons oldpivot (sort-parts-explicit-lazy rightpartz))                    
                          []))))))

Testing:

(require '( clojure test ))
(clojure.test/is (is-sorted (sort-parts-explicit-lazy [[]])))
(clojure.test/is (is-sorted (sort-parts-explicit-lazy [[1]])))
(clojure.test/is (is-sorted (sort-parts-explicit-lazy [[1 2]])))
(clojure.test/is (is-sorted (sort-parts-explicit-lazy [[1 2 3]])))
(clojure.test/is (is-sorted (sort-parts-explicit-lazy [[3 2 1]])))
(clojure.test/is (is-sorted (sort-parts-explicit-lazy [[3 3 3]])))

So, it works.

Both functions are essentially the same.

However I have a bad feeling about this. The simultaneous use of recur and full recursion, with the full recursion path "leaving" the loop in its middle in the same function feels weird, like unstructured code dropping a good, fat GOTO.

Here is the expression tree for reference:

quicksort function expression tree

We are far from from beta-reduction here. The "reduction" can only be understood using explicit instruction flow semantics. Okay, reality meets platonic ideals.

Is the loop-recur/full-recursion supposed to look like this? Is it a style problem that can be improved?

\$\endgroup\$
2
\$\begingroup\$

As you have already noticed, this can be viewed as a case of mutual recursion. To demonstrate this I give the following mutually recursive definitions:

(defn sort-parts [work] (lazy-seq (sp-loop work)))

(defn sp-loop [[part & parts]]
  (if-let [[pivot & xs] (seq part)]
    (sp-loop ;or recur for tco
      (let [smaller? #(< % pivot)]
        (list*
          (filter smaller? xs)
          pivot
          (remove smaller? xs)
          parts)))
    (when-let [[x & parts] parts]
      (cons x (sort-parts parts)))))

Because sp-loop is needed only in one place inside sort-parts, we can replace the previous with the following:

(defn sort-parts [work]
  (lazy-seq
    ((fn sp-loop [[part & parts]]
       (if-let [[pivot & xs] (seq part)]
         (sp-loop ;or recur for tco
           (let [smaller? #(< % pivot)]
             (list*
               (filter smaller? xs)
               pivot
               (remove smaller? xs)
               parts)))
         (when-let [[x & parts] parts]
           (cons x (sort-parts parts)))))
     work)))

Of course, if we use recur, sp-loop can be anonymous. But instead of defining and calling an anonymous function which only executes a loop, we can explicitly write a loop, arriving this way at the definition given in the book.

Moving further, noticing that in the mutually recursive definitions there is very little code inside sort-parts apart from the call of sp-loop (this call is just being wrapped in a LazySeq's thunk), we can define qsort using only one recursively defined function and no (explicit) loops, as shown below:

(defn qsort [xs]
  (lazy-seq
    ((fn sort-parts [[part & parts]]
       (if-let [[pivot & xs] (seq part)]
         (recur ;or sort-parts for no tco
           (let [smaller? #(< % pivot)]
             (list*
               (filter smaller? xs)
               pivot
               (remove smaller? xs)
               parts)))
         (when-let [[x & parts] parts]
           (cons x (lazy-seq (sort-parts parts))))))
     (list xs))))

And if we drop laziness, we can use just one loop:

(defn qsortv [xs]
  (loop [done []
         [part & parts] (list xs)]
    (if-let [[pivot & xs] (seq part)]
      (recur
        done
        (let [smaller? #(< % pivot)]
          (list*
            (filter smaller? xs)
            pivot
            (remove smaller? xs)
            parts)))
      (if-let [[x & parts] parts]
        (recur (conj done x) parts)
        done))))

Finally, in this question you can see a similar case of mutual recursion and laziness but without tail calls.

\$\endgroup\$
  • \$\begingroup\$ That's pretty extensive. \$\endgroup\$ – David Tonhofer Jul 4 at 13:25
2
\$\begingroup\$

We are far from from beta-reduction here. The "reduction" can only be understood using explicit instruction flow semantics.

No. You have chosen to interpret loop and recur in this way, but that is not how Clojure understands them.

  • recur is simply a flag for a tail-recursive call, functional as you like.
  • loop is a gloss on defining and applying a function.

We could define loop as a macro in terms of fn:

(defmacro loop [bindings & expressions]
  (let [[bindees values] (->> bindings
                              (partition 2)
                              (apply map vector))]
    `((fn ~bindees ~@expressions) ~@values)))

The real loop macro checks the syntax of bindings. I've not bothered. And it handles destructuring explicitly. I've left it for fn to do.

\$\endgroup\$
  • \$\begingroup\$ Ok. I have actually moved the deconstruction in loop further down for "beginner's clarity" after I printed out work and noticed that it never changed in the "loop" and that I had better use what's on the left side. And having many things happen at once that I don't really can be sure of and not having "asserts" makes me nervous. \$\endgroup\$ – David Tonhofer Jul 1 at 17:24
  • \$\begingroup\$ I get it. So maybe the glossed-over "loop" function should be made explicit, then we could have the recursive call tree TOPF--calls-->LOOPF--calls-->(LOOPF or TOPF). This is more verbose but more expository for beginners. \$\endgroup\$ – David Tonhofer Jul 1 at 17:28
  • \$\begingroup\$ @DavidTonhofer Clojure is not a pure functional language. My point is that loop and recur don't make it any less pure. The former is a piece of syntactic sugar simple enough to be expressed as a three line macro. The latter is an implementation hint/instruction. By the way, I'm sorry to say that I don't know what TOPF or LOOPF mean. \$\endgroup\$ – Thumbnail Jul 2 at 23:29
  • \$\begingroup\$ Ah, soory. Just "top function" and "loop function". I should be clearer... \$\endgroup\$ – David Tonhofer Jul 4 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.