One intriguing problem on 4clojure is writing
comp from scratch. Before we discuss how to do that, let’s start by understanding how Clojure’s
comp or “compose” works.
If we wanted to write a function to reverse a list, and then take only the rest of that reversed list, we could write a function to do just that:
(defn reverse-and-take-rest [numbers] (rest (reverse numbers))) (reverse-and-take-rest [1 2 3 4]) ;; => (3 2 1)
comp function, we have another and more concise way to achieve the same result:
(def reverse-and-take-rest (comp rest reverse)) (reverse-and-take-rest [1 2 3 4]) ;; => (3 2 1)
comp will work right to left applying each function. In other words,
reverse is called first and
rest is called second.
One other important detail is how
comp behaves when it receives no functions:
((comp) [1 2 3 4]) ;; => [1 2 3 4]
In the simplest case with no functions,
comp will use the
identity function, handing back whatever it received. We will return to this detail in a moment.
Now that we understand how
comp works, how would we write it from scratch? Having worked through The Little Schemer, my first inclination is to use recursion with Clojure’s
recur. Although idiomatic Clojure code rarely uses
loop, it’s a good place to start.
First, we know how our function should behave:
((my-comp rest reverse) [1 2 3 4]) ;; => (3 2 1)
Even though the example above shows two functions, in usage, it will have to support any number of functions. So we’ll start by declaring a function which takes a variable number of arguments:
(defn my-comp [& all-fns] ;; body here )
Then, we can put the recursive structure in place using
recur. With each recursive step we will build up a new function while working through the list of functions passed to
my-comp. I have adopted a convention used in The Little Schemer and refer to the “accumulated function” as
acc-fn. The usual convention is to have an accumulator which as its name suggests accumulates the results of each recursive call.
(defn my-comp [& all-fns] (loop [fns all-fns acc-fn identity] ;; if base case, return the accumulated function ;; else keep recursing (recur)))
Recall that the base case of
comp is to return the
identity function. Here we have initialized our
identity for the case when
my-comp is called with no arguments.
With the basic skeleton in place, we can now establish the base case and start thinking about how each recursive step should work.
(defn my-comp [& all-fns] (loop [fns all-fns acc-fn identity] (if (empty? fns) acc-fn (recur (butlast fns) ;; create an accumulated function here ))
Once our collection of functions is empty, we know that we’re done and can return the resultant
acc-fn. Because we’ll apply the functions from right to left, we will use
butlast to recurse with all but the last function in the list. The
butlast function does exactly what its name implies:
(butlast '(rest reverse)) ;; => (rest) (butlast '(rest)) ;; => nil
Note that calling
butlast on a one-member sequence will return
nil. “But what about calling
(empty? nil),” you might ask, as will happen once we have recursed through all our functions and have finally reached the bottom of
my-comp. Fortunately, Clojure has us covered:
(empty? nil) ;; => true
So now that we have established our basic recursive structure with a base case and with a recur step to whittle down our list of functions, how we do build up an accumulated (and composed) function?
First, we know that we need to return a function that takes an argument. Second, we want to call our accumulated function with that argument. And third, we want to pass the result of the function call to our current function. Here’s what that looks like:
(defn my-comp [& all-fns] (loop [fns all-fns acc-fn identity] (if (empty? fns) acc-fn (recur (butlast fns) (fn [a] ((last fns) (acc-fn a)))))))
And with that, we have a simple but working version of
comp. The hardest part is thinking about how to build up the accumulated function. It helps to write out all the recursive steps to figure out just how to build up the accumulated function. As we’ve written
my-comp, our accumulated function will be as follows:
;; First frame (fn [a] (reverse (identity a))) ;; Second frame (fn [b] (rest ((fn [a] (reverse (identity a))) b))
At this point, it’s fairly easy to refactor our code to use
reduce instead of
(defn my-comp [& all-fns] (reduce (fn [acc-fn curr-fn] (fn [a] (acc-fn (curr-fn a))) identity all-fns))
reduce function takes three arguments: 1) a reducing function, 2) an initial argument passed to that reducing function as the first argument, and 3) a collection to reduce. The reducing function takes two arguments: the accumulated function passed from one step to the next, and an element from the collection. Within the reducing function, we have to do almost exactly what we did in the recursive function above: return a function composed of the accumulated function and the current function. Note that the order of invoking the accumulated function and the current function is reversed because
reduce works from left to right through a collection.
This is a good first step, but there is one flaw to
my-comp: it returns a composed function which only takes one argument. In Clojure, though,
comp returns a composed function which accepts a variable number of arguments. How can we fix our function to have the same behavior?
The key issue is the arity of the returned function within our reducing function:
(fn [a] (acc-fn (curr-fn a)))
If we instead change the signature to accept a variable number of arguments and apply the current function to those arguments, we have a solution. The entire
my-comp is now:
(defn my-comp [& all-fns] (reduce (fn [acc-fn curr-fn] (fn [& args] (acc-fn (apply curr-fn args))) identity all-fns))
While building up a more involved function like
my-comp, I find it helpful to start with a very simply recursive solution first to develop an understanding of the various details involved with a working solution. With a good understanding in place, it’s fairly simple to refactor the code, both to support variable arguments and to be idiomatic.