Functors in F#
Tags: fsharp, dotnet, functional
Published: 2020-01-15 18:56:05

Functors are a popular topic in the functional programming world[^1], but some of what's been written is confusing. In this post, I hope to provide a clear description of the concept so we can build on it in the future.

So, what is a functor exactly? The short answer is that **a functor is anything that can be "mapped" over**. F# contains lots of maps, and most of them are actually called "map", which is certainly helpful. A map is simply a function that can be used to transform a functor instance into a different instance of the same type (without changing its structure). For example, the `List` type is a functor that can be mapped over using the `List.map` function:

```fsharp
let before = [ 1; 2; 3 ]
let after = List.map (fun x -> x * 2) before
```

We've used `List.map` to transform the list `[ 1; 2; 3 ]` into the the list `[ 2; 4; 6 ]` by doubling each element.

The result of `List.map` will always be another `List` instance, but the type *contained* in the resulting list might be different. For example, we can convert a `List<string>` to a `List<int>` like this:

```fsharp
let before = [ "one"; "two"; "three" ]
let after = List.map String.length before
```

The produces `[ 3; 3; 5 ]`. In short, if you know how to transform an `'a` into a `'b` (via an `'a -> 'b` function), then you can also transform any functor of `'a` into a functor of `'b`.

All of F#'s collections are functors[^2], because they're all mappable in this way. It's very common for containers to be functors. For example, the `Option` type is also a functor:

```fsharp
let beforeSome = Some 10
let afterSome = Option.map (fun x -> x * 2) beforeSome

let beforeNone = None
let afterNone = Option.map (fun x -> x * 2) beforeNone
```

Here, we've transformed `Some 10` into `Some 20`, again by doubling, while `None` maps to `None` as expected. You can think of `Option` as a container that always holds either a single value (`Some x`) or no value (`None`).

So is a functor just a fancy synonym for a container that can be mapped over? No. Most well-behaved containers are definitely functors, but there are functors that don't fit this description. For example, functions are also functors because their return values can also be mapped over. Let's take a look at an implementation of `List.map` to make sure we map function return values in the exactly the same way:

```fsharp
module List =
    let map mapping list =
       [
           for elem in list do
               yield mapping elem
       ]
```

OK, so to do the same thing with functions, we need a `Function.map` function that follows the same pattern:

```fsharp
module Function =
    let map mapping func =
        // implementation?
```

We need to apply the `mapping` function to the result of the `func` function in just the same way that `List.map` applies its `mapping` function to each element of the list:

```fsharp
module Function =
    let map mapping func =
        fun funcInput ->                      // pretend we have input to func
            let funcResult = func funcInput   // get the result of calling func
            mapping funcResult                // send that value into the mapping
```

We can simplify the implementation considerably:

```fsharp
module Function =
    let map mapping func =
        fun x -> mapping (func x)
```

Let's rewrite that using [pipes](https://dev.to/shimmer/f-tip-2-use-the-pipe-operator-2i2j) instead:

```fsharp
module Function =
    let map mapping func =
        fun x -> x |> func |> mapping
```

But now we don't even need `x` at all:

```fsharp
module Function =
    let map mapping func =
        func >> mapping
```

So `Function.map` is just standard function composition, which makes sense if you think about its type signature:

```fsharp
('b -> 'c) -> ('a -> 'b) -> ('a -> 'c)
```

# Laws

Functors must obey certain laws in order to be considered well-behaved. These laws require that `map` not affect the structure of the functor. The function passed to `map` may change the values within the functor, but `map` itself may not change the functor at all.

The first rule is that if the mapping function doesn't change anything, then calling `map` with that function returns the functor unchanged:

```fsharp
let same x = x

List.map [1; 2; 3] same = [1; 2; 3]
```

The second rule is that you can compose two mapping functions before calling `map` or you can compose two individual calls to `map` with those mapping functions, and you get the same result either way:

```fsharp
let times2 x = x * 2
let plus1 x = x + 1

let resultA = List.map (times2 >> plus1) [1; 2; 3]
let resultB = ((List.map times2) >> (List.map plus1)) [1; 2; 3]
```

In both cases, the resulting list is `[3; 5; 7]`, which is obtained by multiplying each element of the orginal list by 2 and then adding 1.

# Summary

We've seen that a functor is anything that can be mapped over. All functors fall into one of the two buckets we've discussed:

* Containers of values, like `List` or `Option`. Mapping applies to the contained values. These are called "data functors".

* Something that can *produce* a value (even though it doesn't actually contain that value), like the return value of a function[^3]. Mapping applies to the produced value. These are called "control functors".[^4]

Functional programmers use functors every day, even without realizing it. But now that we understand the pattern, we can use it to build even more powerful and sophisticated tools.

[^1]: Some object-oriented languages, like C++, use the word "functor" to describe a completely different thing, which we won't be discussing here. In math, the word "functor" is also used, but in a more general way than what we're covering in this post.

[^2]: Except, perhaps, [`Set<'T>`](https://blog.ploeh.dk/2018/12/03/set-is-not-a-functor).

[^3]: Functions can also be seen as functors in their *input* value, but only in the general math sense. In the programming sense, functions are [contravariant](https://dev.to/shimmer/contravariants-p6n) in their input value. So if a functor is something that can be "mapped over", then a contravariant is something that can be "mapped into" by a pre-processing function.

[^4]: See [this blog post](https://www.tweag.io/posts/2020-01-16-data-vs-control.html) for more on the distinction between data and control functors.