Reduce All the Things!

Posted on   |   In

Nobody can deny it, Functional Programming - capital FP, as in the paradigm - is hot right now. Even Java, the prime example of Object-Oriented Programming, has added lambdas (or as you might know them, JS folks, anonymous functions). This recent explosion in popularity has led to more interest in writing code in a declarative, functional style, and means knowing how to structure algorithms and applications in this new style.

At another time I'll talk about this style of programming in general, but today I want to talk about the one helper function that seems to give lots of beginners fits: reduce Conceptually, a reduce or fold is pretty easy to understand. You take a list of some values, and starting from one side, combine the values until you're have one value representing the combined list.

Since I'm sure many of you have read that and it didn't help at all, let's try walking through this process in a familiar way.

Let's take a list of numbers:

1
1, 2, 3, 4, 5

And say we want to add them together. How would you write that out? Probably something like:

1
2
3
4
1  + 2 = 3
3  + 3 = 6
6  + 4 = 10
10 + 5 = 15

Do you notice any pattern here? The solution (right of the equals sign) to each line is the new first value for the next operation. Let's examine how you might write a simple program that computers this same answer:

Add an Array
1
2
3
4
5
6
7
8
9
var arr = [1, 2, 3, 4, 5];
function addList(arr) {
  var sum = 0;
  for (var i=0; i<arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}
console.log(addList(arr)); // 15

Pretty straightforward, right? But break down some of assumptions we've made.

  1. Since we need an ordered list, we have to accept an array
  2. Our sum can always start at 0

Doesn't seem like much, but both are significant. The first is that since our order does matter, this operation only makes sense on an array (objects in Javascript not having any implied order). We can prove this but changing the addition to subtraction.

Subtract an Array
1
2
3
4
5
6
7
8
9
10
11
12
var arr = [1,2,3,4,5];
var rev = arr.slice().reverse();

function subtractList(arr) {
  var ans = 0;
  for (var i=0; i<arr.length; i++) {
    ans -= arr[i];
  }
  return ans;
}
console.log(subtractList(arr)); // -15
console.log(subtractList(rev)); // -15

Well... wait. Is that right? If we write these out by hand again:

1
2
3
4
5
6
7
8
9
1  - 2 = -1
-1 - 3 = -4
-4 - 4 = -8
-8 - 5 = -13

5  - 4 = 1
1  - 3 = -2
-2 - 2 = -4
-4 - 1 = -5

Those aren't -15. What's going wrong? Our second assumption up above, that we're safe starting from zero, doesn't apply. In fact, we don't want to assume any starting value, right? When we work by hand, we use the first item in our list. We can do that via code pretty easily.

Fixed Subtract an Array
1
2
3
4
5
6
7
8
9
10
11
12
var arr = [1,2,3,4,5];
var rev = arr.slice().reverse();

function subtractList(arr) {
  var ans = arr[0];
  for (var i=1; i<arr.length; i++) {
    ans -= arr[i];
  }
  return ans;
}
console.log(subtractList(arr)); // -13
console.log(subtractList(rev)); // -5

Awesome, right answers. Now, as you're probably used to doing if you've been implementing these higher-order helper functions, we want to remove the operation from the function we're writing, and instead take a callback that defines how to combine the two values. Let's examine how & why this works, first by modifying the adding function a bit:

Add an Array v2
1
2
3
4
5
6
7
8
9
var arr = [1, 2, 3, 4, 5];
function addList(arr) {
  var sum = arr[0];
  for (var i=1; i<arr.length; i++) {
    sum = sum + arr[i];
  }
  return sum;
}
console.log(addList(arr)); // 15

Did you spot the little change? It's on line 5 above. Instead of using the shorthand +=, I switched it around to the long form. Now it mimics how it looks when we wrote the steps out by hand.

At this point I want you to stop and consider that + itself is a function. Sure, it doesn't look like what you traditionally think of as a function. But if you think of it as taking arguments from the left and right side of itself (that's called an infix operator), you can easily imagine it rewritten to look like +(sum, arr[i]). Expanding from that, what if we write our own add function and use that in lieu of the built-in +:

Add an Array v3
1
2
3
4
5
6
7
8
9
10
11
12
var arr = [1, 2, 3, 4, 5];
function add(a,b) {
  return a+b;
}
function addList(arr) {
  var sum = arr[0];
  for (var i=1; i<arr.length; i++) {
    sum = add(sum, arr[i]);
  }
  return sum;
}
console.log(addList(arr)); // 15

Nothing has changed in how we compute our answer, but we've restructured the logic. Hopefully you're seeing where I'm going with this: What would it look like if we write a function that takes both a list and an operation? Could we change that last code a bit and have it work for all the tests we've used so far?

Wait... This is Reduce!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var arr = [1, 2, 3, 4, 5];
var rev = arr.slice().reverse();
function add(a,b) {
  return a+b;
}
function subtract(a,b) {
  return a-b;
}
function combineList(arr, operation) {
  var ans = arr[0];
  for (var i=1; i<arr.length; i++) {
    ans = operation(ans, arr[i]);
  }
  return ans;
}
console.log(combineList(arr, add)); // 15
console.log(combineList(arr, subtract)); // -13
console.log(combineList(rev, subtract)); // -5

Coming together nicely now - believe it or not, this is a working, simple reduce! Try to add an optional starting value (eg: I want to start adding my list at 1000) and see how else you could write the looping logic (think recursion and other functional helpers you might see in Lodash). Check out Reduce All The Things part 2 for solutions and discussion if you get stuck!