Can I use `recur` in this implementation of function composition in Clojure?

Question

Consider this simple-minded recursive implementation of comp in Clojure:

(defn my-comp
  ([f]
   (fn [& args]
     (apply f args)))
  ([f & funcs]
   (fn [& args]
     (f (apply (apply my-comp funcs) args)))))

The right way to do this, I am told, is using recur, but I am unsure how recur works. In particular: is there a way to coax the code above into being recurable?

Answer 1

evaluation 1

First let's visualize the problem. my-comp as it is written in the question will create a deep stack of function calls, each waiting on the stack to resolve, blocked until the the deepest call returns -

((my-comp inc inc inc) 1)
((fn [& args]
     (inc (apply (apply my-comp '(inc inc)) args))) 1)

(inc (apply (fn [& args]
                (inc (apply (apply my-comp '(inc)) args))) '(1)))

(inc (inc (apply (apply my-comp '(inc)) '(1))))

(inc (inc (apply (fn [& args]
                     (apply inc args)) '(1))))

(inc (inc (apply inc '(1)))) ; ⚠️ deep in the hole we go...
(inc (inc 2))
(inc 3)
4

tail-recursive my-comp

Rather than creating a long sequence of functions, this my-comp is refactored to return a single function, which when called, runs a loop over the supplied input functions -

(defn my-comp [& fs]
  (fn [init]
    (loop [acc init [f & more] fs]
      (if (nil? f)
          acc
          (recur (f acc) more))))) ; 🐍 tail recursion

((my-comp inc inc inc) 1)
;; 4

((apply my-comp (repeat 1000000 inc)) 1)
;; 1000001

evaluation 2

With my-comp rewritten to use loop and recur, we can see linear iterative evaluation of the composition -

((my-comp inc inc inc) 1)
(loop 1 (list inc inc inc))
(loop 2 (list inc inc))
(loop 3 (list inc))
(loop 4 nil)
4

multiple input args

Did you notice ten (10) apply calls at the beginning of this post? This is all in service to support multiple arguments for the first function in the my-comp sequence. It is a mistake to tangle this complexity with my-comp itself. The caller has control to do this if it is the desired behavior.

Without any additional changes to the refactored my-comp -

((my-comp #(apply * %) inc inc inc) '(3 4)) ; ✅ multiple input args

Which evaluates as -

(loop '(3 4) (list #(apply * %) inc inc inc))
(loop 12 (list inc inc inc))
(loop 13 (list inc inc))
(loop 14 (list inc))
(loop 15 nil)
15

right-to-left order

Above (my-comp a b c) will apply a first, then b, and finally c. If you want to reverse that order, a naive solution would be to call reverse at the loop call site -

(defn my-comp [& fs]
  (fn [init]
    (loop [acc init [f & more] (reverse fs)] ; ⚠️ naive
      (if (nil? f)
          acc
          (recur (f acc) more)))))

Each time the returned function is called, (reverse fs) will be recomputed. To avoid this, use a let binding to compute the reversal just once -

(defn my-comp [& fs]
  (let [fs (reverse fs)] ; ✅ reverse once
    (fn [init]
      (loop [acc init [f & more] fs]
        (if (nil? f)
            acc
            (recur (f acc) more))))))