First of all, I'm not a category theorist. These things just fascinate me, and I enjoy reading about this in my free time. I'm your ordinary "Joe, the programmer" working at a small software company.

Still, I find these things useful in my day job. Why? Because as a programmer I'm building mathematical machines (namely software) all day long and these concepts help me to order my thoughts and make at easier to reason about my software and design stuff.

In this blogpost I want to show how to derive Monads from what you already know and give names to things you maybe never even thought about.

**Categories**

Since monads come from Category Theory we first have to define what a

**category**is.

A category

**basically consists of 2 sets**

*C**ob*(

*) and*

**C***hom*(

*) where we call*

**C***ob*(

*) the*

**C****objects**of

**and**

*C**hom*(

*) the*

**C****morphisms**of

**. Morphisms are maps that go between objects.**

*C*Never saw a

**Category**in your every day programming? Sure? There is a

**Category**called

**, its objects are the Haskell types and its morphisms are Haskell functions. So you can think about that in a Scala context:**

*Hask*Let

`f`

be a function of type `Int => String`

. `Int`

and `String`

are both elements of *ob*(

*) and*

**C**`f`

is an element of *hom*(

*).*

**C**There's more to a

**Category**, we need to be able to compose morphisms and there has to be a special element called

**identity**. Lets looks at composition first.

Let f and g be functions:

```
f: A => B
g: B => C
```

We can compose those 2 functions in Scala by using the

`compose`

method to get a new function.
```
g compose f // yields a function of type A => C
```

OK, that's half the rent. Now we just need the special element called

**identity**which basically is a function that does nothing. It just takes a value and returns it unmodified. So when we

`compose`

a function `f`

with `identity`

we get back a function that is equivalent to `f`

and it should not matter if we compose `f`

with `identity`

or `identity`

with `f`

.
In short: The following 3 functions are equivalent (which means: when fed with the same input values they will yield the exact same result)

```
f // A => B
f compose id // A => B
id compose f // A => B
```

Now we know that a

**Category**is (well, at least we know enough to start, a real category theorist can take you on a breathtaking journey from here :)). Let's move on!

**Enter Higher-Kinded-Types**

Next "scary word", but again: You use them all the time. First we need to know what a

**kind**is. We know what types and values are. You can think of them as levels. A value like

`1`

and `x => x`

(that's a function value, yes those are values too!) live a the value level while types like `Int`

and `Int => Int`

live at the type level. We group values into types. `true`

and `false`

are both values of type `Boolean`

(think of types as sets of values).
OK, if we group values into types, can we group types? Yes, we can! We can group types into… *drumroll* KINDS! Now we have a third level and our world looks something like this:

```
kinds
---------
types
---------
values
```

In most languages we only deal with one kind called

`*`

(pronounced *type*) that groups all types, but there are languages that allow infinite levels (I might cover one of them in future blog posts).

We now have a basic idea of what kinds are, so what are

**higher kinded types**? Like High-Order-Functions (functions that take functions as arguments and yield functions e.g. compose)

higher kinded types are

**type constructors**that take type constructors as arguments and yield types (or maybe even

**type constructors**).

"Wait a minute… are you talking about generics?"

Think about

`List`

. It's not a type by itself, you need to feed it a type as an argument to get a type. This is called a **Type Constructor**.

`List`

takes one type and returns a type, hence `List`

has the kind `* -> *`

(this notation is borrowed from Haskell). The Scala notation for a **type constructor**like

`List`

is `List[_]`

.
So a

**higher kinded type**looks something like this:

`trait Functor[F[_]]`

where F could be a `List`

, `Option`

or any other **type constructor**that takes one argument.

**Functors**

Now that we have

**higher kinded types**, let's take a look at our functions

`f`

and `g`

from the beginning and lets add a **type constructor**

`F[_]`

to the mix (this is Scala notation and means: takes one type and yields a type). We can now produce a whole new set of types with this higher kind (e.g. `F[Int]`

, `F[String]`

etc.). We could now create functions that work with these types… hey I know this. This sounds like… a **Category**! Yes, it is! It's actually a

**Subcategory**of our

**Hask**

**Category**we introduced at the beginning. Let's call this new

**Category**

**(so we don't confuse it with the**

*D***type constructor**F). So elements of

*ob*(

*) would be something like F[A] and for*

**D***hom*(

*) it would be something like F[A] => F[B].*

**D**Now wouldn't it be cool if there was a morphism between those two categories, one that preservers composition and the identity rule? Something that could map a function of type

`A => B`

to a function of type `F[A] => F[B]`

? That's what's we call a **Functor**, it's a morphism between categories.

"Why is this useful?" you might ask. Just think about the kind of code reuse you could achieve. Let's look at

`Option`

as a concrete example. It's a **type constructor**. So how do we map a function of type

`Int => Int`

to a function of type `Option[Int] => Option[Int]`

? Can't you tell by now? The answer is the `map`

method of Option ;).
Let's check it out:

```
scala> val f = (_: Int) + 1
f: (Int) => Int = <function1>
scala> Some(1) map f
res0: Option[Int] = Some(2)
```

We could now reuse our function

`f`

with `Option`

, there was no need to write a special version of `f`

that works with `Option`

.
The second ingredient we need to make our

**Functor**complete is a morphism that maps a value of type

`A`

to a value of type `F[A]`

. In the case of `Option`

this is just the factory function:
```
scala> Some(_: Int)
res0: (Int) => Some[Int] =
```
scala> Option(_: Int)
res1: (Int) => Option[Int] =
scala> Option(1)
res2: Option[Int] = Some(1)
scala> Some(1)
res3: Some[Int] = Some(1)

**Endofunctors**

Now, let's assume that we want something like this:

```
scala> Some(1) map {
| case x if x % 2 == 0 => Some("YES!")
| case _ => None
| }
res1: Option[Option[java.lang.String]] = Some(None)
```

We want to use a function of type

`Int => Option[String]`

with `Option`

's `map`

method. But what's that? We get an `Option[Option[String]]`

. That's stupid, now I have to unpack one `Option`

to get the result I actually wanted.
What happened here? Remember how we mapped a function of type

`A => B`

to a function of type `F[A] => F[B]`

in the previous section about functors? What we did now is: we mapped a function of type `Int => Option[String]`

to a function of `Option[Int] => Option[Option[String]]`

. Yikes, we went a little bit over the top here, huh? We kind of like mapped something into an `Option`

and into an `Option`

this is how we ended up with an `Option[Option[String]]`

. You can think of this as a result of a composition of 2 `Option`

**Functors**.

This is a special kind of

**Functor**that maps a category into itself and is called an

**Endofunctor**

**Natural Transformations**

Now that we have morphisms between objects of a

**Category**which are Scala functions and

**Functors**which are basically morphisms between categories it's time to introduce morphisms between

**Functors**.

Why do we need this? Well in the last example we ended up with an

**Endofunctor**(we mapped a

**Category**into itself). We need to get rid of one of the

`Option`

s. We do this with a morphism that maps the composition of 2 **Functors**

*(*

**F***composed with*

**F***) to the*

**F****Functor**

*.*

**F**Lets do a concrete example that involves

`List`

```
scala> List(1,2,3) map { x => List(x + 1) }
res0: List[List[Int]] = List(List(2), List(3), List(4))
```

It happened again, but this time we ended up with a

`List[List[Int]]`

! We now need a **Natural Transformation**to join those lists together, this

**Natural Transformation**is called

`flatten`

in Scala.
```
scala> List(1,2,3) map { x => List(x + 1) } flatten
res1: List[Int] = List(2, 3, 4)
```

`List`

comes with a method that does both in one step, it's called `flatMap`

.
```
scala> List(1,2,3) flatMap { x => List(x + 1) }
res2: List[Int] = List(2, 3, 4)
```

This enables us to chain functions together in a very convenient way.

```
scala> Some(1) flatMap { x => Some(2) flatMap { y => Some(x + y) } }
res3: Option[Int] = Some(3)
```

or a little more concise

```
scala> Some(1) flatMap { x => Some(2) map { y => x + y } }
res4: Option[Int] = Some(3)
```

**Monads**

This is actually what makes up a

**Monad**. It's an Endofunctor with two

**Natural Transformations**called

*unit*and

*join*(which is called

`flatten`

in Scala). They are such a fundamental concept that Scala features a syntactic sugar for them, the `for`

-comprehension. Do NOT confuse this with a mere `for`

-loop, this is a different animal. The last example above can be written in the following way:
```
scala> for {
| x <- br="" some=""> | y <- br="" some=""> | } yield x + y
res5: Option[Int] = Some(3)
//translates to
scala> Some(1) flatMap { x => Some(2) map { y => x + y } }
res6: Option[Int] = Some(3)
```

**Conclusion**

This is an introduction on how to think about

**monads**and how to derive them from simple building blocks. They are a very powerful abstraction that pops up all the time. You use them all the time without knowing. Since programming is all about abstraction it's useful to recognize those underlying patterns. Don't let others fool you into believing that this is just some bizarre functional stuff that has no use in the real world. This is just the tip of the iceberg, an amazing journey lies ahead. Let's learn!

## Kommentare:

Excellent! Thank you!

Nice write-up, thanks. I have some comments, though:

Call me picky, but categories are not necessarily restricted to sets, but more generally to collections of objects, which could also be classes. Not too important for computer science, though.

In the functors section there is a typo: It should be "... and for hom(D) it would be ..."

fmap(akamap) is all a functor needs. If you add the "factory" functionpure(akaunitaka ...) you end up with a pointed functor.In my opinion your explanation of endofunctors is misleading: You are still mapping from category C to category D. In your example

Int => Option[String]is an element of hom(C) (withIntandOption[String]elements of ob(C)) andOption[Int] => Option[Option[String]]is an element of hom(D) (withOption[Int]andOption[Option[String]]elements of ob(D)).Well, as D is a subcategory of C you have indeed an endofunctor, but that's true of every functor in a program, because they will always deal with types and functions, right? Therefore "your" endofunctor is not that special ...

Hi Heiko,

Yes, you are absolutely right. Endofunctors are indeed not THAT special in this situation (http://stackoverflow.com/questions/3273373/are-all-haskell-functors-endofunctors). I just wanted to point out what they are since monads are sometimes explained as "Endofunctors with 2 Natural Transformations" (I also left out monoids etc.). I find them to be quite a good vehicle to explain what's happening. Of course others might think different about this.

Being picky is a good thing ;) Keeps the mind healthy.

Regards!

Nice post, thanks. Is there a book or article you would suggest for those who woule like to learn more about this subject?

@Julio: The Haskell Wiki http://www.haskell.org/haskellwiki/Haskell has a lot to offer about this topic.

Regards!

>> elements of ob(D) would be something like F[A] and for hom(F) it would be something like F[A] => F[B].

you meant hom(D)? :)

@tuxslayer: Thank you. Fixed ;) Heiko already pointed that out but I somehow always forgot about it ^^

Kommentar veröffentlichen