Combined looping and recursion when implementing Quicksort, using proper Clojure style

Question

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:

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?

Answer 1

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.

Answer 2

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.