Recursive approach to map and reduce: A thought experiment

In my early stages of learning Elixir, I had to write a recursive implementation of the functions map and reduce. It turned out to be a simple albeit extremely interesting exercise. I was struck by the elegance and simplicity of such implementations.

That got me thinking about how similar or different it would be to implement a recursive approach to these functions in JavaScript. So what follows are my thoughts on the matter, where I translate my implementations into JavaScript and think out loud about some differences between Elixir and JavaScript.

Map

Here's my quick implementation for map:

def map([], _func), do: []
def map([ head | tail ], func), do: [ func.(head) | map(tail, func) ]

This executes the function until it finds an empty list, at which point it returns the empty list. Until that point, it takes the fist element of the list, applies the given function to it, and maps the rest of the list.

My first attempt to implement this in JavaScript was a very naïve one. I did this:

const map = ([ head, ...tail ], func) => [
    func(head),
    map(tail, func)
]

If you pay more attention to detail than I, you'll probably have realised that this will cause a call stack overflow. Unlike Elixir, JavaScript doesn't support defining multiple clauses for a function. So, in order to translate it into JavaScript, we need a condition or some other way to exit the recursion:

const map = ([ head, ...tail ], func) => tail.length === 0
    ? func(head)
    : [ func(head), map(tail, func) ]

This is better. When map reaches the last element in the list, it simply applies the function to it and returns it. Again, because we can't just define multiple clauses for a function in JavaScript, the empty list as ending point doesn't really work. At least not with this parameter definition. However, if we did want to use an empty list as the stopping point (to keep it closer to the original version?), we could try something like this:

const map = (list, func) => list.length === 0
    ? []
    : [ func(list[0]), map(list.slice(1), func) ]

Here we're keeping the same exit point for the recursion. It generates almost the same result as the previous implementation, but the body of the function is a bit more cumbersome. I prefer the previous one, because there's no need to call slice or to pick the first element in list.

You may have already noticed that there is a problem with this map. Specifically, it returns a list with the processed value as the fist element and another list as the second. So the result is going to be a mess of nested lists:

const list = [ 1, 2, 3, 4, 5 ]
const double = x => x * 2
map(list, double) // -> [ 2, [ 4, [ 6, [ 8, 10 ] ] ] ]

Turns out that doing [ func(head), map(tail, func) ] in JavaScript isn't equivalent to doing [ func.(head) | map(tail, func) ] in Elixir. The pipe character in Elixir separates the value of an element and the pointer to the next element. So it is expected that the pointer will be to a list. The comma in JavaScript separates two elements in a list. So if the second element is a list, it will be a nested list.

Obviously, we don't want that. To try and fix it, we could take a hint from map's arguments and use the spread operator:

const map = ([ head, ...tail ], func) => tail.length === 0
    ? func(head)
    : [ func(head), ...map(tail, func) ]

But if we do that, the runtime will complain and say that map is not a function or its return value is not iterable. A quick fix would be to use concat instead:

const map = ([ head, ...tail ], func) => tail.length === 0
    ? func(head)
    : [ func(head) ].concat(map(tail, func))

This returns a list with the first element as the head, and concatenates a recursive call to include the following elements. Now it generates the proper result:

const list = [ 1, 2, 3, 4, 5 ]
const double = x => x * 2
map(list, double) // -> [ 2, 4, 6, 8, 10 ]

Although it doesn't seem much more complex, I like the implementation in Elixir a lot better. Mostly it's because I think this is ugly: [ func(head) ].concat(map(tail, func)). I don't like creating an array and immediately invoking a method on it. But that might be just me. I also don't like that it needs a conditional expression. But there's not much we can do without pattern matching and multiple function clauses. It turned out to be a lot simpler than I expected, though.

Reduce

Once we've done map, it seems that reduce shouldn't be much harder. This is the implementation I wrote in Elixir:

def reduce([], value, _func), do: value
def reduce([ head | tail ], value, func), do: reduce(tail, func.(head, value), func)

Note: I am aware that this doesn't handle the case where the function receives list with a single element. This would be easy to implement, but since the point of this exercise is to look at the general logic, I didn't want to over complicate it by handling all possible cases.

Here we have another function with two clauses. Much like map, it applies a function to a value and then calls itself again. It keeps doing that until it reaches an empty list, at which point it returns the accumulated value.

Much like we did with map, we can check if we're on the last element of the list, in which case we return the function applied to the current element and the accumulated value. Otherwise, we call reduce itself passing the list, the call to the function and the function itself. Something like this:

const reduce = ([ head, ...tail ], value, func) => tail.length === 0
    ? func(head, value)
    : reduce(tail, func(head, value), func)

const list = [ 1, 2, 3, 4, 5 ]
const sum = (val, acc) => val + acc
reduce(list, 0, sum) // -> 15

This works just fine. But what happens if we want to use the first element of the list as the initial value? In Elixir it is as simple as creating another function that takes care of it:

def reduce([ head, second | tail ], func), do: reduce(tail, func.(second, head), func)

This function will use the first element of the list as the initial value and then call the other reduce function with the right accumulated value. But in JavaScript two different functions can't share name and there's no such thing as function overloading. So we need an alternative.

If we want to keep the order of the parameters, we need to figure out whether the second argument is a function or not in order to know if it's the initial value. We could write something like this:

const reduce = ([ head, ...tail ], second, third) => {
    if (tail.length === 0) {
        return third(head, second)
    }
    if (typeof second === 'function') {
        return reduce(tail.slice(1), second(tail[0], head), second)
    }
    return reduce(tail, third(head, second), third)
}

As before, we first check if we've reached the end of the list, in which case we assume third is a function and second the accumulated value.

If it's not the end of the list, we check if second is a function. If it is, we assume we've passed no initial value and forget about third. Then we slice tail in order to be able to use the first two elements in our call to the function.

Otherwise, we do the same we did in the last implementation.

However, this is hard to understand. Since we don't know what second and third are going to be, it's hard to give them meaningful names, which doesn't help anyone who reads it.

So let's try changing the order of the parameters. We'll define the reducer function as the second parameter and the initial value as the third:

const reduce = ([ head, ...tail ], func, value) => {
    if (tail.length === 0) {
        return func(head, value)
    }
    if (value === undefined) {
        return reduce(tail.slice(1), func, func(tail[0], head))
    }
    return reduce(tail, func, func(head, value))
}

The implementation doesn't change all that much from the previous one, but the names are a lot clearer. Now we can pass two or three arguments and the function we'll be able to handle it:

const list = [ 1, 2, 3, 4, 5 ]
const sum = (val, acc) => val + acc
reduce(list, sum) // -> 15
reduce(list, sum, 5) // -> 20

This implementation still has one problem, though: it won't be able to handle well the case where it receives a two-element list and no initial value:

const list = [ 1, 2 ]
const sum = (val, acc) => val + acc
reduce(list, sum) // -> NaN

To fix that, we can check the whole list's length in the first if instead of only the tail's:

const reduce = (list, func, value) => {
    if (list.length === 0) {
        return value
    }

    const [ head, ...tail ] = list
    if (value === undefined) {
        return reduce(tail.slice(1), func, func(tail[0], head))
    }

    return reduce(tail, func, func(head, value))
}

Now it will check the length of the whole list first and, if it's not empty, it'll do the destructuring. If we wanted, to avoid those ugly tail.slice and tail[0], we could use some more destructuring:

const reduce = (list, func, value) => {
    if (list.length === 0) {
        return value
    }

    if (value === undefined) {
        const [ head, second, ...tail ] = list
        return reduce(tail, func, func(second, head))
    }

    const [ head, ...tail ] = list
    return reduce(tail, func, func(head, value))
}

All in all, the JavaScript version of reduce isn't particularly complicated either. Because of the different places in which it does the destructuring, the recursive calls are nice and clean. Very much like map, instead of three clauses (or, to be precise, a function with one clause and a function with two clauses), we have three branches within the function sifted through with two conditionals.

Final thoughts: Was it worth it?

I'm not going to suggest to write your own implementation of map and reduce to use in a project. I'm not even sure that using recursion is a good idea if one were to do it. But, as an exercise, it has been interesting to think how to do it in JavaScript and to observe how it differs from Elixir.

One of the things I really like about Elixir is pattern matching. I think it adds a lot of flexibility when defining functions and, to me, how a function handles different cases is clearer and easier to follow with a clause for each case, rather than with a bunch of conditions in the function's body. It is unfortunate that until pattern matching is implemented in JavaScript, different cases have to be handled with conditions (or a plugin).

I also liked thinking how to translate [ func.(head) | map(tail, func) ] into JavaScript. The pipe character is really useful to create lists and prepend elements. In some cases, the spread operator would accomplish the same; but not when we want to join a list and the result of recursively calling a function.

So it has been an interesting exercise for me.