Functors, Monads and better functions
Tags: functional, math
Published: 2018-11-29 17:46:38

---
title: Functors, Monads and better functions
published: true
description: A quick dive into category theory
tags: #functional #math
---

<i>This post is part of a series called </i>functional fundamentals<i>. See the [introduction and index](https://dev.to/drbearhands/a-series-on-functional-fundamentals-48mb). That's also where you can request specific topics</i>

<i>Note that I am not an authoritative figure on these subjects, if you see something you think might be incorrect or incomplete, please point it out with a  comment, let's prevent mistakes from spreading :-)
</i>

-------------------

__This post was edited for clarity following feedback__

_In reading this, you should probably try not to think about concepts from imperative programming language. Especially forget about weakly types languages such as python and javascript. The isomorphism expressed here holds best with functional, strongly typed languages. Ideally, you have already written a very basic Elm or Haskell program or played around with their REPL._

It's about time to take a shallow dive into category theory. You can try to understand Functors and Monads without it, but that will often be awkward and sometimes even wrong. Category theory can also help you make better decisions about e.g. what type signatures your functions should have.

You might say category theory is the study of composition. This makes it weirdly abstract at times, but, I find, surprisingly easy to understand. At least, once your brain manages to parse all the symbols into meaning.

Category theory deals with _objects_ (not related to OOP) and _arrows_. The arrows go from one object to another. Object and arrows are very abstract concepts, category theory simply does not case about what they are, only about how arrows connect objects.
This makes category theory applicable to a lot of domains.

A category is merely "that which we are talking about". In FP, "that which we are talking about" is usually types and functions, so the objects correspond to types and the arrows correspond to functions. But in imperative programming you might use program state as objects and commands as arrows, as in [Hoare logic](https://en.wikipedia.org/wiki/Hoare_logic).

The two rules that we do require for a category are _identity_ and _composition_.

##### Identity

![image showing identity](https://thepracticaldev.s3.amazonaws.com/i/c2cyb9ijpg31h437uce9.png)
_Identity_ is an arrow that goes from an object to itself and exist for every object in a category.


##### Composition

![image showing composition](https://thepracticaldev.s3.amazonaws.com/i/8i8xbux61h63qw1qh2aq.png)

If there is an arrow `f` from object `a` to object `b` (denoted `f :: a → b`), and there is an arrow `g :: b → c`, then there must be an arrow `a → c`, called the _composition_ of `g` after `f`, denoted as `g ∘ f`.


#### Isomorphism with FP

In the category of types (and functions), we have identity by the `identity` function, and composition by the function composition operator (`<<` in Elm and `.` in Haskell). That means type systems in functional programming indeed follow the rules of category theory. Other languages do as well but in a bit of a weird way.

### Functors

Objects and arrows are part of a category. While arrows connect one object to another, it is also possible to connect one category to another, by connecting all objects from one category to objects in the other. This is called a _functor_ if the arrows in the first category connect objects in more-or-less the same way as in the second category.

![example of a functor](https://thepracticaldev.s3.amazonaws.com/i/lsbcb9sq368laadqlsp7.png)
<figcaption>In this image, the dotted line represents a functor. I've left out identity arrows for clarity.</figcaption>

But what does that mean exactly?

For a functor `F`, which goes from any object `x` in one category to a corresponding object `F x` in another category, and any pair of arrows `f :: a → b` and `g :: b → c`, and their composition `g ∘ f`, there must be corresponding arrows 
`f' :: F a → F b`, `g' :: F b → F c` and 
`(g ∘ f)' :: F a -> F c`, so that:
* if `f` is the identity arrows , `f'` is also the identity arrows (_identity_ is preserved)
* `(g ∘ f)' = g' ∘ f'` (_composition_ is preserved).

This tells us that structural rules that hold in one category, still hold in a category that is its functor.

In the image above, with `F` being a functor represented by the dotted line, you can see that we can first follow `f`, then `F`, then `g'`, or we can follow `g ∘ f`, then `F`, or `F` followed by `(g ∘ f)'`. The result will be the same because the 'path' on the left has a corresponding 'path' on the right.

A functor doesn't have to be between different categories, it can be from one category to itself, in which case we call it an _endofunctor_.

What does this mean for functional programming? Well, in type systems, we can create a type constructor (or [higher kinded type](https://en.wikipedia.org/wiki/Kind_(type_theory)) if you prefer): `List`, `Set`, `Array`, `Iterator`, `Maybe` / `Optional`, `Cmd` etc. They aren't really types by themselves, but will construct a type from another type.

A type constructor `F` is a functor [iff.](https://english.stackexchange.com/questions/62067/is-iff-considered-a-real-word-or-just-an-abbreviation) we have a function `fmap` that takes any function `a -> b` and produces an `F a -> F b` (with preservation of identity and composition we discussed above).

This `fmap` functions abstracts away the functor's inner structure, letting us focus on element operations. That way we can e.g. apply an operations to a list, dict, stream, promise or whatnot without resorting to loops, recursion or callback nesting.

Some Elm code samples:

* `List.map ((+) 1) listOfInts` will increase the values of all elements in `listOfInts` by 1.
* `Maybe.map ((+) 1) maybeInt` will increase `maybeInts` by 1 if it isn't `Nothing`.
* `Cmd.map ((+) 1) someCmd` (very much Elm specific) will cause the `msg : Int` passed to the update function in Elm's to be one higher than the result of executing `someCmd : Cmd Int`.

In Haskell, you use typeclasses to write e.g. `fmap ((+) 1) [...]`, but the idea is the same.

### Monads

_Monads_ are a special type of _endofunctor_ (functors from a category to itself). ~~What's special about them is that they are composable~~ ([not right](https://dev.to/totally_chase/comment/1hkdg)).

For an endofunctor `M` to be a monad, any arrow `f :: a → M b` must have a counterpart `f' :: M a → M b`. That's pretty much it.

This is cool, because it means we can compose functions that return monads.

_(example code is in Elm syntax)_
E.g., if we have a function that parses a string into a float `parseFloat : String -> Maybe Float` and a division function that returns `Nothing` is we try to divide by 0 `divide : Float -> Float -> Maybe Float` (see [dividing by 0](https://dev.to/drbearhands/extra-fundamentals-dividing-by-zero-1li5)), and we'd like to divide some number by the result of `parseFloat someString`.

The code `divide 7 (parseFloat someString)` wouldn't compile, because `(parseFloat someString)` is a `Maybe Float`, and `divide 7` takes a `Float`. Without monads, we'd have to do something like:
```
case parseFloat someString of:
  Just result -> divide 7 result
  Nothing -> Nothing
```
Forcing us to deal with the functor's internal structure explicitly.

With monads (and maybe is a monad), we can use [`andThen`](https://package.elm-lang.org/packages/elm/core/latest/Maybe#andThen), which converts a `a -> M b` to a `M a -> M b`, to _lift_ `divide 7 : Float -> Maybe Float` to `andThen (divide 7) : Maybe Float -> Maybe Float`. This lets us write:
```
andThen (divide 7) (parseFloat someString)
```
or, leveraging the `|>` operator:
```
parseFloat someString
|> andThen (divide 7)
```

Haskell doesn't have a standard `|>` operator, but combines `|>` with `andThen` to `>>=`.

```
parseFloat someString
>>= divide 7
```

I should note that Haskell (and probably other languages) has [a few more bells and whistles for monads](https://wiki.haskell.org/Monad). This is somewhat Haskell-specific as it relates to lazy evaluation and `do` blocks, so I'm not going to get into it at this point in time.

### Function signatures

Category theory also teaches us what 'better' functions look like in regard to composition. Now this is a rather vague argument based on how sums and products are defined in category theory, but it's rather self-evident:

If you have `f :: a → c` and `g :: b → c`, and some `h` exists s.t. `h :: a → b`, but no `h` exists s.t. `h :: b → a`, arrow `g` is 'better' than `f` for constructing `c`, since we'd also have `g ∘ h :: a → c`.

In other words, when in doubt, implement the simplest function. This is a rather like a formalization of the first two pillars of the UNIX philosophy:

> This is the Unix philosophy: Write programs that do one thing [...]. Write programs to work together. [...]

## Further reading

* See if you can find out why a [list](https://package.elm-lang.org/packages/elm/core/latest/List) is a monad.
* Try to think of a functor that isn't a monad. This might take you a while.
* I would heartily recommend further CT material by Bartosz Milewski. He has a [somewhat practical, written series](https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/) and a [video lectures series](https://www.youtube.com/playlist?list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_). I personally prefer the content of the later but the format of the former, as I find videos a bit too passive for this material, but find the more abstract concepts a stronger basis.