The accumulator pattern

No! Not that!

I’m sure that there are tons of available articles on this subject, yet I have an urge to try and tackle it myself. To be more specific, I think this is the perfect introduction to recursive functions. Many developers seems to hate recursion, and, to be perfectly honest, I’m one of them. The only place where they really shine is traversing through, or creating tree-like structures. Otherwise, I stick with imperative style. And yet, recursion is actually really simple, and thus, this article is born. I’m a simple man as well, not an Einstein…

I’ll be using JavaScript for examples, simply because its almost like Esperanto for programming languages. There will also be some amount of TypeScript, because types can help a lot in understanding. Plus, JavaScript has its own implementation of accumulator function, which is reduce() .

Before checking JS reduce, let’s try and implement our own. I’ll start by showing function declaration (in TypeScript) and than do some explanation. Again, I think that the types are really helpful here. So, our own reduce declaration:

Quite a line to unpack. Starting with declaration we have:

function reduce<T, S>

So this part tells us that we will be working with 2 major types: T and S . They are generic, but the whole function revolves around them. Now the function parameters:

array: T[]
state: S
actionFn: (state: S, x: T) => S

So reduce first takes an array of T , then it takes some initial state of type S , then it takes a function which has S and a single element of the array to produce a new state.

Finally reduce<T, S>(...): S returns S . This means 2 things. First, your output will be of the same data type as initial state, second, we can feed the output as new initial state to another reduce() invocation.

Ungh… That’s a mouthful. Here is an easier way to digest all of this, and I guarantee that you already know it. Summing numbers in array:

We are relatively close. If you invoke this function like sum(arr, 0) you will get the sum of the array. Notice that you have the liberty to start the sum from any number. 0, -1, 1000, -1284… Whatever. That’s the initial state. Now, this function can only sum the numbers. What we want to do is to replace that addition function (a, b) => a + b to be any function that satisfies the

(a: S, b: T) => S signature. So that function becomes the parameter as well, and we get our first version of reduce:

This is a valid iterative implementation of accumulator pattern. Time to make it recursive. Before jumping into that, one neat trick on how to separate array’s first element from the rest:

This will help to make the code cleaner. Ok, recursive version one:

Instead of relying on for/foreach to get a specific element, we just split the array to head/tail parts in each call. We also don’t mutate the state. Here’s a visual intuition of the process for summing numbers in [1, 2, 3]:

Just a little nitpicking before proceeding. I don’t like how actionFn is passed down as a parameter recursively. This can be solved easily. We can create inner function, with exactly the same logic, but it won’t take actionFn as parameter. Since they will be in the same scope, the inner function can still use it. Recursive implementation version two:

I’ve also skipped explicitly creating then returning results

That’s it. This is the full implementation. Again, JS version has some overloads. Let’s see how to use both ours, and JS version. Summing of numbers first:

Almost the same, except JS has a clear advantage that you can dot into the reduce function. Also, it is almost always better to pass actionFn as a lambda, instead of declaring it like I did here.

Finally, the fun actually begins. You can use reduce() instead of map() and filter() functions… Let’s see how:

Notice that map() and filter() return Array object as result. Therefore, our initial state for reduce also must be of Array type. Remember, reduce() is generic. It allows you to return any data structure you like.

Side note: just because you can use reduce() instead of map(), filter() doesn’t mean that you should. I’m just showing examples here to make you comfortable with using it. In the real world, since reduce() can return anything, you must dig into the implementation to see what it actually does. With map(), filter() you know something is being mapped or filtered without checking. Less cognitive overload.

And last two examples now. Try running this snippet:

let arr = [1, 2, 3];
let sum = arr.reduce((state, x, i) => {
    console.log(`Step ${i + 1}:`);
    console.log(`${state} + ${x} = ${state + x}`);
    return state + x;
}, 0);

It uses one of those overloads I’ve mentioned (i parameter). It will print the steps of execution to the console. Perfect if you’re still unsure of what is going on.

Lastly, some… err… real world usage. I often use reduce() to group data:

Now I can easily check if it’s a sausage party or not. Accumulator for the win!

Hope you found this informative and useful.