Functors are a popular topic in the functional programming world1, 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 functors2, 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
orOption
. 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 function3. 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.
-
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. ↩
-
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. ↩
Top comments (2)
I've heard that ML module functors are very powerful, but haven't had any experience with them. Thanks for the links.
That’s interesting. It does seem like the Shape module essentially behaves like an abstract base class here.