How to Write a Functor in Elixir
Tags: elixir
Published: 2022-08-02 10:55:16

There’s a function called `Enum.map` in Elixir that works on multiple collection types, but it's not without its issues.

In this post, I will introduce you to a concept from functional programming called a functor. We’ll make a `Functor` protocol with a function called `fmap` that will aspire to be a better version of `Enum.map`.

_Note:_ The article is inspired by the Witchcraft library, which we covered in one of our [previous posts](https://blog.appsignal.com/2022/02/08/functional-programming-in-elixir-with-witchcraft.html).

But first: what's the problem with `Enum.map` exactly?

## The Issue with `Enum.map` in Elixir

While `Enum.map` works fine with lists, its behavior is a bit odd for other collections.

```elixir
iex(1)> cities = %{"Latvia" => "Riga", "France" => "Paris", "Germany" => Berlin}
%{"France" => "Paris", "Germany" => Berlin, "Latvia" => "Riga"}
iex(2)> cities = Enum.map(cities, fn x -> x end)
[{"France", "Paris"}, {"Germany", Berlin}, {"Latvia", "Riga"}]
```

Even though we call it with an identity function that returns its input unchanged, we don’t get the same structure back.

And we can’t use the result as a map.

```elixir
iex(2)> Map.fetch(cities, "Latvia")
** (BadMapError) expected a map, got: [{"France", "Paris"}, {"Germany", "Berlin"}, {"Latvia", "Riga"}]
    (stdlib 3.17) :maps.find("Latvia", [{"France", "Paris"}, {"Germany", "Berlin"}, {"Latvia", "Riga"}])
```

Understanding how `Enum.map` works on maps depends on knowing two things:

1. Elixir thinks of maps as lists of tuples (but only when it wants to).
2. `Enum.map` will always return a list as a result.

Safe to say, this is not intuitive. But what could be a better way to do things, and how can we ensure we don’t make the same mistake again?

Let's see how a functor can help.

## What’s a Functor in Haskell?

In Haskell, `Functor` is a [typeclass](https://serokell.io/blog/haskell-typeclasses), an ‘interface’ with a set of methods common to multiple data types.

```haskell
-- Definition for illustrative purposes.

class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
```

The closest thing to typeclasses in Elixir is [protocols](https://blog.appsignal.com/2019/02/19/elixir-alchemy-pouring-protocols.html). In the same way that we have [`Enumerable`](https://hexdocs.pm/elixir/1.13/Enumerable.html) (`Enum`) in Elixir, you can also think of `Functor` as _Functor-able_, or, in more human language, _Mappable_.

The important method of the Functor typeclass in Haskell is `fmap`.

### `fmap`

`fmap` takes a function and a structure, then returns the same structure with the function applied to the structure's content.

In other words, it implements a **structure-preserving transformation**.

`fmap` is similar to `Enum.map`, but there are some key differences:

- `fmap` returns the structure it is called on, while `Enum.map` always returns a list.
- It enables you to map a wider set of structures. For example, in Haskell, you can use `fmap` with single-item structures (like `{:ok, result}`) and even functions.

_Note:_ In Haskell, `fmap` takes the function as the first argument. But since Elixir usually has data in the first position due to pipes, I've switched the arguments while adapting the concept.

It’s best to look at some examples to understand what `fmap` does. The examples below use the implementation that we will later create ourselves.

```elixir
iex(1)> import Functor
Functor
```

**Lists**

```elixir
iex(2)> fmap([1, 2, 3], fn x -> x + 1 end)
[2, 3, 4]
```

**Maps**

```elixir
iex(3)> cities = %{"Latvia" => "riga", "France" => "paris", "Germany" => "berlin"}
%{"France" => "paris", "Germany" => "berlin", "Latvia" => "riga"}
iex(4)> fmap(cities, fn x -> String.capitalize(x) end)
%{"France" => "Paris", "Germany" => "Berlin", "Latvia" => "Riga"}
```

**Trees**

```elixir
iex(5)> a = %Tree{value: 1, children: [%Tree{value: 2, children: []}, %Tree{value: 3, children: []}]}
%Tree{
  children: [%Tree{children: [], value: 2}, %Tree{children: [], value: 3}],
  value: 1
}
iex(6)> fmap(a, fn x -> x + 1 end)
%Tree{
  children: [%Tree{children: [], value: 3}, %Tree{children: [], value: 4}],
  value: 2
}
```

**Result tuples**

```elixir
iex(7)> fmap({:ok, 4}, fn x -> x + 3 end)
{:ok, 7}
iex(8)> fmap({:error, :not_a_number}, fn x -> x + 3 end)
{:error, :not_a_number}
```

If you look at these examples, you’ll see that they all have a/some value(s) wrapped in a structure. `fmap` uses the function we provide to change the value(s) while keeping the structure the same.

If I could write its typespec, it would look something like this.

```elixir
@spec fmap(f(a), (a -> b)) :: f(b)
```

It takes:

1. something of type `a` wrapped in type `f`
2. a function from type `a` to type `b`

And it returns a value of type `b` wrapped in type `f`.

### Functor Laws in Elixir

`fmap` needs to follow a set of equational laws to achieve its goal. And if laws scare you — please skip this, look at the implementation, then come back, and it will be easier.

In Haskell, the compiler doesn't check these laws by default, but you need to follow them for the implementation to ‘make sense’.

The first law says that if you have a function that returns its output untouched, ‘fmapping’ it will do the same.

```elixir
fmap(y, fn x -> x end) == y
```

The second law says that composing two ‘fmaps’ is the same as ‘fmapping’ the composition of those functions.

It looks something like this:

```elixir
(fmap(x, f1) |> fmap (f2)) == (fmap(x, fn y -> f2(f1(y)) end))
```

The laws are awkward to express in Elixir, but they basically work to preserve the structure of the type you’re mapping over.

The implementation of `Enum.map` for maps, for example, satisfies the second law, but doesn’t satisfy the first. Hence, it is not a lawful implementation of `fmap`.

## Why Do You Need to Know About Functors?

In programming, some patterns repeat themselves time and time again.

For a long time, people have been trying to describe these patterns and pass them on to other software developers to:

1. Solve problems faster
2. Expand ‘tools for thought’
3. Make communication easier.

A functor is also a pattern, just like singleton and factory.

Most classic patterns are useful, yet appear infrequently. But patterns like functors (and other math-based typeclasses) are so simple in their internal structure that they are bound to appear in your code (even if you don't mean them to). At that point, you can either use the knowledge we have to handle them or not.

Let's look at an example. In Elixir, a lot of our code is expressed in pipelines, which can be looked at as a series of transformations on data. It's very readable: one of the main reasons why the syntax of Elixir is so attractive.

Functors can help us make our code even better in two ways.

First, functors express pipe-able transformations of collections of data. If we have a `fmap` function that returns the same kind of wrapper, we can easily pipe transforms into each other without calling `Enum.into()` in between.

Secondly, functors also help to transform nested values in pipelines. If a function returns a data type with a more complex structure like `{:ok, result}/{:error, error}`, we sometimes run into problems when piping. To handle the value, we either need to deconstruct it or write a function that handles the structure and does the transformation behind the scenes.

The first can create such horrors as piping into case statements in the middle of a pipeline, while the second can introduce a lot of code duplication and make code more obscure.

`fmap` enables us to apply a function to a nested value without explicitly destructuring, unwrapping, and/or repacking the data. The word `fmap` informs other readers of your code what the function does. Then, after all transformations are complete, you can handle the resulting value.

Now that we have a feel for what functors are, we can try to replicate their behavior in Elixir. To do that, we’ll use protocols.

## Simulating Functors in Elixir

In this section, we will create a [protocol](https://hexdocs.pm/elixir/1.12.3/Protocol.html) for functors and provide implementations for four data types: lists, maps, trees, and result tuples.

### Set-up

For this tutorial, we will need a new Elixir project.

```shell
mix new functor
```

And a file called `functor.ex`.

### Create a `Functor` Protocol

This is rather straightforward.

First we open `functor.ex`. Then we use the `defprotocol` macro to create a protocol.

We provide the functions that the protocol will have to the macro. In our case, the only function is `fmap`.

```elixir
defprotocol Functor do
  def fmap(a, f)
end
```

That’s all we need to do.

### Create an Implementation for Lists

Of course, a protocol is only as good as its implementations.

We can create new implementations for a protocol with the `defimpl` macro. Let’s do the list right inside `functor.ex` since list is a staple data type.

`fmap` for lists is the same as a regular map. So we’ll just use `:lists.map` from grandpa Erlang for the implementation.

```elixir
defimpl Functor, for: List do
  @spec fmap(list, (list -> list)) :: list
  def fmap(a, f), do: :lists.map(f, a)
end
```

Here’s how `fmap` works for lists:

```elixir
iex(1)> Functor.fmap([1,2,3], fn x -> x + 1 end)
[2, 3, 4]
```

### Create an Implementation for Maps

Now we’ve come to the data type we mentioned at the start of the article.

The easiest way to make `Enum.map()` return a map is to pack it back into a map after mapping it.

```elixir
defimpl Functor, for: Map do
  def fmap(a, f), do: Enum.map(a, f) |> Enum.into(%{})
end
```

But there’s a small problem here. It can easily fail.

```elixir
iex(1)> Functor.fmap(%{Netherlands: "Amsterdam"}, fn {k, v} -> v end)
** (ArgumentError) argument error
    (stdlib 3.17) :maps.from_list(["Amsterdam"])
    (elixir 1.13.0) lib/enum.ex:1448: Enum.into_map/1
```

This is one of the reasons why `Enum.map()` on maps returns lists. The function you provide might create something that isn't a map anymore.

It’s also not a valid functor implementation. Functors can change only one value: they can map either keys or values, and we have to choose one for the implementation.

We can solve both of these problems at the same time by limiting the mapping operation to the values.

```elixir
defimpl Functor, for: Map do
  def fmap(a, f) do
    map_in_list = Map.to_list(a)

    :lists.map(fn {k, v} -> {k, f.(v)} end, map_in_list)
    |> Enum.into(%{})
  end
end
```

Here’s how it works:

```elixir
iex(1)> Functor.fmap(%{Netherlands: "Amsterdam"}, fn x -> x <> "!" end)
%{Netherlands: "Amsterdam!"}
```

There are some arguments against this implementation (even though it is a valid functor 😅). Having a map function work only on values might be as unintuitive as having it return a list.

You also can't work with the keys in any capacity — you need other functions for that. But every time you call `fmap` on a map, you will get a map back.

### Create an Implementation for Trees

Now that we have seen how to define fmap for simpler data types, let's try to define it for a type not served by the `Enum` protocol — trees.

First off, we need to define the struct. We’ll do that in `structures.ex`.

```elixir
defmodule Tree do
  defstruct value: nil, children: []

  @type t() :: %__MODULE__{
          value: any(),
          children: [t()]
        }
end
```

For simplicity’s sake, each of the tree's nodes has a value and a list of children that can be empty.

Now we can define the Functor implementation inside the module. In the definition, we can skip the `for: Tree` part — Elixir will know we mean the module struct.

```elixir
defmodule Tree do
  # ...
  defimpl Functor do

  end
end
```

All that is left is to write the implementation, which will be recursive.

We’ll apply the function to the value if we have a leaf (which has no children).

```elixir
def fmap(%Tree{value: value, children: []}, f), do: %Tree{value: f.(value), children: []}
```

If the node has children, we need to _map this fmap_ over all of them. This gives us a great opportunity to use the `Functor.fmap` we created earlier!

```elixir
def fmap(%Tree{value: value, children: children}, f) do
  updated_children = Functor.fmap(children, fn x -> fmap(x, f) end)
  %Tree{value: f.(value), children: updated_children}
```

If you understand the piece of code above, you have already achieved a certain level of enlightenment about functors ☯

Here’s how the function works:

```elixir
iex(1)> a = %Tree{value: 1, children: [%Tree{value: 2, children: []}, %Tree{value: 3, children: []}]}
%Tree{
  children: [%Tree{children: [], value: 2}, %Tree{children: [], value: 3}],
  value: 1
}
iex(2)> Functor.fmap(a, fn x -> x + 1 end)
%Tree{
  children: [%Tree{children: [], value: 3}, %Tree{children: [], value: 4}],
  value: 2
}
```

As an exercise, you can try to create a struct for a _binary tree_ — one where a node has a maximum of two children — and a `fmap` implementation for this struct.

### Create an Implementation for Result Tuples

Finally, let's see how we can implement `fmap` for result tuples.

Now, mapping a tuple might seem counterintuitive for some. But transforming a collection of values is not the only thing `fmap` can do. Another angle of how we can look at `fmap` is that it _lifts_ a function into a context.

In Elixir, functions sometimes return one of `{:ok, result}` or `{:error, error}`. We can call this the context of a computation that might have succeeded or failed.

Now imagine we want to apply a function such as `fn x -> x + 1 end` to this result.

We can either:

- Unpack it via pattern-matching and handle the error right here, right now.
- Lift the function inside the context of possible error and then send the result somewhere further.

It is pretty straightforward to do the second with this tuple. If we have an `{:ok, result}`, we just apply the function to the result. If we have an `{:error, error}`, we don’t apply the function, but simply pass on the error.

But there are some problems with making a functor implementation.

To do it, we have to dispatch on the `Tuple` type, which theoretically has a lawful Functor implementation of its own that changes only the last element of the tuple.

Since Elixir cannot discern our intentions, this would mean doing something practical yet a bit unlawful.

But since “practical yet a bit unlawful” sounds like the best characterization of Elixir I’ve read, we’ll go ahead and do it anyway.

```elixir
defimpl Functor, for: Tuple do
  def fmap({:ok, result}, f), do: {:ok, f.(result)}
  def fmap({:error, reason}, \_f), do: {:error, reason}
end
```

Here’s how it works:

```elixir
iex(2)> fmap({:ok, 4}, fn x -> x + 3 end)
{:ok, 7}
iex(3)> fmap({:error, :not_a_number}, fn x -> x + 3 end)
{:error, :not_a_number}
```

The lawful but unidiomatic way to do this in Elixir would be to create two structs — `%Result.Ok{}` and `%Result.Err{}` — and define the `fmap` implementation for those instead.
As an exercise, you can try to do this on your own.

## Are Functors Useful in Elixir?

Now that we have created a basic yet working protocol for functors, it’s good to ask: is this thing useful?

Well, it's kind of cute. We can use it to do some cool things, such as create a map function that works on both a list of trees and a tree of lists.

```elixir
def mega_map(a, f) do
  Functor.fmap(a, fn x -> Functor.fmap(x, f) end)
end
```

And when we add a couple more implementations, having a mapping function that works on multiple data types (like `Enum.map`) but doesn't always return list can be handy.

But the power of Haskell-inspired ideas is proportional to the infrastructure you have to work with them. Let's think of this as an optimization exercise. We’re traveling away from a local idiomatic Elixir peak to write code that is more expressive and intuitive.

In Haskell, you have access to a ton of other ‘mathy’ typeclasses like Applicative, Monad, and more to help you write code that’s starkly different from Elixir. And it’s much easier because of the type system and other peripherals.

At the same time, what happens if we carefully pick out concepts from other programming languages and adapt them to how we write Elixir right now? We develop a way of writing Elixir that is more convenient and makes sense to adopters from other functional programming languages.

This is akin to mainstream languages borrowing higher-order functions and result types from functional programming. Haskell's whole complex type machinery is not needed in Elixir, but perhaps there is a simpler way to structure work with collections that doesn’t take inspiration from Ruby.

In particular, I've lately fallen in love with Witchcraft's vision for how the syntax of Elixir could look. It provides custom operators that work in a pipe-like fashion. For example, you can use `~>` instead of `|> fmap`.

Having a few custom operators like these that synergize with how idiomatic Elixir is written, yet follow strict laws for implementation, would enable writing very expressive code that still feels like Elixir.

And given the news that Elixir is working on a [set-theoretic type system](https://twitter.com/josevalim/status/1535008937640181760?s=20&t=g8IJbaJyi5TZuDdbgDmLqg), it’s high time to take a quick peek in the direction of other typed functional languages.

## Wrap Up and Further Learning

In this article, we covered how to build a simple protocol for functors, together with implementations for four data types: lists, maps, trees, and result tuples.

If you’re interested in trying out more functors magic in Elixir, check out [Witchcraft](https://github.com/witchcrafters/witchcraft), which has been my main inspiration for this post.

And if you want to delve deeper into the world of typed functional programming, you should definitely try out Haskell. The best way to do that is to start with one of these books: _[Haskell Programming From First Principles](https://haskellbook.com/)_ or _[Get Programming With Haskell](https://www.manning.com/books/get-programming-with-haskell)_.

Until next time, happy coding!

**P.S. If you'd like to read Elixir Alchemy posts as soon as they get off the press, [subscribe to our Elixir Alchemy newsletter and never miss a single post](/elixir-alchemy)!**