Higher Order Fun

There are not many things that programmers enjoy more than arguing about definitions. So it’s no wonder that terms like “functional programming” can have different meanings for different people. However, all the definitions I came across so far included that functions need to be “first-class”, i.e. they are no different from other basic data types (like numbers or strings) in that they can be stored in variables, passed as arguments, or returned as another function’s result.

Higher-order functions

A function which takes another function as an argument or returns a new function as its return value is called a “higher-order function”. One such function that many people will be familiar with is trusty old map. Here’s a basic example in Clojure.

(map inc (range 1 6))
;; => (2 3 4 5 6)

This takes the function inc (which not surprisingly increments a number) and applies it to every element in the range 1–5, yielding the sequence of numbers from 2 to 6.

Another nice feature of Clojure’s map function is that it can take more than one collection to map over. In that case it expects a function with the same arity (the number of arguments a function accepts) as the number of provided collections. Sounds complicated? Let’s look at an example!

First we define the infinite lazy sequence of natural numbers. You read that correctly, Clojure sequences are not evaluated until their values are actually needed, so it’s possible to construct theoretically infinite data structures.

(def naturals (iterate inc 1))
(take 5 natural)
;; (1 2 3 4 5)

Now how would we go about constructing a list of all squares from that? Well, a square is just a number multiplied by itself, something that can be very elegantly expressed with Clojure’s map function:

(def squares (map * naturals naturals))
(take 7 squares)
;; (1 4 9 16 25 36 49)

Here we construct the list of all squares by providing map with 2 collections (well, 2 copies of the same collection really) and the function * which will multiply the corresponding elements from each collection. We then use take to look at the first 7 squares and can be satisfied that everything worked as expected.

Onwards and upwards

Clojure is defined in terms of simple yet powerful abstractions, which combined with its pervasive use of basic data structures (lists, vectors, maps, sets) makes the language not only beautiful to read, but also a lot of fun to program in.

So let’s do something useful with what we learned about higher-order functions so far and implement a generic function analyze, which takes a sequence and an array of functions and then returns a map with the results of all the functions applied to the provided sequence (note: this function was inspired by an example in the excellent “Clojure for the Brave and True”).

(defn analyze
  "Expects a collection and a map of key/function pairs.
  Returns a map of key/function-applied-to-collection pairs."
  [collection analyzers]
  (into {} (map (fn [[k f]] {k (f collection)}) analyzers)))

Remember how we said that that in a functional programming languages functions can be used like any other data type? This is exactly what we are doing here, passing in a whole bunch of functions in the map (or hash or associative array depending on your background) analyzers. This is the actual collection that map will apply the provided anonymous function to.

In said anonymous function we destructure each key value pair, binding the key to k and the value (a function) to f. We then return a new one element map with the same key k and the result of applying f to the collection as the value.

The last piece of the puzzle is the function into, which combines all our newly returned maps into a single one.

Ready, set, action

Granted, if you’re a new to Clojure and/or functional programming, the above function can look a bit daunting at first. Let’s look at two examples that hopefully will clear things up a bit.

(let [sum #(reduce + %)
     avg #(/ (sum %) (count %))
     analyzers {:sum sum :avg avg}]
  (analyze (range 1 5) analyzers))
;; => {:sum 10, :avg 5/2}

Here we use let to bind an anonymous function for adding up a sequence of numbers to the name sum. We then use this newly created function to define avg, which will calculate the average for us. Finally we create a map that defines how we want our return value to look: the key :sum will be associated with the sum of all the collection’s elements, while :avg will tell us about their average. With all this done we finally call analyze providing the range of numbers from one to five and our analyzers map as arguments. As expected the returned map includes the correct sum and average (note that Clojure uses rational numbers for the sake of precision).

require '[clojure.string :as str])

(let [word-count #(-> % (str/split #"\s") (count))
      line-count #(-> % (str/split #"\n") (count))
      analyzers {:chars count :words word-count :lines line-count}]
  (analyze
   "this is a test string.\nit is also not very interesting."
   analyzers))
;; => {:chars 55, :words 11, :lines 2}

This example follows the same pattern we saw before: we first create two anonymous functions to calculate the word and line lengths, then put them in a map. Note that we also use Clojure’s built-in count function, which will return the number of elements in a sequence strings in Clojure are defined in terms of the sequence abstraction) to calculate the number of characters in our string. We then call analyze with a silly example string and our map of functions, and get a map including character, word, and line counts in return.

As can be seen from the above two examples, analyze is not picky at all. It doesn’t care how many functions you put into the analyzers map or what type of sequence collection is, it dutifully accepts whatever you hand it and performs its task. In fact the first argument doesn’t even have to be a sequence at all, so maybe the argument name wasn’t that well chosen ;-)

That’s it folks

While this short post barely scratched the surface, I hope the above examples illustrated how using first-class and higher-order functions can lead to very concise and expressive code. Together with Clojure’s well thought-out abstractions and core data types, many seemingly complex problems can be elegantly solved.