# Tuple monoids by Mark Seemann

*Tuples of monoids form monoids. Data objects of monoids also form monoids. An article for object-oriented programmers.*

This article is part of a series about monoids. In short, a *monoid* is an associative binary operation with a neutral element (also known as *identity*). This article starts off with some easy-to-understand, but abstract results. Once these are established, however, you'll see how to use them in a relatable example, so keep reading!

**Tuples**

A tuple is a group of elements. In statically typed programming languages, each element has a type, and the types don't have to be the same. As an example, in C#, you can create a tuple like this:

Tuple<int, string> pair = Tuple.Create(42, "Foo");

This creates a tuple where the first element must be an `int`

and the second element a `string`

. In the example, I've explicitly declared the type instead of using the `var`

keyword, but this is only to make the type clearer (since you don't have an IDE in which to read the code).

The `pair`

tuple is a two-tuple, which means that it must have exactly two elements, of the types given, but you can also create larger tuples:

Tuple<string, bool, int> triple = Tuple.Create("Bar", false, 42);

This is a three-tuple, but conceptually, tuples can have any size.

**Pairs of monoids**

A *pair* (a two-tuple) forms a monoid if both elements form a monoid. Haskell formalises this by stating:

`instance (Monoid a, Monoid b) => Monoid (a, b)`

The way to read this is that for any monoid `a`

and any monoid `b`

, the pair `(a, b)`

is also a monoid.

Perhaps this is easiest to understand with a C# example. Consider a tuple of the type `Tuple<int, string>`

. Integers form monoids under both addition and multiplication, and strings are monoids under concatenation. Thus, you can make `Tuple<int, string>`

form a monoid as well. For instance, use the multiplication monoid to define this binary operation:

public static Tuple<int, string> CombinePair( Tuple<int, string> x, Tuple<int, string> y) { return Tuple.Create(x.Item1 * y.Item1, x.Item2 + y.Item2); }

For this particular example, I've chosen multiplication as the binary operation for `int`

, and the string concatenation operator `+`

for `string`

. The point is that since both elements are monoids, you can use their respective binary operations to return a new tuple with the combined values.

This operation is associative, as the following FsCheck property demonstrates:

[Property(QuietOnSuccess = true)] public void CombinePairIsAssociative( Tuple<int, string> x, Tuple<int, string> y, Tuple<int, string> z) { Assert.Equal( CombinePair(CombinePair(x, y), z), CombinePair(x, CombinePair(y, z))); }

This property passes for all the `x`

, `y`

, and `z`

values that FsCheck generates.

The `CombinePair`

operation has identity as well:

public static Tuple<int, string> PairIdentity = Tuple.Create(1, "");

Again, you can use the identity value for each of the elements in the tuple: `1`

for the multiplication monoid, and `""`

for string concatenation.

This value behaves as the identity for `CombinePair`

, at least for all non-null string values:

[Property(QuietOnSuccess = true)] public void CombinePairHasIdentity(Tuple<int, NonNull<string>> seed) { var x = Tuple.Create(seed.Item1, seed.Item2.Get); Assert.Equal(CombinePair(PairIdentity, x), CombinePair(x, PairIdentity)); Assert.Equal(x, CombinePair(x, PairIdentity)); }

Again, this test passes for all `seed`

values generated by FsCheck.

The C# code here is only an example, but I hope it's clear how the result generalises.

**Triples of monoids**

In the above section, you saw how pairs of monoids form a monoid. Not surprisingly, triples of monoids also form monoids. Here's another C# example:

public static Tuple<string, bool, int> CombineTriple( Tuple<string, bool, int> x, Tuple<string, bool, int> y) { return Tuple.Create( x.Item1 + y.Item1, x.Item2 || y.Item2, x.Item3 * y.Item3); }

The `CombineTriple`

method is another binary operation. This time it combines two triples to a single triple. Since both `string`

, `bool`

, and `int`

form monoids, it's possible to combine each element in the two tuples to create a new tuple. There's more than one monoid for integers, and the same goes for Boolean values, but here I've chosen multiplication and Boolean *or*, so the identity is this:

public static Tuple<string, bool, int> TripleIdentity = Tuple.Create("", false, 1);

This triple simply contains the identities for string concatenation, Boolean *or*, and multiplication. The operation is associative, but I'm not going to show this with a property-based test. Both tests for associativity and identity are similar to the above tests; you could consider writing them as an exercise, if you'd like.

This triple example only demonstrates a particular triple, but you can find the generalisation in Haskell:

instance (Monoid a, Monoid b, Monoid c) => Monoid (a, b, c)

This simply states that for monoids `a`

, `b`

, and `c`

, the tuple `(a, b, c)`

is also a monoid.

**Generalisation**

At this point, it can hardly come as a surprise that quadruples and pentuples of monoids are also monoids. From Haskell:

instance (Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a, b, c, d) instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) => Monoid (a, b, c, d, e)

The Haskell standard library stops at pentuples (five-tuples), because it has to stop somewhere, but I'm sure you can see how this is a general rule.

**Data objects as monoids**

If you're an object-oriented programmer, you probably don't use tuples much in your day-to-day work. I'd even suggest that you shouldn't, because tuples carry too little information to make good domain objects. For example, if you have `Tuple<int, string, string>`

, what do the elements mean? A better design would be to introduce a small Value Object called `Customer`

, with `Id`

, `FirstName`

, and `LastName`

properties.

(In functional programming, you frequently use tuples, because they're useful for 'gluing' generic functions together. A Haskell programmer may instead say that they are useful for composing parametrically polymorphic functions, but the meaning would be the same.)

As on object-oriented developer, then why should you care that tuples of monoids are monoids?

The reason this is interesting in object-oriented programming is that there's a strong relationship between tuples and data objects (Value Objects or Data Transfer Objects). Consider the `Customer`

examples that I sketched out a few paragraphs above. As you'll learn in a future article, you can refactor a tuple to a class, or a class to a tuple.

**Example: Roster**

In Denmark, where I live, learning to swim is a mandatory part of the school curriculum. Teachers take the children to the nearby swimming stadium and teach them to swim. Since this is an activity outside of school, teachers would be prudent to keep a roster of the children. Modelled as a class, it might look like this:

public class Roster { public int Girls { get; } public int Boys { get; } public IReadOnlyCollection<string> Exemptions { get; } public Roster(int girls, int boys, params string[] exemptions) { Girls = girls; Boys = boys; Exemptions = exemptions; } // ... }

Some children may be temporarily exempt from a swimming lesson, perhaps because of a passing medical condition. This changes from lesson to lesson, so the roster keeps track of them separately. Additionally, the boys will need to go in the men's changing rooms, and the girls in the women's changing rooms. This is the reason the roster keeps track of the number of boys and girls separately.

This, however, presents a logistical problem, because there's only one teacher for a class. The children are small, so need the company of an adult.

The way my children's school solved that problem was to combine two groups of children (in Danish, *en klasse*, a class), each with their own teacher - one female, and one male.

To model that, the `Roster`

class should have a `Combine`

method:

public Roster Combine(Roster other) { return new Roster( this.Girls + other.Girls, this.Boys + other.Boys, this.Exemptions.Concat(other.Exemptions).ToArray()); }

Clearly, this is easy to implement. Just add the number of girls together, add the number of boys together, and concatenate the two lists of exemptions.

Here's an example of using the method:

[Fact] public void UsageExample() { var x = new Roster(11, 10, "Susan", "George"); var y = new Roster(12, 9, "Edward"); var roster = x.Combine(y); var expected = new Roster(23, 19, "Susan", "George", "Edward"); Assert.Equal(expected, roster); }

The `Combine`

method is an instance method on the `Roster`

class, taking a second `Roster`

as input, and returning a new `Roster`

value. It's a binary operation. Does it also have identity?

Yes, it does:

public static readonly Roster Identity = new Roster(0, 0);

Notice that the `exemptions`

constructor argument is a `params`

array, so omitting it means passing an empty array as the third argument.

The following properties demonstrate that the `Combine`

operation is both associative and has identity:

[Property(QuietOnSuccess = true)] public void CombineIsAssociative(Roster x, Roster y, Roster z) { Assert.Equal( x.Combine(y).Combine(z), x.Combine(y.Combine(z))); } [Property(QuietOnSuccess = true)] public void CombineHasIdentity(Roster x) { Assert.Equal(x, Roster.Identity.Combine(x)); Assert.Equal(x, x.Combine(Roster.Identity)); }

In other words, `Combine`

is a monoid.

This shouldn't surprise us in the least, since we've already established that tuples of monoids are monoids, and that a data class is more or less 'just' a tuple with named elements. Specifically, the `Roster`

class is a 'tuple' of two addition monoids and the sequence concatenation monoid, so it follows that the `Combine`

method is a monoid as well.

**Roster isomorphism**

In future articles, you'll learn more about isomorphisms between various representations of objects, but in this context, I think it's relevant to show how the `Roster`

example is isomorphic to a tuple. It's trivial, really:

public Tuple<int, int, string[]> ToTriple() { return Tuple.Create(this.Girls, this.Boys, this.Exemptions.ToArray()); } public static Roster FromTriple(Tuple<int, int, string[]> triple) { return new Roster(triple.Item1, triple.Item2, triple.Item3); }

This pair of methods turn a `Roster`

into a triple, and a corresponding triple back into a `Roster`

value. As the following two FsCheck properties demonstrate, these methods form an isomorphism:

[Property(QuietOnSuccess = true)] public void ToTripleRoundTrips(Roster x) { var triple = x.ToTriple(); Assert.Equal(x, Roster.FromTriple(triple)); } [Property(QuietOnSuccess = true)] public void FromTripleRoundTrips(Tuple<int, int, string[]> triple) { var roster = Roster.FromTriple(triple); Assert.Equal(triple, roster.ToTriple()); }

This isn't the only possible isomorphism between triples and `Roster`

objects. You could create another one where the `string[]`

element goes first, instead of last; where boys go before girls; and so on.

**Summary**

Tuples of monoids are also monoids. This holds for tuples of any size, but all of the elements has to be monoids. By isomorphism, this result also applies to data objects.

**Next:** Function monoids.

## Comments

Hi Mark, I have trouble understanding your usage of the term 'monoid' in this post. You apply it to the types string, bool, and int when you say that a tuple of those "monoids" is a monoid as well. But up to this point you made it very clear, that a type is NOT a monoid. A function can be a monoid. So, would it be more correct to say that a tuple of certain functions, which are monoids, is a monoid as well?

Punkislamist, thank you for writing. You're entirely correct that a monoid is an associative binary operation with identity. It's a function, not a type. If this article is unclear, the fault is all mine.

Not surprisingly, this topic is difficult to write about. The text has to be exact in order to avoid confusion, but since I'm only human, I sometimes make mistakes in how I phrase my explanations. While I've tried to favour the phrase that

a type forms a monoid, I can see that I've slipped up once or twice in this article.Some types form more than a single monoid. Boolean values, for instance, form exactly four monoids. Other types, like integers, form an infinite set of monoids, but the most commonly used integer monoids are addition and multiplication. Other types, particularly

unit, only form a single monoid.Why do I talk about types, then? There's at least two reasons. The first is the practical reason that most statically typed languages naturally come with a notion of types embedded. One could argue, I think, that types are a more fundamental concept than functions, since even functions have types (for instance, in Haskell, we'd characterise a binary operation with the type

`a -> a -> a`

).A more abstract reason is that category theory mostly operates with the concepts of

objectsandmorphisms. Such objects aren't objects in the sense of object-oriented programming, but rather correspond to types in programming languages. (Actually, a category theoryobjectis a more fluffy concept than that, but that's the closest analogy that I'm aware of.)In category theory, a particular monoid is an object in the category of monoids. For example, the integer addition monoid is an object in the category of monoids, as is the string concatenation monoid, etcetera.

When you consider a 'raw' programming language type like C#'s

`int`

, you're correct that it's not a monoid. It's just a type. The same goes for Haskell's corresponding`Int32`

type. As primitive values, we could say that the type of 32-bit integers is an object in some category (for example, the category of number representations). Such an object is not a monoid.There exists, however, a morphism (a 'map') from the 32-bit integer object to the addition monoid (which is an object in the category of monoids). In Haskell, this morphism is the data constructor

`Sum`

:What this states is that

`Sum`

is a function (i.e. a morphism) that takes an object`a`

and turns it into an object`Sum a`

. We have to be careful here, because`Sum a`

is a Haskelltype, whereas`Sum`

is the function that 'elevates' an object`a`

to`Sum a`

. The names are similar, but the roles are different. This is a common idiom in Haskell, and have some mnemonic advantages, but may be confusing until you get the hang of it.We can think of

`Sum a`

as equivalent to the category theory objectaddition in the category of monoids. That's also how it works in Haskell:`Sum a`

is a monoid:In Haskell,

`<>`

is the polymorphic binary operation; exactly what it does depends on the object (that is: the type) on which it operates. When applied to two values of`Sum a`

, the result of combining 40 and 2 is 42.To be clear,

`Sum`

isn't the only morphism from the category of number representations to the category of monoids.`Product`

is another:Thus, there

isa relationship between types and monoids, but it's most apparent in programming languages that are geared towards that way of thinking (like Haskell). In C#, it's difficult to translate some of these concepts into code, because C#'s type system isn't up to the task. Instead, when we consider a type like`int`

, I think it's pragmatic to state that the type forms one or more monoids. I've also encountered the phrase thatit gives rise to a monoid.While you can represent a monoid with a C# interface, I've so far tried to avoid doing so, as I'm not sure whether or not it's helpful.

Hi Mark, I did not expect to recieve such an exhaustive answer. That is incredible, thank you so much! It did clear up my confusion as well. Since most of these terms and concepts are new to me, even a slight inconsistency can be really confusing. But with your additional explanation I think I got a good understanding of the terms again.

Your explanations of these concepts in general are very well written and make it easy for people unfamiliar with this topic to understand the terms and their significance. Thanks again for writing!

Punkislamist, thank you for those kind words. I'm happy to hear that what I wrote made sense to you; it makes sense to me, but I forgot to point out that I'm hardly an expert in category theory. Writing out the above answer helped clarify some things for me as well; as is common wisdom: you only really understand a topic when you teach it.