How to Write a Functor in Elixir

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.

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.

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.

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, an ‘interface’ with a set of methods common to multiple data types.

-- 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. In the same way that we have Enumerable (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.

iex(1)> import Functor
Functor

Lists

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

Maps

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

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

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.

@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.

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:

(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 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.

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.

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.

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:

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.

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.

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.

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:

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.

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.

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).

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!

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:

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.

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:

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.

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, 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, 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 or 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!

Comments

[NDREAN]

Thanks for sharing. Following you, I believe the defined Functor for List can be immediately used in your Functor for Map:

defimpl Functor, for: Map do
  def fmap(a, f) do
    Map.to_list(a)
    |> Functor.fmap(fn {k, v} -> {k, f.(v)} end)
    |> Enum.into(%{})
  end
end