Day 11 - Appreciating Mathematics and Monoids

As stated in my last post, I started reading the chapter on Monoids from the Haskell Book. It’s such a brilliantly written chapter, I almost feel like an enlightened being.

For anyone who’s tinkered with Haskell, or attempted to learn it previously like me, or trying to learn right now like me, or even just read StackOverflow answers and Reddit posts about it, you probably already know how close mathematics is to Haskell and Functional programming in general. A lot of type theory, category theory and lambda calculus is involved in Haskell. Although most Joe programmers can make it through without the mathematical baggage, my recent experience with this book and learning Haskell from it has made me realize that the average Joe can get a lot of mileage out of understanding a few mathematical concepts than running away from them. Anyway, story time.

I’m not good at mathematics, I barely passed high school with it. Years of studying the subject in fear and the resulting shame in doing not so great at it has led many people, including me, to hold a grudge against it. It often ends up at making up our minds that we just suck at it, that it’s a subject for the students scoring 99/100 in the exam, who lost 1 mark at some silly spelling mistake. The fact that Indian societies love glorifying the kid who got 99/100 in front of those that barely passed the subject didn’t help it either. It’s the subject for the sharpest of minds, lowly peasants like me should just stay off its trajectory.

Or so I thought till I made the decision a couple of years ago to not pursue my education. I decided not to go to college. My marks were bad enough as they were, and on top of that, what passes off as the syllabus for even the acceptable colleges in my country, they looked worse than my mark sheet. And I was fed up of the whole routine of studying in a bad college because I had bad marks, having a bad education at a huge expense, a useless degree at the end of four long years to work at ABC company as a junior developer after begging for an internship at XYZ company in one of the summer breaks. It looked vicious and I wanted a way out, so I just didn’t go to college.

It took my parents a huge amount of convincing and a job offer from a very popular company for them to finally let me come to Bengaluru, where I currently live, and study and work here on my own. I ended up not taking the job because of a lot of reasons, but I got into freelancing and things went fine. Best part, I get to study my own syllabus, and I was going to exclude all forms of mathematics from it.

That’s how things went till I started studying Algorithms. You’d often find a lot of books that take an induction-based approach to solving problems. At first it immediately put me off. The only previous exposure I had to Induction was in my 11th year of high school, and I hated it. You could say that’s another fault of textbooks here, we are taught what something is in mathematics, how to solve a problem that involves it, but very very very rarely how that knowledge will ever translate to something usable in the real world.

And using induction to come up with a problem’s solution was just black magic to me, and sometimes, it still is even now. But being free from a college education comes with its own set of advantages. No one’s going to judge me this time for sucking at it. There isn’t going to be a mark sheet that’s going to be presented to the whole world that says in big bold letters that I got 36/100. Yes, I was that bad. No pressure of doing better than your classmates, no pressure from your parents to save their dignity in front of the neighbors and relatives, just mathematics and me, trying to come to terms with each other. So I continued reading whatever I was reading, mathematics included.

To my surprise, I was actually getting it and solving the chapter-end exercises. From proofs on binary trees to finding paths in a directed acyclic graph to coloring sections in a plane, I was finally getting it. Back in high school, Induction was mostly along the lines of proving something like a very boring formula, like say, proving that 3^n - 1 is a multiple of 2. After solving hundreds of those, you’re just like, “yeah, where do I ever get to use this?” In fact, I remember our teacher back in the day giving us a very flaky answer to the same question, something about us finding that out when we grow up and study higher mathematics.

Ever since then, my interest in mathematics has been rekindled, although I’m far from being good at it. I have come to terms with it in my own way. I’m not going to be the guy who can calculate an answer to some problem in the blink of an eye and write up a proof in another. I definitely can’t and won’t be the guy who always tops the mathematics exam. But what I can do is, I can try to learn it enough to understand and reason about problems that I face in my daily work. Being able to prove that my algorithm runs in O(N) time, even if I arrive at the proof while bumbling along the way and stumbling in the dark, that’s always an asset and never a burden. Just knowing that the only barrier between mathematics and me is just me, not a mark sheet on public display or my parents’ dignity helps a lot. As long as I’m improving, it’s good news, I’ve already accepted long ago that I wouldn’t become the next Euler, so what does a Joe have to lose by trying anyway?

Over the last two years, I’ve started to study bits and parts of it again. Mooculus has helped me with Calculus a lot, Linear Algebra Done Right by Sheldon Axler has helped me with Linear Algebra. I have my eyes set on Algebra: Chapter 0 next, since I’m learning Haskell seriously, so a bit of Algebra and Category theory could help out in the long run.

The point I’m trying to make through all of that backstory is that Mathematics is important, especially if you’re a Joe programmer like me, yet we all tend to run away from it. Every time I understand the mathematical concept behind a problem or even language syntax in Haskell’s case, I shed a little bit of my Joeness. In competitive programming, you’ll often see that the most successful coders are the ones who have a firm mathematical foundation on a set of mathematical topics on which the problems are based on; induction, combinatorics, number theory, geometry and so on.

Joes love to hide behind the excuse that very little mathematics actually gets used by a programmer in a working environment. I can accuse other Joes of that because I am guilty of the same. I have never had to delve into any complicated mathematics for any client’s work. And truth be told, there is some truth to that excuse. It’s true, an average programmer doesn’t need too much mathematics in everyday tasks. Very few products and applications have such requirements, and even then there’s usually a library created by someone nice on Github which one can just import and use. If not that, we can of course just tap our feet till someone else figures it out for us in the team.

But we are programmers, part of our job does involve solving problems. By ignoring mathematics, we ignore a whole set of problems and sit on top of another set of problems that we have solved over and over again. Where’s the fun in that? More importantly, why purposefully limit ourselves? We are ultimately a product of Computer Science, and that involves mathematics. To intentionally ignore the very foundation of this field is like making a house in an earthquake-prone zone, without the necessary groundwork structure to make sure that the house will stand on the fateful day.

And why am I yapping so much about mathematics today? Because I had another mathematical enlightenment, or something.

Algebras and Haskell

One of the brilliant reasons I love the chapter on Monoids in the book is because it starts out not by introducing a monoid directly but by introducing algebra. What exactly is an algebra? If like me, you’re a student of the Indian high school system, you ran into algebra at around 6th standard. And rarely throughout your years as a student has any teacher decided to drill into you what exactly “algebra” is.

For a lot of us, algebra has been that topic in mathematics where you basically find the value of some variable in some expression. Maybe it all happened because we were considered kids back then, so instead of a formal definition, the teachers decided to go by example. And going further ahead, everyone just forgot to define what exactly algebra is, and we passed high school never knowing what algebra is. If you weren’t the genius bunch in class, you probably, like me, never bothered much about it anyway.

So, back to the chapter, it starts out by defining “algebra”.

Algebra is the study of mathematical symbols and the rules governing their manipulation.

It also mentions that it differentiates from arithmetic in its use of variables. The above definition states that algebra studies symbols and their rules, hence, the values aren’t of much concern to us, so they are abstracted away through the use of variables. This is what reconciles what we learned about algebra back in high school with what it actually is.

Now, when we refer to “an algebra”, what we mean is, there’s a bunch of operations and there’s a set on which these operations can operate over. This will make more sense when we discuss the Haskell implementation next.

In Haskell, the Typeclass system allows us to represent these algebras. Each algebra can be implemented as a typeclass, the functions in that typeclass constitutes the operations of that algebra. So, we have the operations of our algebra, we just need the set now over which these operations will operate.

The set is formed by the types that create an instance of that typeclass. Remember how types instantiate a typeclass to be able to use the functions provided by that typeclass? From the viewpoint of algebra, we create the set over which the operations of that algebra can operate over when a type derives from a typeclass. We’ll explore this with the Monoid.

Monoid

Wikipedia and the book define a monoid as an algebraic structure with a single associative binary operation and an identity element.

Let’s break that definition down, as done in the book. Firstly, a monoid is an algebra. So it has its own set of operations. To think in terms of Haskell, imagine having a typeclass which has a few operations in it. We don’t have to worry about the operations at this moment.

class Monoid' m where
    ...
    ...

That’s what we know from the first part of the definition.

The next part of the definition says that a monoid has a single associative binary operation.

Single. Associative. Binary. Operation.

So, the monoid algebra has one operation that takes two arguments (binary). Also, that operation has to be associative. Being associative means the result of performing this operation must be the same regardless of how the arguments are grouped in an expression.

For example, addition and multiplication are associative.

 1 + (1 + 2) == (1 + 1) + 2
 1 * (1 * 2) == (1 * 1) * 2
 

With this in mind, we can extend our Haskell implementation of monoid as follows:

class Monoid' m where
    binaryOperation :: m -> m -> m
    ...
    ...

We cannot code in the associativity part of the definition because we’re only writing the type signatures for now. Each data type will have different means of being associative, so we leave the implementation of that to the type that will derive from this Monoid' typeclass.

The last part of the definition says that it has an identity element. This means that there will be some value in the set (over which our operations from the Monoid will be operating on) which when combined with another value, will always give us the other value.

For the addition operation, 0 is the identity. For multiplication, it’s 1. Similarly, there will be some identity value in the set.

With that bit, we can complete our Monoid' typeclass:

class Monoid' m where
    identityElem :: m
    binaryOperation :: m -> m -> m

Again, we only set the type signature here. The actual identity value will be different for different types that will derive this class. For numbers under addition, it’s 0. For lists, it’s the empty list []. For Maybe values, it’s Nothing.

The important part here is that we have arrived at an algebra implementation in Haskell from a single-line definition. Think of the typeclass as the algebra, its functions as the operations of that algebra, and the types that derive from this typeclass as the set of values over which the operations of that algebra can operate on.

The actual Monoid typeclass is implemented something like this:

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mempty

mempty is the identity element. mappend is the binary associative operation. mconcat is a bonus function that comes with a default implementation. It basically reduces a list of monoidal values by applying the mappend operation.

An example Monoid instance: Lists

For an example of deriving from Monoid, let’s take a look at how lists are monoids. Now, according to our definition and typeclass of a monoid, we first need a binary operation that’s associative. In the case of lists, we have one such function in ++.

[1, 2 , 3] ++ [4, 5, 6] -- [1, 2, 3, 4, 5, 6]
([1, 2 , 3] ++ [4]) ++ [5, 6] -- [1, 2, 3, 4, 5, 6]
[1, 2, 3] ++ ([4] ++ [5, 6]) -- [1, 2, 3, 4, 5, 6]

For our identity value for lists, we have the empty list []. If we combine a list with any empty list using ++, we get the list back.

[1, 2, 3] ++ [] -- [1, 2, 3]

So, to derive our Monoid instance for lists, we can write:

instance Monoid [a] where
    mempty = []
    mappend = ++

That’s kind of how lists are actually monoids in Haskell. For other types, we have to similarly define the identity value and binary operation.

Monoid Laws

Monoids have a few laws that they adhere to. There are a lot of reasons as to why laws are important if you’re wondering about their need. But let’s just go with the algebra theme for now: Algebras are defined by their laws. Quite literally. Remember the definition of the Monoid? It’s defined in terms of the laws it obeys, associativity and identity.

Here are the laws that Monoids follow.

  • Left Identity
mappend mempty x = x

The identity value as the left/first argument of the binary operation combined with any other value should return that other value.

  • Right Identity
mappend x mempty = x

The identity value as the right/second argument of the binary operation combined with any other value should return that other value.

  • Associativity
mappend x (mappend y z) = mappend (mappend x y) z

The order of grouping up the binary operations shouldn’t matter and return the same result regardless of how the arguments are grouped up.

The importance of laws isn’t always obvious. We’ve seen these laws such as associativity, commutativity, identity and so on in our mathematics textbook for a long time, without any practical use.

So why pay any attention to Monoidal laws? The reason is that these laws help us to properly reason about our monoids. Say, we derived our own instance of the Monoid typeclass. How will we know that our derived instance is actually a Monoid? It’s the laws! By checking if the three laws hold for our derived type, we are guaranteed that our type is a monoid and we can compose accordingly. If it passes all the laws, it is a valid monoid and won’t misbehave in some weird way while you’re trying to combine values in some way.

One important note here is that typeclasses don’t enforce these laws on the derived instances. It’s the programmer’s duty to make sure that any derived instance follows these monoidal laws. It’s possible to derive an instance and not follow the laws, so one should be careful and always check for validity through the laws.

Monoid Uses

I haven’t used Monoids enough to be talking about its uses but if I don’t write about it here, I would have committed the same sin as my high school teachers of teaching a mathematical concept but never being able to relate it or translate it to something in the real world.

One very sensible example that the book gives is of parallel computation. Say, you’re writing a library that does some calculations in parallel and combines the result in some way. We can visualize this as a tree, with each leaf being a separate computation. When the computations are over on each leaf, a pair-wise operation is performed on the results.

But this creates a problem, what if we have an odd number of leaves? The pair-wise operation would need to even out an odd number of leaves but it takes only two arguments at a time.

Monoids to the rescue! If we simply provide an mempty value or an identity value to the odd leaves, we easily solve this problem as the result of that operation is the value from the odd leaf. This way we even out the odd count of the leaves.

This also shows why the monoid laws are important. The laws guarantee that if we have a monoidal value, combining it with the mempty or identity value will always return that same value. This reassurance is what lets us reason about this solution. And that is why laws are important. It also further shows that mathematics does show up in programming in real life and is always a great asset to have.

Another use of monoids I’ve found in the wild is the Context monoid, which is used quite a lot in the Hakyll. I’ve seen a few Hakyll configurations which use the <> function in them. The <> function is the infix version of the mappend function, defined in Data.Monoid in Haskell.

Conclusion

Mathematics is important. It’s okay to hate it if you’re not good at it, but if you’re a working programmer, knowing it just for the sake of your own profession will pay huge benefits in the longer run. Out there, very rarely do we have to show our mathematical prowess to the world. Once the peer-pressure that comes with mathematics since our childhood is separated from it, and we start seeing its uses and appearances in the real world, amidst our own work, it makes the whole thing much easier, even for someone who’s as bad as me in it.

Mathematics is so tightly wound into Computer Science that ignoring it as a programmer is like working with a severe self-imposed limitation. Solving problems is a huge part of this industry, and mathematics helps us in doing just that. We shouldn’t ignore one of the biggest tools of problem-solving just because we were made to believe that we aren’t good at it. From my recent experience of self-learning a bit, I think I can say that the biggest barrier to learning and utilizing it isn’t our lack of technical and mathematical ability, but it’s the emotional barrier of telling ourselves that we are no good at it. Just remember that the goal is to use mathematics to solve some of the problems we face, not to become the next Euler.

On Monoids, they are very simple. But their simplicity has helped me appreciate the relation between mathematics and programming. The process laid out in the book on how to go from its definition to its code implementation and how laws give us the reassurance to reason about solutions has really put things in a different perspective for me. A few years ago, I held the belief that I would never get to see any use of the identity laws or associativity laws. But, here I am now, learning about monoids, and seeing examples of those same laws being used to write programs.

For my next few days, I’ll be studying Functors, Applicatives and Monads respectively. I haven’t checked the content of the book yet but I’m guessing it might be building up from monoids into functors into applicatives and so on. Either way, we are approaching the Monad landmark! I’m very excited about studying the upcoming topics.

Hope everyone’s having a great time with their #100DaysOfCode. Cheers and good luck!

comments powered by Disqus