Going Functional: Reduce

Reduce (a.k.a. foldl) is one of my all-time favorite higher-order functions. It’s kinda sorta the crane stance of the functional style kung-fu: you don’t want to use it a lot but when you do it can save the day.

Every now and then you come across an array and you want to combine its items somehow to compute a value. But the final result depends on the intermediate results of each step so you need to use an acumulator that holds those. And things get messy.

That’s where reduce shines.

You give it an array, a function and an initial value and it builds up a return value for you by recursively applying the function to each of the items while passing in the intermediate result.

Gee, that sounds complicated

But it’s not, really. All that happens is you take the initial value and combine it with the first item of the array to get an intermediate result (let’s call it result1). Then you you combine result1 with the second item of the array and get result2. And so on and so forth until you combine with the last item N and get resultN (which is the final one). That’s it, no rocket science here.

A few real-world examples should make this clear.

**Compute a sum **of an array of integers:

sum = _.reduce [1, 3, 5, 7, 9], ((memo, i) -> memo + i), 0

…which basically resolves into:

( ( ( ( ( 0 + 1 ) + 3 ) + 5 ) + 7 ) + 9 )

The third parameter to reduce is the initial value used to ‘seed’ the computation; the iterator function is always called with an intermediate result – in the case of the first call the intermediate result is simply the initial value. In this case, we want a sum of ints so the initial value should be the additive identity (i.e. zero).

Flatten an array of arrays:

flat = _.reduce [[1, 2], [3, 4], [5, 6]], ((memo, arr) -> memo.concat arr), []

…which is an equivalent of:

( ( [].concat( [1, 2] ) ).concat( [3, 4] ) ).concat( [5, 6] )

**Recursively access **a property of an object:

item = {post: author: id: '42'}
_.reduce 'post.author.id'.split('.'), ((obj, part) -> obj[part]), item

…which is effectively the same as:

( ( ( item['post'] )['author'] )['id'] )

foldl vs. foldr

If you take a look at the examples above you’ll probably notice they’re all left-associative – the combinations always start with the first item in the array.

What if you wanted right-associativity (i.e., start with the last item)? Well, in such a case you’re looking for a function conveniently named foldr or reduceRight (in Underscore.js). Unfortunately, foldr is more useful in languages with lazy evaluation such as Haskell (foldr recurses into an argument and hence can be used on infinite lists).

Next in the series we’ll cover a handful of useful little utility functions like ‘all’ and ‘any’.