Clojure: Implementing the comp function

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).

Here is my solution:

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

I like A. Webb's solution better, though it does not behave exactly like comp because it does not return identity when called without any arguments. Simply adding a zero-arity body would fix that issue though.

Consider this example:

(def c (comp f1 ... fn-1 fn))

(c p1 p2 ... pm)

When c is called:

• first comp's rightmost parameter fn is applied to the p* parameters ;

• then fn-1 is applied to the result of the previous step ;

  (...)

• then f1 is applied to the result of the previous step, and its result is returned

Your sample solution does exactly the same.

• first the rightmost parameter (last xs) is applied to the ys parameters:

  (apply (last xs) ys)
  

• the remaining parameters are reversed to be fed to reduce:

  (rest (reverse xs))
  

• reduce takes the provided initial result and list of functions and iteratively applies the functions to the result:

  (reduce #(%2 %1) ..init.. ..functions..)