Writing filter in Elixir

Published October 12, 2018 by Toran Billups

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


Today I'll be hand rolling `filter` and using it to return even numbers in a list. Note: the `rem` function is short for remainder and proves useful when trying to determine if an integer is even or odd.

    Enum.filter([1, 2, 3], &(rem(&1, 2) == 0))

The interface for this `filter` function is fairly straight forward. The first parameter is a list to enumerate. The second parameter is a function we apply to each item in the list. Ideally this function should return true or false. The return type is a new list.

    defmodule MyEnum do
      def filter([], _func), do: []
      def filter([head | tail], func) do
        case func.(head) do
          true ->
            [ head | filter(tail, func) ]
          false ->
            filter(tail, func)

The first function clause acts as our starting point returning an empty list. We include 2 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 `filter` with the tail and `func`. When the anonymous function returns `true` we also include the `head` value. When it returns `false` we omit the `head` to avoid returning it of course.

    MyEnum.filter([1, 2, 3], &(rem(&1, 2) == 0))

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

    [ ]         # filter([])
    [ ]         # filter([3])
    [ 2 | [ ] ] # filter([2, 3])
    [ 2 ]       # filter([1, 2, 3])

Because `filter` is robust we can also use it to return odd numbers in a list like you'd expect with `Enum.filter`.

    MyEnum.filter([1, 2, 3], &(rem(&1, 2) == 1))

Implementing `filter` was a little more fun than `reduce` because I had to learn about the `case` control flow structures. This provides a gateway to even more Elixir goodness!

Buy Me a Coffee

Twitter / Github / Email