Grokking Functors
Tags: fsharp, functional, programming, grokking
Published: 2021-03-31 10:04:42

In this post we're going to grok functors by "discovering" them through a worked example.

# Small F# primer

Skip this if you've got basic familiarity with F#. 
It should be easy enough to follow along if you've not used F# before though. You'll only need to understand the following bits.

* F# has an `option` type. It represents either the presence of `Some` value or its absence through a `None` value. It is typically used instead of `null` to indicate missing values.
* Pattern matching on an `option` type looks like:

```fsharp
match anOptionalValue with
| Some x -> // expression when the value exists
| None -> // expression when the value doesn't exist.
```

* F# has a pipe operator which is denoted as `|>`. It is an infix operator that applies the value on the left hand side to the function on the right. For example if `toLower` takes a string and converts it to lowercase then `"ABC |> toLower` would output `"abc"`.

# The scenario
Let's say we've been asked to write a function that will print a user's credit card details. The data model is straight forward, we have a `CreditCard` type and a `User` type.

```fsharp
type CreditCard =
    { Number: string
      Expiry: string
      Cvv: string }

type User =
    { Id: UserId
      CreditCard: CreditCard }
```

# Our first implementation
We want a function that takes a `User` and returns a `string` representation of their `CreditCard` details. This is fairly easy to implement.

```fsharp
let printUserCreditCard (user: User): string =
    let creditCard = user.CreditCard

    $"Number: {creditCard.Number}
    Exiry: {creditCard.Expiry}
    Cvv: {creditCard.Cvv}"
```

We can even factor this out by writing a `getCreditCard` function and a `printCreditCard` function, which we can then just compose them whenever we want to print a user's credit card details.

```fsharp
let getCreditCard (user: User) : CreditCard = user.CreditCard

let printCreditCard (card: CreditCard) : string =
    $"Number: {card.Number}
    Exiry: {card.Expiry}
    Cvv: {card.Cvv}"

let printUserCreditCard (user: User) : string =
    user
    |> getCreditCard 
    |> printCreditCard
```

Beautiful! 👌

# A twist 🌪
All is well, until we realise that we first need to lookup the user by their id from the database. Fortunately, there's already a function implemented for this. 

```fsharp
let lookupUser (id: UserId): User option =
    // read user from DB, if they exist return Some, else None
```

Unfortunately, it returns a `User option` rather than a `User` so we can't just write

```fsharp
userId
|> lookupUser
|> getCreditCard
|> printCreditCard
```

because `getCreditCard` is expecting a `User`, not an `option User`.

Let's see if we can transform `getCreditCard` so that it can accept an `option` as input instead, without changing the original `getCreditCard` function itself. To do this we need to write a function that will wrap it. Let's call it `liftGetCreditCard`, because we can think of it as "lifting" the `getCreditCard` function to work with `option` inputs.

This might seem a bit tricky to write at first, but we know that we have two inputs to `liftGetCreditCard`. The first is the `getCreditCard` function and the second is the `User option`. We also know that we need to return a `CreditCard option`. So the signature should be `(User -> CreditCard) -> User option -> CreditCard option`.

By following the types there's only really one thing to do, try and apply the function to the `User` value by pattern matching on the `option`. If the user doesn't exist then we can't apply the function so we have to return `None`.

```fsharp
let liftGetCreditCard getCreditCard (user: User option): CreditCard option =
    match user with
    | Some u -> u |> getCreditCard |> Some
    | None -> None
```

Notice how in the `Some` case we have to wrap the output of `getCreditCard` in `Some`. This is because we have to make sure both branches return the same type and the only way to do that here is to make them return `CreditCard option`.

With this in place our pipeline is now

```fsharp
userId
|> lookupUser
|> liftGetCreditCard getCreditCard
|> printCreditCard
```

By partially applying `getCreditCard` to `liftGetCreditCard` we created a function whose signature was `User option -> CreditCard option`, which is what we wanted. 

Well nearly, we've got the same issue as before except on the last line now. `printCreditCard` only knows how to deal with `CreditCard` values and not `CreditCard option` values. So let's apply the same trick again and write `liftPrintCreditCard`.

```fsharp
let liftPrintCreditCard printCreditCard (card: CreditCard option): CreditCard option =
    match card with
    | Some cc -> cc |> printCreditCard |> Some
    | None -> None
```

And our pipeline is now

```fsharp
userId
|> lookupUser
|> liftGetCreditCard getCreditCard
|> liftPrintCreditCard printCreditCard
```

# Is that a functor I see 🔭
If we zoom out a bit, we might notice that the two `lift...` functions are remarkably similar. They both perform the same basic task, which is to unwrap the `option`, apply a function to the value if it exists and then package this value back up as a new `option`. They don't really depend on what's inside the `option` or what the function is. The only constraint is that the function accepts as input the value that might be inside the `option`.

Let's see if we can write a single version called `lift` which defines this behaviour for any valid pair of a function, which we'll call `f` and an `option`, which we'll call `x`. We can erase the type definitions for now and let F# infer them for us.

```fsharp
let lift f x =
    match x with
    | Some y -> y |> f |> Some
    | None -> None
```

Tidy, but perhaps a little bit abstract. Let's see what the inferred types tell us about this. F# has inferred it to have the type `('a -> 'b) -> 'a option -> 'b option`. Where `'a` and `'b` are generic types. Let's place it side-by-side with `liftGetCreditCard` to help us make it more concrete.

```fsharp
(User -> CreditCard) -> User option -> CreditCard option

('a -> 'b) -> 'a option -> 'b option
```

The concrete `User` has been replaced by the generic type `'a` and the concrete `CreditCard` type has been replaced with the generic type `'b`. That's because `lift` doesn't care what's inside the `option` box, it's just saying "give me some function `f` and I'll apply this to the value contained within `x` if it exists and repackage it as a new option". 

A more intuitive name for `lift` would be `map`, because we're just mapping the contents inside the `option`.

So with this new `map` function in place let's use it in our pipeline.

```fsharp
userId
|> lookupUser
|> map getCreditCard
|> map printCreditCard
```

Nice! This is nearly identical to the version we wrote before the `option` bombshell was dropped on us. So the code is still very readable. 

# You just discovered functors 👏
That `map` function we wrote is what makes `option` values functors. Functors are just a class of things that are "mappable". Lucky for us, F# has already defined `map` in the `Option` module, so we can actually just write our code using that instead

```fsharp
userId
|> lookupUser
|> Option.map getCreditCard
|> Option.map printCreditCard
```

# Functors are just "mappable" containers 📦
Another good way to intuit functors is to think of them as value containers. For each type of container we just need to define a way to be able to map or transform its contents. 

We've just discovered how to do that for `option`s, but there are more containers that we can turn into functors too. A `Result` is a container which either has a value or an error and we want to be able to map the value regardless of what the error is. 

The most common container though is a `List` or an `Array`. Most programmers have encountered a situation where they've needed to transform all the elements of a list before. If you've ever used `Select` in C# or `map` in JavaScript, Java etc then you've probably already grokked functors, even if you didn't realise it.

# Test yourself 🧑‍🏫
See if you can write `map` for the `Result<'a, 'b>` and `List<'a>` types. The answers are below, no peeking until you've had a go first!

{% details Result solution %} 
```fsharp
let map f x =
    match x with
    | Ok y -> y |> f |> Ok
    | Error e -> Error e
```

This one is nearly identical to `option` in that we just apply the function to value of the `Ok` case otherwise we just propagate the `Error`.
{% enddetails %}

{% details List solution %}
```fsharp
let rec map f x =
    match x with
    | y:ys -> f y :: map f ys
    | [] -> []
```
    
This is a little trickier than the others, but the basic idea is the same. If the list has some items we pick off the head of the list, apply the function to the head and add it to the front of a new list created by mapping over the tail of this one. If the list is empty we just return another empty list. By reducing the list size by one each time we call `map` again we guarantee that eventually we hit the base case of the empty list which terminates the recursion.
{% enddetails %}

# What did we learn 🧑‍🎓
We learnt that functors are just types of containers that have a `map` function defined for them. We can use this function to transform the contents inside the container. This allows us to chain together functions that work with regular values even when those values are packaged in one of these container types.

This is useful because this pattern occurs in lots of different situations and by extracting a `map` function we can eradicate quite a bit of boilerplate that we'd otherwise have to do by constantly pattern matching.

# Taking it further
If you enjoyed grokking functors, you'll love [Grokking Monads](https://dev.to/choc13/grokking-monads-in-f-3j7f). There we follow a similar recipe and discover a different type of function that's also very useful.