What is a functor?

People will often ask me about monads - it's a common topic on the stream but we don't really give functors any love. That's a pity, as functors are a great gateway to understanding monads as well as many other things.

Let's have a quick look at what a functor has to do:

// Just one example of a functor
type Functor<'a> = List<'a> 

type MapFunctor<'source, 'result> =
    ('source -> 'result) -> Functor<'source> -> Functor<'result>

Let's break this down as it is a little unwieldy:

The first line is just giving us an example of something that could be considered a functor, Lists aren't the only functors around though as we'll see later.

For now let's work on the meat of the definition: that MapFunctor that we defined. Remember that -> means that we're working with a function and that a -> b could be read as "a goes to b" or just "a to b" so MapFunctor is a function that takes in a function of a single argument and a "wrapped" item, then returns a new "wrapped" item where the function taken has been applied to each item before re-wrapping it.

A concrete example mught help I think:

let ourList = [1; 2; 3; 4]

let mapList : MapFunctor<_, _> = List.map

let newList = mapList (fun item -> item + 1) ourList

newList now holds the value:

[2; 3; 4; 5]

As you can see - each element has been incremented.

Hold on - you never defined the MapFunctor, you just used List.map!

Indeed, well spotted. While I could go into implementing List.map here I think it would be best left as an exercise to the reader. (Hint: pattern matching and recursion are your friends.)

Let's introduce the Option Functor:

type Option<'a> =
    | Some of 'a
    | None

The general idea here is instead of null we have something where you either have Some value or you have None. So what should our map function do? I think we can pretty safely say that any None value should map to None and that only if we pass in Some value should we execute the function thus:

let mapOption func opt =
    match opt with
    | Some item -> Some (func item)
    | None -> None

We can see that the function above does what we wanted. Something that we haven't yet touched on yet though is that we can map to a different type. Let's have a look at that now:

let toString (num: int) = num.ToString()

let someNum = Some 1
let someStr = mapOption toString someNum

someStr is now not an Option<int> but is the following Option<string>:

Some "1"

As you can see - the map operation isn't just reserved for collections but can work for other constructs too. Any construct that the map operation can sensibly be defined on can be considered a functor.

By sensibly we mean the following:

These may seem complicated but they really are just pretty standard behaviour and by following these rules with a type you have just made a functor!

Multiple items
module List

from Microsoft.FSharp.Collections

type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member GetSlice : startIndex:int option * endIndex:int option -> 'T list
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
type MapFunctor<'source,'result> = ('source -> 'result) -> Functor<'source> -> Functor<'result>

Full name: 2018-11-05-what-is-a-functor.MapFunctor<_,_>
type Functor<'a> = List<'a>

Full name: 2018-11-05-what-is-a-functor.Functor<_>
val ourList : int list

Full name: 2018-11-05-what-is-a-functor.ourList
val mapList : MapFunctor<'a,'b>

Full name: 2018-11-05-what-is-a-functor.mapList
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val newList : Functor<int>

Full name: 2018-11-05-what-is-a-functor.newList
val item : int
Multiple items
module Option

from Microsoft.FSharp.Core

type Option<'a> =
  | Some of 'a
  | None

Full name: 2018-11-05-what-is-a-functor.Option<_>
union case Option.Some: 'a -> Option<'a>
union case Option.None: Option<'a>
val mapOption : func:('a -> 'b) -> opt:Option<'a> -> Option<'b>

Full name: 2018-11-05-what-is-a-functor.mapOption
val func : ('a -> 'b)
val opt : Option<'a>
val item : 'a
val toString : num:int -> string

Full name: 2018-11-05-what-is-a-functor.toString
val num : int
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

type int = int32

Full name: Microsoft.FSharp.Core.int

type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
System.Int32.ToString() : string
System.Int32.ToString(provider: System.IFormatProvider) : string
System.Int32.ToString(format: string) : string
System.Int32.ToString(format: string, provider: System.IFormatProvider) : string
val someNum : Option<int>

Full name: 2018-11-05-what-is-a-functor.someNum
val someStr : Option<string>

Full name: 2018-11-05-what-is-a-functor.someStr