Higher order functions and function composition

Functions in Clojure are first-class citizens. It means functions can be treated as values, stored in sequences and passed as arguments. Of course, not all functions expect other functions as arguments, but those that do are called higher order functions. One particularly useful higher order function is map. It takes two arguments:

  1. Function.
  2. Collection.

map applies the given function to each element of the given collection, and returns the new collection. Let's try this:

user=> (map inc (range 10))
(1 2 3 4 5 6 7 8 9 10)

inc itself is a simple incrementor: it takes a number and adds 1 to it. Above we've asked map to apply inc to each element of the range, this is why the result is a sequence from 1 to 10.

The result of this function call is a brand new sequence. The original sequence was not modified. In fact, data stuctures in Clojure are immutable, you can't ever change existing values, only create new ones. There are no variables in the common sense. This idea scares some people even more than parentheses do. You will soon see why immutable data structures is a good idea, which liberates and makes things much easier for us, programmers.

Wait... The result of calling map was a sequence, so we can apply inc to its elements again:

user=> (map inc (map inc (range 10)))
(2 3 4 5 6 7 8 9 10 11)

This works, but looks clumsy. What we're trying to do is to add 2 to each number, or, in other words, apply inc twice. Clojure allows us to build new functions from existing functions by using comp which stands for composition. comp is conceptually simple: pass any functions in the order you want, and it will return a new function which is the composition of them. comp applies the functions from right to left. "Any functions" can be the same function several times, which is what we want:

(comp inc inc)

The result of calling comp is a new function without a name. Nevertheless, we can immediately call it:

user=> ((comp inc inc) 4)
6

user=> ((comp inc inc) 9)
11

Let's plug it into the map call:

user=> (map (comp inc inc) (range 10))
(2 3 4 5 6 7 8 9 10 11)

This long expression can be unwrapped like this: "apply the result of composing two inc calls to the collection of numbers from 0 to 9."

Since functions can be treated as data, we can "store" this dynamically created function for future use by assigning it a name using def:

user=> (def dinc (comp inc inc))
#'user/dinc

user=> (dinc 2)
4

user=> (map dinc (range 5 8))
(7 8 9)

Another useful higher-order function is reduce. It takes two arguments:

  1. Function.
  2. Collection.

And consequently applies the given function to pairs of elements of the collection, reducing it into a single value. It's easier to show:

user=> (reduce + (range 10))
45

Expression (range 10) produces (0 1 2 3 4 5 6 7 8 9), and here we asked reduce to do the following:

  1. 0 + 1 -> 1
  2. 1 + 2 -> 3
  3. 3 + 3 -> 6
  4. 6 + 4 -> 10
  5. etc.

Which got us 45 in the end: the sum of all elements of the range.

The whole map or reduce call can be further treated as an element of a more complex composition. This can go on indefinitely: the nature of functions in Clojure makes everything extremely flexible. Note that we haven't created any new function manually yet. Let's do it after these short exercises.

Also, here's a short video visualization of map, reduce and another common higher order function called 'filter':

Exercises

Exercise 1. Use map to decrement all values of (13 49 12 34) by applying dec. Then, use reduce to multiply all values of the resulting sequence. Finally, increment the result by 2. Do it all in one line of code. You should get 209090 as the final result.

Exercise 2. Call range with such arguments so that it produces: 

(0 -1 -2 -3 -4 -5 -6 -7 -8 -9)

Exercise 3. Use reduce to get sums of two sequences: (45 931 13) and (63 19 5143). Use the sums to create a new list of two values. Then use map to increment both elements of the new list. You should get (990 5226) as the final result.

To create a list from expressions, use function list. Example:

user=> (list 1 2 3)
(1 2 3)

user=> (list (first '(3 4 5)) (last '(6 7 8)))
(3 8)