Clojure: Implementing the comp function

Question

4Clojure Problem 58 is stated as:

---

Write a function which allows you to create function compositions. The parameter list should take a variable number of functions, and create a function applies them from right-to-left.

(= [3 2 1] ((__ rest reverse) [1 2 3 4]))

(= 5 ((__ (partial + 3) second) [1 2 3 4]))

(= true ((__ zero? #(mod % 8) +) 3 5 7 9))

(= "HELLO" ((__ #(.toUpperCase %) #(apply str %) take) 5 "hello world"))

Here __ should be replaced by the solution.

In this problem the function comp should not be employed.

---

A solution I found is:

(fn [& xs]
  (fn [& ys]
    (reduce #(%2 %1)
            (apply (last xs) ys) (rest (reverse xs)))))

It works. But I don't really understand how the reduce works here. How does it represent (apply f_1 (apply f_2 ...(apply f_n-1 (apply f_n args))...)?

Answer 1

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"

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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