My Journey To Understanding Function Composition

Special restrictions: comp

1
2
3
4

(= [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"))

So, whenever the exercise forbids use of certain function(s), that basically means I have to write my version of that function. By looking at the tests I have quickly come up with:

1
2
3

(fn my-comp [f g]
  (fn [x]
    (f (g x))))

I knew right away that it would only pass the first two tests, since it accepts fixed number of functions (2), and only one argument, but I had to start somewhere. The next thing was how to implement my-comp function to accept variable number of arguments. Clojure has an easy way for this, by using & in front of args (or however we want to call our collection of arguments). But, that means I cannot implement my function the same way as above, since I don’t know how many arguments I’ll have. The first method I reach for in those situations is loop/recur. After a while I hacked this solution that works:

1
2
3
4
5
6
7

(fn my-comp2 [& fns]
  (fn [& xs]
    (loop [xs (apply (last fns) xs)
           fns (rest (reverse fns))]
      (if (seq fns)
        (recur ((first fns) xs) (rest fns))
        xs))))

It accepts multiple function arguments, and the inner function accepts variable number of arguments. It also passes all four tests, so I might consider I completed the task. Although this solution works, there are several problems with it. Let’s call this function with 1st test case ((my-comp2 rest reverse) [1 2 3 4]) and analyze this function:

• First, we define a function my-comp2 and we see that it accepts multiple arguments [& fns]
• Next, the inner function accepts multiple arguments [& xs]
• Then we encounter a loop where the following values are bound:
  • xs (apply (last fns) xs) - I’m applying the last argument from fns, which is reverse to my xs collection, which is [1 2 3 4] so the value of xs is [4 3 2 1]
  • fns (rest (reverse fns)) - Since functions have to be applied right-to-left, I needed to reverse my sequence of functions, and to leave out the function I already applied to arguments when I declared xs binding.
• Next is (if (seq fns)... which I first wrote as (if fns (then branch) (else branch)) but I got werid Execution error (NullPointerException) (i found out that if call causes this error by using CIDER Debugger). I wasn’t sure why I got this error, since fns should be a seq AFAIK. I managed to “solve” it by (seq fns). It happens when rest is applied to fns containing one argument, and it returns empty seq, which evaluates to true, and then ((first fns) xs) produces this error. Calling seq on empty sequence returns nil, and we get expected results.
• As long as we have functions in our seq this code executes: (recur ((first fns) xs) (rest fns)) - New value of xs is the result of first function in line executed on current xs value, and new value of fns is everything except the function that was just executed on xs
• When there are no functions left to execute (our fns is empty), we just return our xs collection, which is what we need to pass the exercise.

This solution works, but there are several problems with it. Mainly, when the xs and fns are declared. For xs the (apply (last fns) is used, which has to go through the whole seq of functions in order to get to last and execute it. Then, when fns is declared the reverse function is applied, which is not lazy, so it rearranges our seq, and proceeds to apply the rest function on result. Although this way I was able to successfully complete the exercise I knew there must be a better way to implement this function. So I thought maybe it wasn’t a bad idea to write a function that will behave differently depending on the number of functions it got. After some time I came up with:

1
2
3
4
5
6
7
8
9

(fn my-comp3
  ([f]
   (fn [& xs]
     (apply f xs)))
  ([f g]
   (fn [& xs]
     (f (apply g xs))))
  ([f g & fns]
   (reduce my-comp3 (my-comp3 f g) fns)))

Let’s analyze. We have three function bodies. First, which gets only one function and applies it to any number of arguments this function gets. Second, and pretty similar to my-comp at the beginning of this article, gets two functions, applies second function to arguments it gets, then calls first function on the result of applying second function to xs. Third body is most interesting, as it is recursive call to the function itself. It accepts first function as f, second as g and remaining functions in fns seq. The body itself (reduce my-comp3 (my-comp3 f g) fns) is the most amazing thing. Since fn [& xs] is called inside of fn [f g], reduce first needs to get to the last function, and then it will get applied to xs, so imagine our fns consists of (fn1 fn2 fn3 fn4 fn5), then reduce will produce a call that looks like (fn1 (fn2 (fn3 (fn4 (apply fn5 xs))))). This looks like much cleaner & more efficient solution.

I hope you had a nice time reading my experience with this. Feel free to comment and to leave any suggestion on how would you approach solving this problem.