Karumi Blog

Monad: From Category Theory to Swift

Davide Mendolia -

The concept of Monad comes from a branch of mathematics called Category Theory. In software design a monad can be referenced as a design pattern, which was formally introduced by Haskell 1.3 (in May 1996) to solve the problematic of I/O, in order to find a way to compose input and output function and handle error cases.

A Monad is a Container with a mechanism of Function Composition! The first part of this article is about Monoid and how to build function composition, and the second part is about Monad and how to apply function composition to a container.
All the code example in this article will use the Swift 2.0 syntax, but it can be rewritten in any language that have lambdas and generics.

Monoid

In category theory, a monoid is an object that has these two properties:

  • An operation that compose two elements of the same type.
  • A zero element, also called unit.

And follow the rules of:

  • Associativity
  • Neutral element

Although the theory is very nice, let's do an example using Integer as type and Multiplication as operation.

  • Operation: *
  • Unit: 1
  • Associativity: (a * b) * c == a * (b * c)
  • Neutral element: 1 * n == n * 1 == n

Example:

  • Associativity: (42 * 4) * 2 == 42 * (4 * 2) == 336
  • Neutral element: 1 * 47 == 47 * 1 == 47

We can see here that Multiplication of Integer is a Monoid.

This is the Monoid protocol not only for Integer but for any given type in Swift.

protocol Monoid {
    typealias ItemType
    var unit: ItemType { get }
    
    func compose(left left: ItemType, right: ItemType) -> ItemType
}

Now, because in Swift functions are first-class citizens. Let's define a Monoid that use function as type "T -> T".

  • Associativity: compose(compose(f,g),h) == compose(f,compose(g,h))
  • Neutral element: compose(unit,f) == compose(f, unit) == f
struct MonoidOfFunction<T>: Monoid {
    let unit: T -> T = { $0 }
    
    func compose(left f: T -> T, right g: T -> T) -> T -> T {
        return { g(f($0)) }
    }
}

The unit function is simply a closure that returns its input param.he compose method is returning a closure that passes the right function the result of the execution of the left function using the first input as parameter. This is function composition.

m.compose(f: m.compose(f: {$0 * 20}, g: {$0 / 5}), g: {$0 + 75})(47)

A monoid does not allow us to transform a Int in a String. To make this kind of operation there is a different slightly implementation called Monoidal Category, which is basically the same idea but with the ability to change the return type of the operands.

struct MonoidalCategoryOfFunction<T>: Monoid {
    let unit: T -> T = { $0 }// Or Identity

    func compose<U, V>(left f: T -> U, right g: U -> V) -> T -> V {
        return { g(f($0)) }
    }
}

Now that the concept of function composition is clear, let's see what a Monad is.

Monad

A monad is a container of a type that helps us to implement programming concepts like I/O, error management, concurrency, continuation and many more. In this article we will describe the general concept of monad (the implementation of some of theses concepts will come in a future article!).

Monad, like Monoid, should also obey to the same property of associativity and neutral element. These properties are called monadic laws. In practice, we will never implement the unit function, because it's implementation is trivial as we seen in the monoid, So we will assume that Monad have obey the neutral element law.

protocol Monad {
    typealias MonadType
    var value: MonadType { get }
    
    func compose(left left: MonadType -> Self, right: MonadType -> Self) -> MonadType -> Self
}

This looks, familiar now that we know what a monoid is, but first big WARNING do not confuse unit monoid and value of Monad.

  • value: is the value contain in the Monad, remember that we said Monad is container.
  • compose: is a method that compose 2 function and return a function.

Now let see an implementation of Monad.

    static func compose<T, U, V>(left f: T -> Monad<U>, right g: U -> Monad<V>) -> T -> Monad<V> {
        return { g(f($0).value) }
    }

We take the result of the first closure, get the value and we pass it to the second function.

But in practice the left closure is always a closure calling the constructor of the monad with the value passed in params. Like the following:

{ Monad(value: $0) }

So we will omit the first closure and replace it by the monad.

    static func compose<U, V>(m: Monad<U>, right g: U -> Monad<V>) -> Monad<V> {
        return g(m.value)
    }

Now that we have a object one side and a function on the other let's rewrite in OOP fashion. That will allow us, to do chaining of function.

struct Monad {
    func compose<V>(g: W -> Monad<V>) -> Monad<V> {
        return g(self.value)
    }
}

We can do better and move the responsibility to initialize the monad inside the function composition and only have the effect in the closure.

struct Monad {
    func compose<V>(g: W -> V) -> Monad<V> {
        return Monad<V>(value: g(self.value))
    }
}

So now we can do some nice function chaining/composition. This implementation of monad, is called Identity Monad and generally the compose function is called bind. And with we can do the following kind of chaining:

IdentityMonad(value: "Hello World")
    .bind({$0.stringByReplacingOccurrencesOfString("World", withString: "Everybody!")})
    .bind(print)

IdentityMonad(value: 47).bind{"\($0)"}.bind {Array($0)} == ["4", "7"]

With this article you know what are the rules and properties that define a Monad, most of the flatMap implementation are monadic, but having a flatMap method in your class does not automatically define you as a Monad.
We will see in a future articles what Monad it can be useful for and different implementation to do I/O or error handling.

Spoiler: Optional is a Monad ;)

References