Writing reduce in Elixir

Published October 11, 2018 by Toran Billups

In part 17 of my Elixir journey I wanted to show how you might implement `Enum.reduce`.


Last time around I implemented `map` to get a sense of how recursion works when the rubber hits the road. Today I'll dive a little deeper by hand rolling `reduce` to learn even more about the wonders of recursion.

    Enum.reduce([1, 2, 3], 0, &(&1 + &2))

The interface for this `reduce` function is fairly straight forward. The first parameter is a list to enumerate. The second is an initial value that we choose to start from. The third is a function we apply to each item in the list.

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

The first function clause acts as our starting point returning our initial value. We include 3 parameters here only to ensure we pattern match correctly. The last parameter `_func` is not needed so to avoid the compiler warning we prefix it with an underscore.

In the second function clause we invoke `reduce` with the tail, a new `value` and the `func` parameter. The magic here is that we compute a new `value` with each call to `reduce` using the `func` supplied.

    MyEnum.reduce([1, 2, 3], 0, &(&1 + &2))

We can calculate the return value from `reduce` by walking through the steps our program will execute in reverse. It's worth mentioning that each time the `reduce` function calls itself, it adds to the stack. And when the `reduce` function returns it will pop off the stack (hence the reverse order).

    0       # reduce([])
    (3 + 0) # reduce([3])
    (2 + 3) # reduce([2, 3])
    (1 + 5) # reduce([1, 2, 3])

With each `Enum` function I implement I can feel myself stretching muscles I've not used in years!

Buy Me a Coffee

Twitter / Github / Email