loading...

Functors in F#

shimmer profile image Brian Berns Updated on ・4 min read

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. 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. I'm not going to spend a lot of time on these, because they are intuitive, and you'd be quite surprised to encounter a map function that didn't follow them.

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

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

  3. See this blog post for more on the distinction between data and control functors. 

Posted on Dec 29 '19 by:

shimmer profile

Brian Berns

@shimmer

Functional programming enthusiast focused on F# .NET applications. #fsharp

Discussion

markdown guide
 

Some object-oriented languages, like C++, use the word "functor" to describe a completely different thing

OCaml, one of F#'s direct relatives, also has another notion of functor:

Module functors

Of course it also has the "mappable" kind of functor, but since there are no type classes the functor type refers to module functors.

For anyone who wants to dig deeper on functors, I think this post explaining them in ReasonML does a good job.

 

I've heard that ML module functors are very powerful, but haven't had any experience with them. Thanks for the links.

 

F# decided to forego them in favor of OO mechanisms. It makes sense since it's a pragmatic language sitting on top of .NET, but I'd sometimes prefer having module functors available as a functional alternative. Here's something I did for a ray tracer using module functors (simplified):

module type Shape = sig
  val intersect : float -> float list
  val normal : float -> float
end

module Make_Shape (M : Shape) : Shape = struct
  let intersect n = M.intersect
  let normal n = M.normal
  (* other functions using intersect and normal *)
end

module Sphere = Make_Shape (struct
  let intersect n = ...
  let normal n = ...
end)

So here each shape brings its own implementation of intersect and normal, and the Make_Shape functor makes new shapes. It's easy to see how one would use interfaces and/or abstract base classes to achieve the same in F# (though in the end I settled for a pattern of passing functions to a "factory" function, something I learned from one of Scott Wlaschin's posts).

That’s interesting. It does seem like the Shape module essentially behaves like an abstract base class here.