Here's a short intro to programming for a category theory person. Programming types, like int
, bool
, string
, etc., are objects in a category. Functions between them are morphisms. So, essentially, you are working with something like Set, modulo non-terminating computations.
Polymorphic types, which are types that depend on other types, are usually endofunctors. The mapping on objects (types) is called a type constructor. You construct some type T a
from an arbitrary type a
. A standard example is a list of a
which, in Haskell, is [a]
. In C++, a common example is vector<T>
.
An endofunctor must also map morphisms. This mapping is called fmap
in Haskell. In other languages there is no common name for it. In C++, for instance, it's called transform
when acting on containers (simplest kinds of endofunctors).
You probably know a monad as an endofunctor with two natural transformations [math]\eta[/math] and [math]\mu[/math]. Natural transformations are, roughly speaking, polymorphic functions. So you need one function, [math]\eta[/math], that takes a value of an arbitrary type a
and returns a value of type T a
. In Haskell this function is called return
. The other function, [math]\mu[/math], is called join
, and it flattens a double application of T (T a)
to a single application of T a
.
A list is a simple example of a monad.
[math]\eta[/math] or return
takes a value x
and returns a singleton list [x]
.
[math]mu[/math] or join
takes a list of lists and return a single list. That's just list concatenation.
My favorite example of a monad is the future monad in C++. You start a thread to calculate a value of some type T
. But you don't get the result immediately. Instead you get a future<T>
. That's your type constructor. The action on morphisms is defined as a (polymorphic) function then
, which applies a function to a future.
[math]\eta[/math] is called make_ready_future
. It creates a fake future that contains a given value.
[math]\mu[/math] is called unwrap
; and there is also a more useful combination of then
and unwrap
, which is called then
(in C++ you can overload the same function name to do two different things).
Monads are ubiquitous in Haskell where they are used to implement IO, exceptions, continuations, parsers, and so on. You can find them in other languages too, but they are more obfuscated.