Function monoids by Mark Seemann
Methods are monoids if they return 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).
Functions #
In statically typed C-languages, like C# or Java, methods are typically declared like this:
public Foo Bar(Baz baz, Qux qux)
As you'll see in another article, however, you can refactor any method to a method that takes a single argument as input, and returns a single (possibly complex) value as output. In abstract form, we can write it like this:
public Out1 Op1(In1 arg)
Another way to abstract a method is by using generics:
public T Op1<T1, T>(T1 x)
Another article demonstrates how this is similar to a generic function. In F#, for instance, the type of the function would be written as 'a -> 'b, whereas in Haskell it'd be written a -> b. The way to read this is that the function takes a value of the generic type T1/'a/a as input, and returns a value of the generic type T/'b/b as output. For the rest of this article, I'll favour the Haskell syntax, since it has minimal noise.
To be clear, however, although I favour the Haskell syntax because of its succinctness, I don't mean to imply that the functions that I discuss are exclusively pure - think of an F# function 'a -> 'b which may or may not be pure.
Binary combination of functions #
A function a -> b is a monoid if b is a monoid. This means that you can combine two functions with the same type. In an object-oriented context, it means that you can combine two methods with the same signature into one method as long as the return type forms a monoid.
Consider the following (facetious) C# example. You're trying to establish how secure a GUID is. Primes are important in cryptography, so the more primes a GUID contains, the better... right?
private const string primes = "2357bd"; public static int CountPrimes(Guid g) { return g.ToString("N").Count(primes.Contains); }
The CountPrimes method counts the number of prime digits in a given GUID. So far so good, but you also think that hexadecimal notation is more exotic than decimal notation, so surely, the digits A-F are somehow more secure, being more unfamiliar. Thus, you have a method to count those as well:
private const string letters = "abcdef"; public static int CountLetters(Guid g) { return g.ToString("N").Count(letters.Contains); }
Good, but both of these numbers are, clearly, excellent indicators of how secure a GUID is. Which one should you choose? Both of them, of course!
Can you combine CountPrimes and CountLetters? Yes, you can, because, while GUIDs don't form a monoid, the return type int forms a monoid over addition. This enables you to write a Combine method:
public static Func<Guid, int> Combine( Func<Guid, int> f, Func<Guid, int> g) { return x => f(x) + g(x); }
Notice that Combine takes two Func<Guid, int> values and return a new Func<Guid, int> value. It's a binary operation. Here's an example of how to use it:
var calculateSecurity = Combine(CountPrimes, CountLetters); var actual = calculateSecurity(new Guid("10763FF5-E3C8-46D1-A70F-6C1D9EDA8120")); Assert.Equal(21, actual);
Now you have an excellent measure of the security strength of GUIDs! 21 isn't that good, though, is it?
Antics aside, Combine is a binary function. Is it a monoid?
Monoid laws #
In order to be a monoid, Combine must be associative, and it is, as the following FsCheck property demonstrates:
[Property(QuietOnSuccess = true)] public void CombineIsAssociative( Func<Guid, int> f, Func<Guid, int> g, Func<Guid, int> h, Guid guid) { Assert.Equal( Combine(Combine(f, g), h)(guid), Combine(f, Combine(g, h))(guid)); }
In this property-based test, FsCheck generates three functions with the same signature. Since functions don't have structural equality, the easiest way to compare them is to call them and see whether they return the same result. This explains why the assertion invokes both associative combinations with guid. The test passes.
In order to be a monoid, Combine must also have an identity element. It does:
public static Func<Guid, int> FuncIdentity = _ => 0;
This is simply a function that ignores its input and always returns 0, which is the identity value for addition. The following test demonstrates that it behaves as expected:
[Property(QuietOnSuccess = true)] public void CombineHasIdentity(Func<Guid, int> f, Guid guid) { Assert.Equal(f(guid), Combine(FuncIdentity, f)(guid)); Assert.Equal(f(guid), Combine(f, FuncIdentity)(guid)); }
As was the case with CombineIsAssociative, in order to assert that the combined functions behave correctly, you have to call them. This, again, explains why the assertion invokes the combined functions with guid. This test passes as well.
Combine is a monoid.
Generalisation #
While the above C# code is only an example, the general rule is that any function that returns a monoid is itself a monoid. In Haskell, this rule is articulated in the standard library:
instance Monoid b => Monoid (a -> b)
This means that for any monoid b, a function a -> b is also (automatically) a monoid.
Summary #
A function or method with a return type that forms a monoid is itself a monoid.
Next: Endomorphism monoid.
