Functors in F#

#fsharp #dotnet #functional

Functors are a popular topic in the functional programming world¹, 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:

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:

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², 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:

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:

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:

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:

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:

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

Let's rewrite that using pipes instead:

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

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

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:

('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:

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:

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³. Mapping applies to the produced value. These are called "control functors".⁴

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.

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. ↩
Except, perhaps, Set<'T>. ↩
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 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. ↩
See this blog post for more on the distinction between data and control functors. ↩