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)
Using the 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)
Note that 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 loop and 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 loop and 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 acc-fn to 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 loop and recur.
(defn my-comp [& all-fns]
(reduce
(fn [acc-fn curr-fn]
(fn [a]
(acc-fn (curr-fn a)))
identity
all-fns))
The 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.