# Endomorphism monoid by Mark Seemann

*A method that returns the same type of output as its input forms a monoid. 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*). Methods that return the same type of value as their input form monoids over composition. The formal term for such an operation is an endomorphism.

### Scheduling example #

Imagine that you have to develop some functionality for scheduling events in the future. As a concrete example, I recently wrote about adjusting dates while taking bank holidays into account. For instance, if you want to find the latest bank day *before* a given date, you could call the `AdjustToLatestPrecedingDutchBankDay`

method. If you give it a normal bank day (say, a Thursday), it'll simply return the input date, but if you give it a Sunday, it'll return the preceding Friday. That is, unless that particular Friday is a bank holiday, in which case it'll return the Thursday before - as long as that's not also a bank holiday, and so on.

In that previous article, the `AdjustToLatestPrecedingDutchBankDay`

method is an extension method, but you can also model it as an instance method, like this:

public DateTimeOffset Adjust(DateTimeOffset value) { var candidate = value; while (!(IsDutchBankDay(candidate.DateTime))) candidate = candidate.AddDays(-1); return candidate; }

This method would be part of a class that implements an interface:

public interface IDateTimeOffsetAdjustment { DateTimeOffset Adjust(DateTimeOffset value); }

You can make other implementations of this interface. Here's one that adjusts a date and time to business hours:

public class BusinessHoursAdjustment : IDateTimeOffsetAdjustment { private readonly static TimeSpan startOfBussiness = TimeSpan.FromHours(9); private readonly static TimeSpan endOfBusiness = TimeSpan.FromHours(17); public DateTimeOffset Adjust(DateTimeOffset value) { // Warning: May not handle DST changes appropriately! // It's only example code... if (value.TimeOfDay < startOfBussiness) return value - value.TimeOfDay + startOfBussiness; if (endOfBusiness < value.TimeOfDay) return (value - value.TimeOfDay + startOfBussiness).AddDays(1); return value; } }

To keep the example simple, business hours are hard-coded to 9-17.

You could also adapt conversion to UTC:

public class UtcAdjustment : IDateTimeOffsetAdjustment { public DateTimeOffset Adjust(DateTimeOffset value) { return value.ToUniversalTime(); } }

Or add a month:

public class NextMonthAdjustment : IDateTimeOffsetAdjustment { public DateTimeOffset Adjust(DateTimeOffset value) { return value.AddMonths(1); } }

Notice that the `Adjust`

method returns a value of the same type as its input. So far when discussing monoids, we've been looking at binary operations, but `Adjust`

is a *unary* operation.

An operation that returns the same type as its input is called an *endomorphism*. Those form monoids.

### Composing adjustments #

It's easy to connect two adjustments. Perhaps, for example, you'd like to first use `BusinessHoursAdjustment`

, followed by the bank day adjustment. This will adjust an original input date and time to a date and time that falls on a bank day, within business hours.

You can do this in a general-purpose, reusable way:

public static IDateTimeOffsetAdjustment Append( this IDateTimeOffsetAdjustment x, IDateTimeOffsetAdjustment y) { return new AppendedAdjustment(x, y); } private class AppendedAdjustment : IDateTimeOffsetAdjustment { private readonly IDateTimeOffsetAdjustment x; private readonly IDateTimeOffsetAdjustment y; public AppendedAdjustment( IDateTimeOffsetAdjustment x, IDateTimeOffsetAdjustment y) { this.x = x; this.y = y; } public DateTimeOffset Adjust(DateTimeOffset value) { return y.Adjust(x.Adjust(value)); } }

The `Append`

method takes two `IDateTimeOffsetAdjustment`

values and combines them by wrapping them in a private implementation of `IDateTimeOffsetAdjustment`

. When `AppendedAdjustment.Adjust`

is called, it first calls `Adjust`

on `x`

, and then calls `Adjust`

on `y`

with the return value from the first call.

In order to keep the example simple, I omitted null guards, but apart from that, `Append`

should work with any two implementations of `IDateTimeOffsetAdjustment`

. In other words, it obeys the Liskov Substitution Principle.

### Associativity #

The `Append`

method is a binary operation. It takes two `IDateTimeOffsetAdjustment`

values and returns an `IDateTimeOffsetAdjustment`

. It's also associative, as a test like this demonstrates:

private void AppendIsAssociative( IDateTimeOffsetAdjustment x, IDateTimeOffsetAdjustment y, IDateTimeOffsetAdjustment z) { Assert.Equal( x.Append(y).Append(z), x.Append(y.Append(z))); }

As usual in this article series, such a test doesn't *prove* that `Append`

is associative for all values of `IDateTimeOffsetAdjustment`

, but if you run it as a property-based test, it demonstrates that it's quite likely.

### Identity #

In true monoidal fashion, `IDateTimeOffsetAdjustment`

also has an identity element:

public class IdentityDateTimeOffsetAdjustment : IDateTimeOffsetAdjustment { public DateTimeOffset Adjust(DateTimeOffset value) { return value; } }

This implementation simply returns the input value without modifying it. That's a neutral operation, as a test like this demonstrates:

private void AppendHasIdentity(IDateTimeOffsetAdjustment x) { Assert.Equal( x.Append(new IdentityDateTimeOffsetAdjustment()), x); Assert.Equal( new IdentityDateTimeOffsetAdjustment().Append(x), x); }

These two assertions verify that left and right identity holds.

Since `Append`

is associative and has identity, it's a monoid.

This holds generally for any method (or function) that returns the same type as it takes as input, i.e. `T SomeOperation(T x)`

. This matches the built-in library in Haskell, where `Endo`

is a `Monoid`

.

### Conclusion #

A method that returns a value of the same type as its (singular) input argument is called an endomorphism. You can compose two such unary operations together in order to get a composed operation. You simply take the output of the first method and use it as the input argument for the second method. That composition is a monoid. Endomorphisms form monoids.

**Next:** Maybe monoids.

## Comments

Hi, Mark!

I'm really enjoing your series on category theory. I think you're doing a great job in making such abstract concepts accessible to us programmers. However, I found this particular episode puzzling. You claim that any composition of endomorphisms is a monoid, and you also claim to have tested that your

`Append`

method is associative. However, it is not hard to come up with a counter-example:Here,

`WeekendAdjustment`

is just a simplified`DutchBankDayAdjustment`

.It would also be interesting to see how you can do property based testing on this, i.e. how to automatically generate meaningful instances of

`IDateTimeOffsetAdjustment`

. When I try to run your test, I get: "IDateTimeOffsetAdjustment is not handled automatically by FsCheck. Consider using another type or writing and registering a generator for it."Tor, thank you for writing, and for your kind words. I suppose that the

`CounterExample`

test fails when one executes it; you don't explicitly write that, but that's what I expect would happen.The

`Append`

operation is, indeed, not commutative. This is, however, not a requirement for monoids, or even for groups. Some monoids, such as addition and multiplication, are also commutative, while others, like list concatenation or, here, the endomorphism monoid, aren't.When it comes to the FsCheck properties, I admit that I cheated slightly with the code listing in the article. I did this because the properties are a bit more complicated than what I show, and I was concerned that the extra infrastructure surrounding those tests would detract from the overall message.

The associativity property in its entirety looks like this:

Where

`GenerateAdjustment`

is defined like this:Not only did I omit all that extra scaffolding, I also pretended that

`IDateTimeOffsetAdjustment`

objects could be compared using their default implementations of`Equals`

, which they meaningfully can't. Notice that the full property listed here also asserts using a custom equality comparer:The custom comparer's

`Equals`

method creates a random number of ticks and uses it to create a`DateTimeOffset`

value. It then calls`Adjust`

on both objects, which are considered equal if they produce the same result.The test for identity is defined in a similar fashion; it also uses

`GenerateAdjustment`

and`DateTimeOffsetAdjustmentComparer`

.Thank you for such a prompt and thorough reply. You are of course correct, I have been confusing associativity with commutativity. I didn't run into the same mistake during the list concatenation article, though, maybe because list concatenation more obviously is associative and not commutative. In the current article, however, I intuitively felt that the operations needed to be commutative, but your reply clears that up.

It is also helpful to see the extra scaffolding around your property based test. The article itself seemed to imply that instances of

`IDateTimeOffsetAdjustment`

could be automatically generated. Your approach to set up such a test will come in handy now that I'm convinced that I should let more of my tests be property based, even in C#!Tor, I made the same mistake several times when I started researching all of this. I think that there's something intuitive and fundamental about commutativity, so at a superficial glance, it seems odd that we can do without it, while at the same time requiring a less intuitive property like associativity.

When it comes to computation, though, I think that it's exactly the nature of associativity that enables us to decompose big problems into several small problems. The order of how you deal with those small problems doesn't matter, as long as you apply the intermediate results in the correct order.

Dear Mark!

These additional explanations and contextual information in the comment sections deserve a place in the original text. To keep the text uncluttered this site uses clickable popups: . If you click on some of the numbers, you'll see what I mean. You might consider adding this feature to the text.

Best regards, Norbert.

Dear Mark,

Although late to the game I really enjoy and appreciate your series here explaining monoids. Your examples are quite helful in getting to a deeper understanding.

This one however have me puzzled.

As I see it, it's fairly easy to produce a counterexample to your claim (if I understand it correctly) that composition of functions with similar domain and codomain forms a monoid. To make it simple I'll use the domain of integers and define a function f(x) = x + 1 and g(x) = x * 6. They both return the same type as they take as input and yet, the composition is clearly not associative.

The possible explanation I've been able to dig out, is if we assume the set of functions we talk about and the composition operator forms a category. However in this case, it's part of the definition of a category that an identity element exist and composition is associative. But then the claim seems circular.

Am I missing anything here?

Michael, thank you for writing. Can you share a counterexample?

I've tried some casual examples with your

`f`

and`g`

functions, but associativity seems to hold:Casual experiments with

`f . f . g`

also indicates associativity.I've also tried with QuickCheck:

The composition

`f . g . f`

doesn't seem to easily produce any counterexamples. I haven't, however, tried all possible permutations of`f`

and`g`

, so that's no proof.If I recall correctly, however, associativity of endomorphisms is a property that one

canprove with equational reasoning, so I'd be surprised if a counterexample exists.Mark, thanks for a quick and quite elaborate reply.

I'm slightly embarrased. First of all, my example attempting to disprove associativity should of course contain 3 functions, not 2 as I did. And second of all I could have / should have done exactly what you did and coded up an example - and then seen the error of my assumptions without taking your time. I apologise for the inconvenience. Lesson learned!

I do appreciate your answer - and clearly I was wrong.

Something still bothers my intuition around this. I trust your statement that it actually can be proven, so clearly my intuition have got it wrong. I'll continue to work on understanding this "associativity of endomorphisms", so I can develop a stronger intuition around monoids as well as associativity.

Thank you for your help :)

Michael, being wrong is rarely a pleasant experience, but it might be a symptom that you're learning. Admitting one's mistake in public is, I believe, a sign of maturity and personal integrity. Thank you for doing that.

I don't know if I can help your intuition along, but the proof isn't that hard. I originally learned

equational reasoningfrom this article by Bartosz Milewski, so I'm using that notation. The goal is to prove that:for any three (pure) functions

`f`

,`g`

, and`h`

, where the binary operation is question is the composition operator`(.)`

given as:This is Haskell syntax, where a function call is simply written as

`f x`

or`g x`

, meaning that you call the function`f`

or`g`

with the value`x`

. Brackets in Haskell work the same way as brackets in F#, which again work like in mathematics. Thus,`(f . g) x`

means'the composed function.`(f . g)`

called with the argument`x`

'The proof might go like this:

Writing out a proof like this isn't something I do every day, so I may have made a mistake or two. Also, I can't shake the feeling that a

simplerproof is available, but on the other hand, I found it a good exercise.Mark, thank you for the kind words!

And thank you for taking the time to write down a proof. Yes, the proof is indeed helpful. Seeing it made it clear that all function composition is associative. I think your comment about this being about pure functions (which really is quite obvious) also helped. It triggered one of the original insights that has moved me towards functional programming, which is Referential Transparency. Suddenly it was blinding obvious that functional composition of pure functions really is just term substitution - so of course it's associative.

It feels good to have my intuition up to speed :)

This has been quite a fun and valuable exchange. Thank you for taking your time. I've learned something new and that's always a source of joy.

Onwards and upwards!