Monoids and mconcat: reducing over types

GET THE CODE: https://github.com/tb01923/functional-js-workshops/blob/master/monoid.js

In a previous post I walked through deriving some basic list processing functions starting with reduce and leveraging that to implement a few others. Reduce should beused when you want to combine a list down into a single value. It is defiend with three inputs: a combiner, an initial value, and a list of inputs. A general abstraction on this concept is a Monoid, a higher kinded type that allows combination. You can combine objects such as Integers with Addition or Multiplication, Booleans with Any or All... Before we jump in I want to issue a brief disclaimer: I get this is JavaScript which lacks some of the sophistication of more traditional functional languages, but I am doing it anyway.

According to fantasy land a Monoid needs to provide the methods: concat and empty. Concat is the work horse that is used to combine two instances together while empty provides a neutral instance. A simple example of a Monoid is Additive, which can be used to Sum a list of Additive types. One could implement it like this:

const Additive = function(v) {
    this.v = v
}

Additive.empty = new Additive(0)
Additive.prototype.concat = function(other) {
    return new Additive(this.v + other.v)
}

// combine
mconcat(new Additive(2),  new Additive(3))
//=> Additive(5)

From a functional perspective this isn't ideal as the class Additive is mutable (concat and empty can be redefined) and we allow direct access to the inner variable v. We also should be providing the method equals, and a way of abstracting object creation. We can write:

const Additive = function(v) {
    this.v = v
}
Additive.of = (x) => new Additive(x)
Additive.empty = Additive.of(0)
Additive.prototype.getValue = function() {
    return this.v
}
Additive.prototype.equals = function(other) {
    return this.getValue() == other.getValue()
}
Additive.prototype.concat = function(other) {
    return Additive.of(this.v + other.v)
}

// combine
mconcat(Additive.of(2),  Additive.of(3))
//=> Additive(5)

This is getting better, but we haven't addressed mutability and I really don't like the idea of constructing each instance with the of method. So we can abstract that away too:

const getInstance = (self, constructor) =>
    (self instanceof constructor) ?
        self :
        Object.create(constructor.prototype)

const Additive = function(v) {
    const self = getInstance(this, Additive)

    // v is immutable from closure 
    self.getValue = () =>
        return v 

    self.equals = (other) =>
        this.getValue() == other.getValue()

    self.concat = (other) =>
        Additive.of(this.v + other.v)

    return Object.freeze(self)
}
Additive.of = (x) => new Additive(x)
Additive.empty = Additive.of(0)

// combine
mconcat(Additive(2), Additive(3))
//=> Additive(5)

While that is a pretty good definition, I don't want to have to repeat it every time I define a new type - especially because the only things that change are the concat AND the empty functions. So we can easily transition this into a type constructor which will take an empty value and a function to perform the combining and return a Monoid of some type. Disclaimer: my intent is to make my type fantasy-land compatible which means I need to leverage the function names they define. They defines these in their specification and it is advised that you pull them into your project and use the index notation (obj[method]) to define the implementations. This style takes some getting used to.

const {empty, of, concat, equals} = require('fantasy-land');

const monoidTypeConstructor = curry(function(_concat, _emptyValue){

    const getInstance = (self, constructor) =>
        (self instanceof constructor) ?
            self :
            Object.create(constructor.prototype)


    function Monoid(value){

        const self = getInstance(this, Monoid)

        self[concat] = other =>
            Monoid[of](
                _concat(self.getValue(), other.getValue())
            )

        self.getValue = () =>
            value

        self[equals] = (other) =>
            Monoid[equals](self, other)

        return Object.freeze(self)
    }

    Monoid[empty] = () =>
        Monoid[of](_emptyValue);

    Monoid[equals] = curry((a, b) =>
        a.getValue() === b.getValue()
    )

    Monoid[of] = (x) =>
        Monoid(x);

    return Object.freeze(Monoid)
})

const add = (a, b) => a + b
const Additive  = monoidTypeConstructor(add, 0)


// combine
mconcat(Additive(2), Additive(3))
//=> Additive(5)

I think this is a pretty good implementation. I suppose you may want to be able to configure equals as well - but that shouldn't be too hard to implement. With this type constructor we could use this to create a type to combine Integers with multiplication too:

const mult = (a, b) => a * b
const Multiplicative  = monoidTypeConstructor(mult, 1)


// combine
mconcat(Multiplicative(2), Multiplicative(3))
//=> Multiplicative(6)

mconcat is essentially an abstraction of reduce that works on monoids. Two of three inputs to reduce can be satisifed by the monoid type itself:

1. the intial value: T.empty
2. the combining function: a.concat

To ease getting these values we define the helper functions mempty and mappend - again using the fantasy land function names. To get access to the type level definition of empty, we take an instance (a) and access the constructor property, which essentially returns the type constructor where thee type level methods live.

const mempty = (a) =>
    a.constructor[empty]()

const mappend = (a, b) =>
    a[concat](b)

With reduce in head from the previous article we can easily write mconcat:

const mconcat = (xs) =>
    reduce(
        mappend,
        mempty(head(xs)),
        xs)

So when you have a list of monoids you want to reduce, mconcat will handle that for you without having to provide the initial value or the combining function (since they are already wrapped up in your type), which should lead to simpler application code.

Why go through all of this?

Secondly, and in more general terms, it signifies because of the associativity of monoid operations that those operations on your data structure  can be parallelized in order to utilize multiple CPU cores efficiently.

There is plenty more to read on the internet such as here: http://www.michael-noll.com/blog/2013/12/02/twitter-algebird-monoid-monad-for-large-scala-data-analytics/

I will try and get another post out this week walking you through testing the monoid type constructor using the fantasy land specification. If I have misrepresented any ideas or can improv upon my code - please let me know. I am always looking to improve!