What is a Monoid?

Monoid is a property of a system which satisfies these three laws:

Well, that sounds a bit abstract. Indeed. Well, is this any useful in programming? You bet it is.

This post is entirely about understanding what a monoid is, with ideas we (OOP) programmers already know. To do so, I will do a addition on data models (bill) and then discuss the flaws, our imperative system has. And then, we will see how monoids naturally come to our rescue.

One thing you need to have in mind as we go is that all we are trying to do is composability of smaller functions to build something useful.

Monoid is not a direct relative of Monad. It is not a semi-monad or a smaller form of Monad. Its a separate concept that has not much to do with Monad

Lets establish a mental picture of monoid now!

Monoid Of Int

With that picture in mind, let move on!

Problem

Let say we are making a POS(Point Of Sale) application where given a bunch of BillReceipts we need to calculate and print the total amount. Jack happens to be our loyal frequent customer.

Lets assume the data model for the BillReceipt is as follows:

struct BillReceipt {
    let name: String
    let quantity: Int
    let totalPrice: Double
}

And here we have a list of items Jack ordered.

let mangoBill = BillReceipt(name: "Mango", quantity: 2, totalPrice: 1.5)
let orangeBill = BillReceipt(name: "Orange", quantity: 3, totalPrice: 2)
let spagettiBill = BillReceipt(name: "Spagetti", quantity: 1, totalPrice: 2.1)

// then
let allReceipts = [mangoBill, orangeBill, spagettiBill]

Now we need to total them up and ask for money. Fair and easy. Lets do this.

We will now go through couple of ways one might tackle this problem. However, our aim is to eventually refine to and try to reach a monoidal approach. Lets get going.

1. Imperative (Von Neumann’s Word at a time processing)

func total(_ bills: [BillReceipt]) {
    var totalPrice = 0.0
    var totalQuantity = 0

    for index in allReceipts {
	// Picking each element:: Von Neumann's Word at Time processing
        totalPrice += index.totalPrice
        totalQuantity += index.quantity
    }
    
    print("Impure Totaling Fucntion:")
    print("Total")
    print("Quantity \t\t",totalQuantity)
    print("Total Price \t", totalPrice)
    print("\n")
}

Disucssion:

2. Functional (Declarative)

let total = allReceipts.reduce((0.0, 0)) { ($0.0 + $1.totalPrice, $0.1 + $1.quantity) }

// Printing is left out intentionally

Discussion:

3. Monoidal Addition:

//1.
extension BillReceipt {

    static func add(_ first: BillReceipt, _ second: BillReceipt) -> BillReceipt {
        let addedPrice = first.totalPrice + second.totalPrice
        let addedQuantity = first.quantity + second.quantity
        let addedName = "Total"
        return BillReceipt(name: addedName, quantity: addedQuantity, totalPrice: addedPrice)
    }

}

//2.
let totalPureMonoidal = allReceipts.reduce(WHATDOIPUTHERE, BillReceipt.add)

Here, we defined a add as type function that takes two BillRecipts and returns added result in a BillReceipt. This is the First Law of Monoid called Closure Property.

Nice!!! (It really doesnot matter if this is a instance or type function. I chosed type function because its easy to plug into list.reduce. See point 2 above)

Make note of WHATDOIPUTHERE up in the code. So what is the initial value? Lets take a moment and do addtion on Ints and String.

let sum = [1,2,3,4].reduce(0, +)
let product = [1,2,3,4].reduce(1, *)
let joinedString = ["Hello", "  ", " there ", "^-^"].reduce("", +)

// Keep an eye on this one too
[1,2,3,4].reduce(0, -)

All of this above methods have a clear defined inital values.

From the above observation, Its obvious that the initial Value for reduce is more likely the identity for Types operation. Now the question is, what is the identity for our BillReceipt type’s add() function?

Searching for BillReceipt Identity

So lets default all the values of member to their identity and hope we will find one.

extension BillReceipt {
    init() {
        name = ""
        quantity = 0
        totalPrice = 0
    }
}

So here we are:

let totalPureMonoidal = allReceipts.reduce(BillReceipt(), BillReceipt.add)

Disucssion:

extension BillReceipt {

    static func add(_ first: BillReceipt, _ second: BillReceipt) -> BillReceipt {
        let addedPrice = first.totalPrice + second.totalPrice
        let addedQuantity = first.quantity + second.quantity
        let addedName = "Total"
        let addedPricePerItem = ...... //WATTTT TO DO HERE
        return BillReceipt(name: addedName, quantity: addedQuantity, totalPrice: addedPrice)
    }

}

Associativity

First off, lets get this associativity right.

These are associative as the order of operation application doesnot matter.

(1 + 2) + 3 == 1 + (2 + 3)
(4 * 5) * 7 == 4 * (5 * 7)
("Hello " + "there") + "Monoid"  == "Hello " + ("there" + "Monoid")

However, substraction satisfied identity and closure property but it doesnot hold true for associativity.

(1 - 2) - 3 != 1 - (2 - 3)

Thus, from the laws for monoid.

However,

What about add on BillReceipt?

Why the fuss? Why the Monoid?

Before going too far, lets appreciate what have we got from Monoids.

Benifits of Associativity

Benifits of Closure

Identity

Identity helps us answer what do we do in these situations:

[].reduce(BillReceipt(), BillReceipt.add)
[Int]().reduce(0, +) //sum of empty list of ints is 0

Sum it up

Despite the fact that we didn’t saw much of theory behind Monoid and how category theory pictographically describes Monoid, we did create a Monoid for us. The above problem helped us understand that if we end up having a Monoid, we can do list comprehension using reduce for free. We can parallelize and incrementally add operations on to the result.

In the end, if I have one senetence to sum it up: Monoid is a way to describe aggregation pattern. List comprehension using reduce is just a prime example of it.

swift  fp  monoid 
comments powered by Disqus