Not another Monad Tutorial

a word of caution

This is my second pass at this post and I’m using it to drive my understanding. I’m not confident everything is correct just yet. While the WiP tag is attached to this post, please take this information with a grain of salt.

A monad is just a monoid in the category of endofunctors, what’s the problem?

source by way of James Iry

If you’re interested in Functional Programming (FP) you have probably stumbled across the above quote. When you google it, you will find multipart essays and heated discussions with claims that some are getting it all wrong and others are gate keeping. A lot has been made of this quote, but it doesn’t hurt to remember James Iry included it as a joke at how complex FP can be to new-comers. Let us try to demystify the quote so that it doesn’t stop you from discovering the powerful concepts inside FP.

First let us start with some definitions:

monoid: A binary function combine: (A, A) -> A that is associative and combines with an identity element which leaves the other element unchanged.; Example:

import java.util.stream.Stream

object Monoid {
    val identity = ""
    val combine: (String, String) -> String = { a, b -> a + b }
}

fun main() {
    Monoid.apply {
        println("""Monoid: combine("a", "b") = """ + combine("a", "b"))
        println("- is associative: ")
        println("""  - combine("a", combine("b", "c")) = """ + combine("a", combine("b", "c")))
        println("""  - combine(combine("a", "b"), "c") = """ + combine(combine("a", "b"), "c"))
        println("""- identity does not change value: combine("a", identity) = """ + combine("a", identity))
        println("""- safely combines in parallel: Stream.of("a", "b", "c", "d", "e").parallel().reduce(identity, combine) = """ +
                Stream.of("a", "b", "c", "d", "e").parallel().reduce(identity, combine))
    }
}

endofunctor: An endofunctor is a container type with a map function that applies a transformation to the contained value. map returns the Functor with the transformed value and can be chained; note: endofunctors are a special type of functor which map to the same category. In most cases: the category is all kotlin types.; Example:

data class Functor(val value: String) {
    fun map(transform: (String) -> String) = Functor(transform(value))
}

val add_b: (String) -> String = {it + "b"}
val add_c: (String) -> String = {it + "c"}

fun main() {
    println("""Intialize: Functor("a") = """ + Functor("a"))
    println("""Map: Functor("a").map(add_b) = """ + Functor("a").map(add_b))
    println("""Chain map: Functor("a").map(add_b).map(add_c) = """ + Functor("a").map(add_b).map(add_c))
}

monad: So… if a monad is a monoid which works on the category of endofunctors you get the following:

import java.util.stream.Stream
data class Functor(val value: String) {
    object Monoid {
        val identity = Functor("")
        val combine: (Functor, Functor) -> Functor = { a, b -> a.map { it + b.value } }
    }

    fun map(transform: (String) -> String) = Functor(transform(value))
}

fun main() {
    val a = Functor("a")
    val b = Functor("b")
    val c = Functor("c")

    Functor.Monoid.apply {
        println("""FunctorMonoid: combine(a, b) = """ + combine(a, b))
        println("- is associative: ")
        println("""  - combine(a, combine(b, c)) = """ + combine(a, combine(b, c)))
        println("""  - combine(combine(a, b), c))= """ + combine(combine(a, b), c))
        println("""- identity does not change value: combine(a, identity)) = """ + combine(a, identity))
        println("""- safely combines in parallel: Stream.of("a", "b", "c", "d", "e").map{Functor(it)}.parallel().reduce(identity, combine)) = """ +
                Stream.of("a", "b", "c", "d", "e").map{Functor(it)}.parallel().reduce(identity, combine))
    }
}

Finally, we can define the Monad using map from the functor and flatMap using compose:

data class Monad(val value: String) {
    object Monoid {
        val identity = Monad("")
        val combine: (Monad, Monad) -> Monad = { a, b -> a.map { it + b.value } }
    }

    fun map(transform: (String) -> String) = Monad(transform(value))
    fun flatMap(transform: (String) -> Monad) = Monoid.combine(Monoid.identity, transform(value))
}

val add_b: (String) -> String = {it + "b"}
val add_c: (String) -> String = {it + "c"}
fun toMonad(t: (String) -> String) = { value: String -> Monad(t(value)) }

fun main() {
    val a = Monad("a")

    println("""Monad: a.flatMap(toMonad(add_b)) = """ + a.flatMap(toMonad(add_b)))
    println("- is associative: ")
    println(
        """  - a.flatMap(toMonad(add_b)).flatMap(toMonad(add_c))= """
        + a.flatMap(toMonad(add_b)).flatMap(toMonad(add_c)) )
    println(
        """  - a.flatMap{ toMonad(add_b)(it).flatMap(toMonad(add_c)) } = """
        + a.flatMap{ toMonad(add_b)(it).flatMap(toMonad(add_c))} )
}