Writing map in Elixir

Published October 10, 2018 by Toran Billups

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

Map

The `Enum` module offers a lot of opportunity to learn about recursion and today I'll be hand rolling the map function to better understand how it works under the hood.

    Enum.map([1, 2, 3], fn (n) -> n + 1 end)
  

The interface for this `map` function is fairly straight forward. The first parameter is a list to enumerate. The second is a function we apply to each item in the list. The return type is a new list.

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

The first function clause acts as our starting point returning an empty list. The less obvious part for anyone new to Elixir like myself is the intentional underscore in the parameter `_func`. This tells the compiler we'd like to pattern match for arity of 2 but once that happens we will ignore the 2nd parameter altogether. Without an underscore at the front of this variable name Elixir will throw a warning.

In the second function clause we get to work by invoking `func` using the `head` we pattern matched. The result from this function call will represent the new head of our list. The tail will then be thrown into the subsequent `map` and that result will represent the new tail of our list.

    MyEnum.map([1, 2, 3], fn (n) -> n + 1 end)
  

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

    [ ]              # map([])
    [ 4 | [ ] ]      # map([3])
    [ 3 | [ 4 ] ]    # map([2, 3])
    [ 2 | [ 3, 4 ] ] # map([1, 2, 3])
  

If the syntax `[ 2 | [3, 4] ]` isn't familiar yet be sure to open IEx and evaluate it. This is easily one of the most essential tools for those learning the language.

    iex -S mix run
  
    [ 2 | [ 3, 4 ] ]
    # returns [ 2, 3, 4 ]
  

Buy Me a Coffee

Twitter / Github / Email