Monads scare a lot of programmers. A) Its a weird word. B) A lot of academic ass holes use it to feel superior. I’d like to change that. So here’s my guide to three common type theory abstractions: Monoids, Functors, and Monads. I hope to help you understand these type abstractions by looking at types you already use in programming. This is a short introduction to these topics, and is aimed at programmers familiar with functional programming.

Disclaimer: I am not a type theorist. This guide is not written in the style of a mathematics class. It is instead aimed to help those not familiar with abstract mathematics become familiar with constructs they can use to help them.

Abstractions

Abstractions are key to writing any complex program. Human brains cannot handle the amount of knowledge required to program in today’s world without abstractions. These abstractions allow a programmer to think on a “higher level.” Take jQuery, for instance, which provides $.ajax() to perform an HTTP AJAX request from the browser. A programmer doesn’t have to consider each browser’s implementation of AJAX, just what his or her app needs in the HTTP request.

The type theory abstractions below are each defined as a “typeclass” or “interface” that different concrete types implement. Each type can implement the typeclass with different functionality, but they all satisfy the “laws” or “rules” of that abstraction. This allows programmers to decouple their code from concrete types and instead couple with one or more type abstractions.

Notation

I will be using Haskell-style type syntax. It looks like this:

-- fn0 is a function of zero arguments returning a type a
fn0 :: a

-- fn1 is a function of 1 argument of type a and returns type b
fn1 :: a -> b

-- fn2 is a function of two integers, returning a string
fn2 :: Integer -> Integer -> String

-- fn3 is (a c) -> b, where a is a type function with c as its argument
-- type functions are like container types, such as Array<C> in Java
fn3 :: (a c) -> b

-- fn4 is like fn3 but a must be a monad (i.e. must satisfy the typeclass/interface)
fn4 :: (Monad a) => (a c) -> b

-- fn5 takes a function as an argument and calls it with 0
fn5 :: (Integer -> Integer) -> Integer
fn5 f = f 0

-- fn6 calls map with an increment (as an anonymous function) on an array
fn6 :: Array Integer -> Array Integer
fn6 arr = map (\x -> x + 1) arr

-- MyEquality is a typeclass (interface) that has some functions
class MyEquality a where
  equals :: a -> a -> Bool

-- SomeType is implementing the typeclass MyEquality
-- here the function name is equals, x and y are arguments
-- the body of the function is after the first equal sign
instance MyEquality SomeType where
  equals x y = (x == y)

Monoids

A monoid is a typeclass that has a “zero” and can be appended. It must implement two functions:

class Monoid a where
  mempty :: a
  mappend :: a -> a -> a

-- Monoid laws:
-- mempty is an identity
mappend x (mempty) = x
mappend (mempty) y = y
-- Associativity
mappend x (mappend y z) = mappend (mappend x y) z

The mappend function combines two instance of a monoid and returns another instance of it. We do this all the time in programming. There are so many structures in programming that implement this interface: lists, arrays, sets, numbers, maps. Let’s implement a couple for example:

class Monoid Integer where
  mempty = 0
  mappend x y = x + y

class Monoid (List a) where
  mempty = []
  mappend x y = concat x y

So why is this type useful? Why wouldn’t a programmer just use +, concat, or merge, as appropriate for the type in question?

First, the reduce function does very similar work to this. Its type signature is:

reduce :: (a -> b -> a) -> a -> [b] -> a

What if we redefined reductions with monoids?

-- reduceMonoid is often called msum
reduceMonoid :: (Monoid a) => [a] -> a

Hey, reduceMonoid looks a lot like List’s flatten and Integer’s sum doesn’t it? Thats because those two functions are just monoid summations from a list of values.

Ok, we established that monoids (and monoid reductions) are used all the time, but still, why wouldn’t I use the appropriate function for the appropriate type?

The answer comes when creating container types, that is, types that contain other types. A common type container is the Maybe a type, which either contains a value of type a, or nothing. This is sometimes called Optional (Java 8 and Swift have Optional<A>).

-- (Maybe a) is a haskell type with possible values Nothing, or (Just v)
-- where v is of type a.
type Maybe a = Nothing | Just a

instance (Monoid a) => Monoid (Maybe a) where
  mempty = Just (mempty)
  mappend x y = case (x,y) in
                 (Nothing, y) -> y
                 (x, Nothing) -> x
                 (Just x, Just y) -> Just (mappend x y)

Here, we see how we can use the monoid functions on a type Maybe a, only when the inner type a is a monoid type. In Java 8 lingo, this means that Optional<List<A>> can be appended to because it wraps a type that can be appended to.

Functors

A functor is a very simple container type with one function:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

-- Functor laws
fmap identity x = x
fmap (compose f g) x = fmap f (fmap g x)

Functors are any container type where a programmer can manipulate the value inside the container. The most common example is the list’s map function:

instance Functor List where
  fmap f x = map f x

This abstraction, however simple, is very powerful. Consider the following node.js code:

function asyncFmap(someAsyncCall, someMappingFunction, callback) {
  someAsyncCall(function (err, val) {
    if (err)
      callback(err)
    else
      callback(null, someMappingFunction(val))
  })
}

function promiseFmap(promise, someMappingFunction) {
  return promise.thenSync(someMappingFunction)
}

This is a very common action in node.js, mapping a future value using callbacks. Then we’ve shown the same action using promises. A promise is a container type, which allows access to the value inside it. Therefor a promise is a Functor, and the thenSync function is its fmap!

Again, you might ask, why would I use fmap() instead of .thenSync() or map()? The Functor abstraction is so simple that it is trivial for many types ot implement. As soon as I see some new type is a Functor, I immediately know how it acts under the functor laws, and that I can then pass it into any of my code that handles functors (and not just a specific functor such as a list).

All the container-like structures are functors, such a lists, sets, and maps; but also trees, and graphs. Promises and streams are functors too. That means that synchronous code meant for lists can be applied to asynchronous streams of data. Also, any monad talked about in the next section is also a functor.

Monads

Monads are a lot like Functors: they contain a type and allow the programmer to manipulate the type inside in a certain way. But they allow a more complicated version of inner manipulation to happen. Instead of going straight to type signatures, lets check out a couple monads.

I introduced the Maybe (aka Optional) type earlier. Here’s some functions that are useful with the Maybe type:

-- createMaybe constructs a maybe type with value (Just v)
createMaybe :: a -> Maybe a
createMaybe x = Just x

-- step is a function to be used in a set of computational steps
-- step takes a current value `v :: Maybe a` and a function `f :: a -> Maybe b`
-- If v is Nothing, step returns Nothing
-- If v is (Just x), step returns (f x)
step :: Maybe a -> (a -> Maybe b) -> Maybe b
step Nothing _ = Nothing
step (Just x) f = f x

-- myComputation does a 3 step computation using the maybe step function
myComputation = let s0 = createMaybe 0
                    s1 = step s0 step1Computation
                    s2 = step s1 step2Computation
                    s3 = step s2 step3Computation
                in s3

This seems to be a reasonable way to create a 3-step computation where any one step might fail. Now lets consider a similar example with promises:

-- createPromise constructs a promise type with a value resolved inide of it
createPromise :: a -> Promise a
createPromise x = Resolved x

-- thenAsync is the asynchronous version of thenSync
thenAsync :: Promise a -> (a -> Promise b) -> Promise b

asyncComputation = let s0 = createPromise "http://google.com"
                       s1 = thenAsync s0 step1AsyncComputation
                       s2 = thenAsync s1 step2AsyncComputation
                       s3 = thenAsync s2 step3AsyncComputation
                   in s3

This also seems like a reasonable way to construct a 3-step serial asynchonous task. Perhaps we can abstract this functionality into a common typeclass.

class Monad m where
  return :: a -> m a
  bind :: m a -> (a -> m b) -> m b

-- Monad Laws:
bind (return a) f = f a
bind m return = m
bind (bind m k) h = bind m (\x -> bind (k x) h)

A monad is a container type that implements two functions:

  • return creates a monad type wrapping the value given
  • bind takes a current monad value and a function of that inner value to a new monad value and returns a new monad value.

The bind function can be hard to visualize, so think of its examples:

  • The Promise’s thenAsync function to serially append an async computation
  • The Maybe’s step function (defined above) to continue calculation only if Nothing has not been encountered
  • The List’s flatMap function, which maps values to lists and concatenates them (aka list comprehension)

Once you understand how a particular monad implements bind, you can use it with higher-level functions that call the return and bind functions insde them. One of those is do-notation, which allows one to write imperative-looking monad bind statements simply, leveraging the power of the underlying monad. I won’t cover do-notation here, but if you are interested, search it out.

Combining Types

I want to point out something about Functor and Monad. Here are the type signatures of fmap, bind, and for clarity bindFlipped:

bind :: m a -> (a -> m b) -> m b

-- Bind with arguments flipped
bindFlipped :: (a -> m b) -> m a -> m b

fmap :: (a -> b) -> f a -> f b

Look how similar the type signatures of bindFlipped and fmap are. They are both functions that allow manipulation of their inner values. In fact, any monad can implement fmap using bind and return:

fmap f m = bind m (\x -> return (f x))

Think of the Promise type: thenSync is fmap and thenAsync is bind. Using these two abstractions, we can represent both synchronous and asynchronous serial computations in this way.

But what about asynchronous parallel computations? If we cannot represent all the actions on a type using common type-theory abstractions, then the facade of abstractions break down. This is where monoid comes into play. We can use the monoid typeclass to wait on multiple promises in parallel, and combine them using the inner type’s monoid implementation.

Here’s the full specification of the typeclasses of Promise (with no implementation).

type Promise a = Resolved a | Future

instance Functor Promise where
  fmap f p = thenSync p f

instance Monad Promise where
  return x = Resolved a
  bind p f = thenAsync p f

instance (Monoid a) => Monoid (Promise a) where
  mempty = Resolved (mempty)
  mappend p1 p2 = thenSync (waitForAll [p1, p2]) (\[v1, v2] -> mappend v1 v2)

Conclusion

I hope you’re convinced that these abstractions are in fact, not very complicated. As we’ve seen, types that implement these abstractions show up a lot in programming.

However, you may not be convinced that they are useful abstractions. I encourage you to start to view the types you use every day as implementing different these different patterns. When you start to see the world in this way, you can create your own abstractions that are decoupled from individual types, and instead operate on these abstractions detailed here.

Using Monads

Here are some implementations of algebraic structures in your language: