Monoids

Recall that a typeclass is something that multiple types have in common. Any time we see a pattern, something that seems to be recurring in code, there’s a good chance we’re going to be able to find a typeclass. We’ll find some things that types have in common with each other.

In this course already we’ve seen all six of these concepts:

Hopefully when we look at this list, the pattern we’re talking about ought to jump right out. Not only do all of these functions have two arguments – additionally, the two arguments have the same type, which is also the same as the return type. When we add or multiply two numbers, we get another number. When we concatenate two lists, we get another list. When we compose two a -> a functions, we get another a -> a function.

One way this pattern emerges in our code is that when we use functions of this particular sort, we often end up chaining them together.

We’ll narrow the set of examples from six to three for brevity’s sake: addition, multiplication, concatenation.

What if we told you that when you write expressions like these, you don’t have to specify what operation you’re using, but rather it could be inferred from the types of the parameters?

Wherever +, *, or ++ appeared in the previous example, they now have all been replaced by this blank-looking <> operator, which some describe as having a sort of diamond shape.

What we’re talking about here is the Semigroup class. The three types that belong to this class we’re demonstrating here are sums, products, and lists. This class has exactly one operation, <>, often referred to as “the semigroup operator”, or sometimes “mappend” (the “m” standing for another concept that we’ll get to shortly).

List, of course, is the type we’ve seen before, and its semigroup operation is concatenation. Sum and Product are new to us, and this newtype keyword is new here as well. The Sum and Product types exist to get around a peculiar little problem with our desire to replace all of the operators with this mysterious semigroup operator. Say we have two integers, 3 and 4. What do we get when we semigroupally combine them?

Do we add them to get 7, or do we multiply them to get 12? Both seem like perfectly sensible answers. And so in circumstances where we want to use the semigroup operator, we need to use not Integer directly, but types like Sum Integer and Product Integer. Sums of integers semigroupally combine with addition, and Products of integers semigroupally combine with multiplication.

We don’t need to go into a discussion of the subtle distinction between data and newtype here. If you read newtype as data, you’ll get the gist. The Sum type has a single constructor, called Sum, and all it really does is wrap up that a value, whatever type a may be, in the Sum type – for example, Integer becomes Sum Integer. It doesn’t add any structure or change what the data is at all, but what it does is exactly what it says: it creates a new type. And once we have a new type, we can define the new type’s membership in the Semigroup class differently – one for addition, and one for multiplication.

We still haven’t done anything interesting yet; all we’ve done is change our + and * symbols to <>, which is not really a useful accomplishment. But here’s something we might want to do with types that follow this semigroup pattern. Suppose we wanted to write a polymorphic function that behaved like this:

This function will take a list of things of some semigroup-having type, and smash all the things in the things in the list together. If it is a list of sums, we will add all the numbers together. If it is a list of strings, we will concatenate them all into one long string.

This seems like something we could do with one of the folding functions we talked about in the previous lesson. There’s one little catch, though, and we always have to thing about all the little catches if we want to write total functions: what would such a function do when the input list is empty?

If the way we combined a list of Sums was to add all of the numbers together, how can we do that if there are no numbers to add?

Recall that we have the concept of an identity value: a value which, if it appears in the list, doesn’t change the result. For example, 0 is the identity for addition, because inserting or removing zeroes doesn’t change the result.

Since removing zeroes from the list shouldn’t change the sum, then the sum of [0] should be the same as the sum of [] – it should be zero. In other words, when we “combine all the items in an empty list”, what we get should be the identity value.

When we fold an empty list of products, we get a product of 1 – because multiplying a number by 1 has no effect. When we concatenate a list of strings together, but there are no strings in the list, we get the empty string.

In answering this question, we have come across another typeclass – another important thing that many types have in common. Sums, products, and lists, all have an identity value. There’s a class for that.

When a type has a semigroup operator and also a corresponding identity value, we call that type a monoid. The Sum, Product, and [] types all belong to the Monoid class. A monoid must have two things: the (<>) function, and an identity value, which we call mempty.

• (<>) :: a -> a -> a
• mempty :: a

So when we think about what it means to take a list of things and smash them all together, we should think of it like this:

For the empty list, what we get is the mempty value. If we have a single element, then in addition to the mempty starting value, we append that element, in whatever way that type enjoys being appended – addition, multiplication, concatenation, etc. The more items we have in the list, the more we can just keep chaining that <> operator over and over.

What we have been discussing is the function known as fold.

It converts a list of a into a single a, with the constraint that a must belong to the Monoid class.

When you want to collapse a list into a single value, it is not always the case that you will want to combine using the element type’s monoid. But when you do, the fold function is nicely concise and convenient.

The type of fold is slightly different than the simplified version we gave above.API documentation for Data.Foldable If you query the type in GHCi, this is what you will see:

λ> import Data.Foldable

λ> :type fold
fold :: (Foldable t, Monoid m) => t m -> m

The actual type of fold does not have list as its parameter; rather, it has a generic t as its parameter type, with a Foldable constraint on the t. That t can be [], but it can also be other types of things, not only lists.

We will give a short demonstration to begin exploring the expanded possibilities that this Foldable polymorphism offers.

We have defined two values of type Maybe String. The first is nothing, and the second is just Alonzo.

What we are to demonstrate here is that, in the sense of being Foldable, Nothing behaves like the empty list, and Just something behaves like a list with one element in it. In fact, we can see that very plainly because there is also a function called toList that converts a value of some Foldable type to its list equivalent.

λ> toList example1
[]

λ> toList example2
["Alonzo"]

So if we fold example 1, then what we get is the same as if we were to fold an empty list of strings.

λ> fold example1
""

And if we fold example 2, then we get the same result as if we folded a list containing only Alonzo.

λ> fold example2
"Alonzo"

The type of fold is interesting because it is the pinnacle of polymorphism – there is not a single specific in this type signature. Haskell, and in particular the base library, is full of functions like these. When you run across one for the first time, it can often seem impossibly abstract and meaningless.

The key to understanding a type signature like this is to understand its constraints. We need to have a sense of what it means for something to be foldable, and what it means for something to be a monoid.

One really good way to go about that is to keep these examples in mind. Think of things like [] and Maybe as your paradigmatic Foldables, and things like Sum, Product, and [] as your prototypical Monoids. Think of folding as taking a list of numbers and adding or multiplying them together, or taking a list of strings as concatenating them all together into a single string.

And as you go through your life in Haskell and encounter new types of Foldable and new types of Monoid, they can always be likened back to those first examples. A class is something that different types share. Always have at hand several examples of types that belong to each class, and be contemplating what it is that the members of a class have in common.