Monads

Note: This is an exploratory post, where I will write about some ideas that are still fresh in my mind and need consolidation. Any mistake, lack of objectivity/rigour, that you find, please let me know. I also tried to balance between being practical and respecting the nomenclature. I started this post with Haskell and Swift in mind, but decided to remove references to the former wherever I saw fit. Finally, the code presented has been built against Xcode 6.1.1.

Intro

A tweet I saw a couple of days ago, describes to some extent, my feelings when I first started learning functional programming and Monads.

If you are like me, you can only get so far with abstractions until eventually you need concreteness. The problem is that Monads are a very abstract concept and, generally speaking, most of what you will find won’t be better than this:

In functional programming, a monad is a structure that represents computations defined as sequences of steps: a type with a monad structure defines what it means to chain operations, or nest functions of that type together.

Monads

One of the best examples I have seen, was in Chris Eidhof’s JSON Parsing in Swift where he uses Monads and Applicatives to parse a piece of JSON into an Array of objects: from a mundane and error-prone task, we get something that it’s safer and much more interesting.

So what is a Monad? A Monad is an abstract structure that has a couple of operations and obeys a few laws. So what could be an abstract structure?

  • Optional<T>
  • [T]
  • class Box<T>

Optionals, Lists and the class Box can all be seen as abstract structures:

  1. You don’t know what’s inside them. It’s abstracted from you, with the use of generics.
  2. It’s a structure, in the sense that it holds something for and “away” from you. If you want to get the inner value, you need to do it in a specific and safe way.

Operations

The most basic operation a Monad needs to have, is the ability to inject a value inside it. And as you might have guessed it’s simply an init:

public final class Box<T>
{
    let value : T

    public init(_ value : T) {
        self.value = value
    }
}

The second operation is called flatMap and it’s used to chain operations between Monads. Of course, depending on the Monadic type we have in hand, the flatMap is implemented in a different way (what makes sense for a List, doesn’t make sense for an Optional and so on). The idea of a flatMap is to map over the inner value of the Monad and return a new Monad with the map’s result. There is still some housekeeping to be done, in order to make this come together:

  1. What does it mean to map over a Box: if I give you a function and a Box, what should happen?
  2. What does it mean to flatten a Box: if I give you a Box nested in another Box, how can I get the inner Box? (you might be thinking why the hell would I have a nested Box? It will soon be clear).

The map could be implemented by extracting the Box’s inner value, applying a function to it and finally wrapping it up again:

func map <T,U>(box : Box<T>, f : T -> U) -> Box<U> {
    return Box(f(box.value))
}

The flattening is even easier:

func flatten <T>(box : Box<Box <T>>) -> Box <T> {
    return box.value
}

Finally our flatMap:

infix operator  >>=  {associativity left}
func >>= <T,U>(box : Box<T>, f : T -> Box<U>) -> Box<U> {
    return flatten(map(box,f))
}

The idea of flattening might make more sense now: because map is expecting a function from a T -> U and you pass a function that goes from a T -> Box<U>, the U in the map function is replaced by Box<U>. So by following the types and replacing them in your head the map becomes like this:

func map <Box<U>>(f : T -> Box<U>) -> Box<Box<U>>

Since you promise the compiler you would return a Box<U> you need to flat the value coming from the map.

With this in place we can start playing around:

let box = Box(4)
let sum3 = {Box($0 + 3)}
let toString = {Box(String($0 + 0))}
let iReallyLike = {Box("I really like the number " + $0)}

let luckyNumber7 = box >>= sum3 >>= toString >>= iReallyLike

This example might be silly, but this pattern is very powerful and used in many places, without people noticing it. So next time you see something that resembles this, you are probably using Monads.

Laws

There are three laws a Monad must follow in order to be one. In all three cases, x and y should be equivalent and yield the same result.

Left identity:

let f = {Box($0 + 1)}
let a = 1

let x = Box(a) >>= f
let y = f(a)

Right Identity:

func constructor<T>(value: T) -> Box<T> {
    return Box(value)
}

let x = Box(1)
let y = Box(1) >>= constructor

Associativity:

let double = {Box(2 * $0)}
let triple = {Box(3 * $0)}

let x = Box(1) >>= double >>= triple
let y = Box(1) >>= {double($0) >>= triple}

When I first saw these laws my initial though was: how could it be in any other way? The reality is that when using flatMap, one could easily change other internal state: incrementing a property, toggling a boolean, who knows? By verifying these laws, we make sure that what we have is truly a Monad.

Conclusion

Hopefully, I was able to demystify Monads a little bit. It took me some time to understand functional programming and Monads and, to be fair, I know very little. So my advise, if you are starting, is to fire up a playground and mess around with my code and reimplement everything from scratch.

Finally, the fact of being an extremely abstract concept is what makes it difficult to understand at first, but, at the end of the day, it’s pretty much a design pattern and one more tool in our developers’s toolbox.