Reduce reduce!

06 Mar 2012

In the past, I’ve often found myself regularly confused by the meaning of the humble reduce function, a stalwart of the functional programming world. But recently, I’ve been using it more and more often as I’ve become more and more accustomed to recognising the patterns that it is designed to replace.

Most tutorials on the topic tend to trot out the classic example of implementing the sum function (which is oddly absent from the Clojure standard libraries)

(reduce + 0 (range 10))
;=> 45

But what does this actually mean? What is going on here? Well to gain an understanding I decided to implement my version of sum by breaking the problem down and implementing it myself.

(defn my-sum [coll]
  (loop [accumulator 0 coll coll]
    (if (empty? coll)
      accumulator
      (recur (+ accumulator (first coll)) (rest coll)))))
;=> (my-sum (range 10))
;=> 45

So in effect, my implementation sets up an accumulator (starting at zero) and loops through the sequence adding the first item on each iteration to the accumulator to eventually yield when the sequence has been exhausted.

This is a lot of code to write just to sum some numbers together, and what happens if I want to write a my-product function? I’d have to create a new function with the same code but replace the + with *.

No one likes repeating code, but in both cases, the pattern is generally the same: -

With that in mind we can use the above pattern and make it more generic and re-usable for multiple uses.

(defn suck-sequence [f accumulator coll]
  (loop [accumulator accumulator coll coll]
    (if (empty? coll)
      accumulator
      (recur (f accumulator (first coll)) (rest coll)))))
;=> (suck-sequence + 0 (range 10)) ; sum
;=> 45
;=> (suck-sequence * 1 [1 2 3 4 5]) ; product 
;=> 120

Note I’ve named it suck-sequence because the process ‘sucks’ each value from the top of the sequence until it’s empty!

This is, in essence, reduce!

While the underlying code in Clojure may be implemented slightly differently, the core concepts described above are generally the same. So if we translate our loop/recur solution for sum to reduce

(reduce (fn [accumulator first-item] (+ accumulator first-item)) 0 (range 10))

You can see we’ve got rid of a lot of the boilerplate we needed before. No longer do we need to manage the flow through the sequence by passing (rest coll) to the loop as reduce handles that for us.

However you’ll notice that the above example doesn’t entirely match what we started out with, the higher-order function passed to reduce seems pretty explicit in its definition. By default, reduce requires a function that accepts two arguments (the accumulator and the first item of the sequence), so we can effectively reduce (excuse the pun) the code by just passing the function name and letting Clojure apply the arguments accordingly. Seeing as + accepts multiple arguments, we can just pass that instead.

(reduce + 0 (range 10))

How about that my-product function?

(reduce * 1 [1 2 3 4 5])

The accumulator doesn’t have to be a number either, it can be anything you want to be! Take this rather contrived example to implement reverse using reduce

(reduce (fn [acc first-item] (conj acc first-item)) '() (range 10))
;=> (9 8 7 6 5 4 3 2 1 0)

Or more succinctly…

(reduce conj '() (range 10))

Pretty neat right? One thing I’ve taken away from this is the fact that a lot of every day programming tasks have been encapsulated into generic functions like map, filter and reduce that remove the need to write boilerplate code, using higher order functions to achieve the desired result.