Endomorphism monoid by Mark Seemann

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:

[Fact]
public void CounterExample()
{
    IDateTimeOffsetAdjustment weekend = new WeekendAdjustment();
    IDateTimeOffsetAdjustment nextMonth = new NextMonthAdjustment();

    var a = new AppendedAdjustment(weekend, nextMonth);
    var b = new AppendedAdjustment(nextMonth, weekend);

    var startDate = new DateTimeOffset(2019, 1, 5, 0, 0, 0, TimeSpan.Zero);
    Assert.Equal(a.Adjust(startDate), b.Adjust(startDate));
}

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:

[Property(QuietOnSuccess = true)]
public Property AppendIsAssociative()
{
    return Prop.ForAll(
        GenerateAdjustment().Three().ToArbitrary(),
        t => AppendIsAssociative(t.Item1, t.Item2, t.Item3));
}
 
private void AppendIsAssociative(
    IDateTimeOffsetAdjustment x,
    IDateTimeOffsetAdjustment y,
    IDateTimeOffsetAdjustment z)
{
    Assert.Equal(
        x.Append(y).Append(z),
        x.Append(y.Append(z)),
        new DateTimeOffsetAdjustmentComparer());
}

Where GenerateAdjustment is defined like this:

private static Gen<IDateTimeOffsetAdjustment> GenerateAdjustment()
{
    return Gen.Elements<IDateTimeOffsetAdjustment>(
        new IdentityDateTimeOffsetAdjustment(),
        new BusinessHoursAdjustment(),
        new DutchBankDayAdjustment(),
        new NextMonthAdjustment(),
        new UtcAdjustment());
}

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:

private class DateTimeOffsetAdjustmentComparer : IEqualityComparer<IDateTimeOffsetAdjustment>
{
    public bool Equals(IDateTimeOffsetAdjustment x, IDateTimeOffsetAdjustment y)
    {
        var rnd = new System.Random();
        var dt = new DateTimeOffset(rnd.Next(), TimeSpan.Zero);
        return x.Adjust(dt) == y.Adjust(dt);
    }
 
    public int GetHashCode(IDateTimeOffsetAdjustment obj)
    {
        return 0;
    }
}

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,

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:

Prelude> (f . (g . f)) (-1)
1
Prelude> ((f . g) . f) (-1)
1
Prelude> (f . (g . f)) 0
7
Prelude> ((f . g) . f) 0
7
Prelude> (f . (g . f)) 1
13
Prelude> ((f . g) . f) 1
13
Prelude> (f . (g . f)) 2
19
Prelude> ((f . g) . f) 2
19

Casual experiments with f . f . g also indicates associativity.

I've also tried with QuickCheck:

Prelude> import Test.QuickCheck
Prelude Test.QuickCheck> f x = x + 1
Prelude Test.QuickCheck> g x = x * 6
Prelude Test.QuickCheck> :{
Prelude Test.QuickCheck| endoIsAssociative :: Int -> Bool
Prelude Test.QuickCheck| endoIsAssociative x = ((f . g) . f) x == (f . (g . f)) x
Prelude Test.QuickCheck| :}
Prelude Test.QuickCheck> quickCheck $ withMaxSuccess 100000 endoIsAssociative
+++ OK, passed 100000 tests.

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 can prove 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 reasoning from this article by Bartosz Milewski, so I'm using that notation. The goal is to prove that:

(f . g) . h == f . (g . h)

for any three (pure) functions f, g, and h, where the binary operation is question is the composition operator (.) given as:

(f . g) x = f (g x)

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:

  (f . g) . h
= { eta expansion }
  (\x -> (f . g) x) . h
= { definition of (.) }
  (\x -> f (g x)) . h
= { eta expansion }
  \y -> ((\x -> f (g x)) . h) y
= { definition of (.) }
  \y -> (\x -> f (g x)) (h y)
= { substitution (x = (h y)) }
  \y -> f (g (h y))
= { definition of (.) }
  \y -> f ((g . h) y)
= { definition of (.) }
  \y -> (f . (g . h)) y
= { eta reduction }
  f . (g . h)

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 simpler proof 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!