Clojure: Implementing the comp function

Let's try modifying that solution in 3 stages. Stay with each for a while and see if you get it. Stop if and when you do lest I confuse you more.

First, let's have more descriptive names

(defn my-comp [& fns]
  (fn [& args]
    (reduce (fn [result-so-far next-fn] (next-fn result-so-far))
      (apply (last fns) args) (rest (reverse fns)))))

then factor up some

(defn my-comp [& fns]
  (fn [& args]
    (let [ordered-fns (reverse fns)
          first-result (apply (first ordered-fns) args)
          remaining-fns (rest ordered-fns)]
    (reduce 
      (fn [result-so-far next-fn] (next-fn result-so-far))
      first-result
      remaining-fns))))

next replace reduce with a loop which does the same

(defn my-comp [& fns]
  (fn [& args]
    (let [ordered-fns (reverse fns)
          first-result (apply (first ordered-fns) args)]
      (loop [result-so-far first-result, remaining-fns (rest ordered-fns)]
        (if (empty? remaining-fns)
            result-so-far
            (let [next-fn (first remaining-fns)]
              (recur (next-fn result-so-far), (rest remaining-fns))))))))

My solution was:

(fn [& fs]
  (reduce (fn [f g]
            #(f (apply g %&))) fs))

Lets try that for:

((
  (fn [& fs]
    (reduce (fn [f g]
              #(f (apply g %&))) fs)) 

  #(.toUpperCase %) 
  #(apply str %) 
  take) 

  5 "hello world"))

fs is a list of the functions:

#(.toUpperCase %) 
#(apply str %) 
take

The first time through the reduce, we set

f <--- #(.toUpperCase %)
g <--- #(apply str %)

We create an anonymous function, and assign this to the reduce function's accumulator.

#(f (apply g %&)) <---- uppercase the result of apply str

Next time through the reduce, we set

f <--- uppercase the result of apply str
g <--- take

Again we create a new anonymous function, and assign this to the reduce function's accumulator.

#(f (apply g %&)) <---- uppercase composed with apply str composed with take

fs is now empty, so this anonymous function is returned from reduce.

This function is passed 5 and "hello world"

The anonymous function then:

• Does take 5 "hello world" to become (\h \e \l \l \o)
• Does apply str to become "hello"
• Does toUppercase to become "HELLO"

Here's an elegent (in my opinion) definition of comp:

(defn comp [& fs]
  (reduce (fn [result f]
            (fn [& args]
              (result (apply f args))))
          identity
          fs))

The nested anonymous functions might make it hard to read at first, so let's try to address that by pulling them out and giving them a name.

(defn chain [f g]
  (fn [& args]
    (f (apply g args))))

This function chain is just like comp except that it only accepts two arguments.

((chain inc inc) 1)              ;=> 3
((chain rest reverse) [1 2 3 4]) ;=> (3 2 1)
((chain inc inc inc) 1)          ;=> ArityException

The definition of comp atop chain is very simple and helps isolate what reduce is bringing to the show.

(defn comp [& fs]
  (reduce chain identity fs))

It chains together the first two functions, the result of which is a function. It then chains that function with the next, and so on.

So using your last example:

((comp #(.toUpperCase %) #(apply str %) take) 5 "hello world") ;=> "HELLO"

The equivalent only using chain (no reduce) is:

((chain identity
        (chain (chain #(.toUpperCase %)
                      #(apply str %))
               take))
 5 "hello world")
;=> "HELLO"

At a fundamental level, reduce is about iteration. Here's what an implementation in an imperative style might look like (ignoring the possibility of multiple arities, as Clojure's version supports):

def reduce(f, init, seq):
    result = init
    for item in seq:
        result = f(result, item)
    return result

It's just capturing the pattern of iterating over a sequence and accumulating a result. I think reduce has a sort of mystique around it which can actually make it much harder to understand than it needs to be, but if you just break it down you'll definitely get it (and probably be surprised how often you find it useful).