Colour-mixing magma by Mark Seemann

Mixing RGB colours forms a magma. An example for object-oriented programmers.

This article is part of a larger series about monoids, semigroups, and other group-like algebraic structures. In this article, you'll see an example of a magma, which is a binary operation without additional constraints.

RGB colours #

The opening article about monoids, semigroups, and their friends emphasised Eric Evans' pigment mixing example from Domain-Driven Design. The following article series then promptly proceeded to ignore that example. The reason is that while the example has Closure of Operations, it exhibits precious few other properties. It's neither monoid, semigroup, quasigroup, nor any other named binary operation, apart from being a magma.

Instead of pigments, consider a more primitive, but well-understood colour model: that of RGB colours. In C#, you can model RGB colours using a struct that holds three byte fields. In my final code base, I ended up implementing ==, !=, Equals, and so on, but I'm not going to bore you with all of those details. Here's the RgbColor constructor, so that you can get a sense of the type:

private readonly byte red;
private readonly byte green;
private readonly byte blue;
 
public RgbColor(byte red, byte green, byte blue)
{
    this.red = red;
    this.green = green;
    this.blue = blue;
}

As you can see, RgbColor holds three byte fields, one for red, green, and blue. If you want to mix two colours, you can use the MixWith instance method:

public RgbColor MixWith(RgbColor other)
{
    var newRed = ((int)this.red + (int)other.red) / 2m;
    var newGreen = ((int)this.green + (int)other.green) / 2m;
    var newBlue = ((int)this.blue + (int)other.blue) / 2m;
    return new RgbColor(
        (byte)Math.Round(newRed),
        (byte)Math.Round(newGreen),
        (byte)Math.Round(newBlue));
}

This is a binary operation, because it's an instance method on RgbColor, taking another RgbColor as input, and returning RgbColor. Since it's a binary operation, it's a magma, but could it be another, stricter category of operation?

Lack of associativity #

Could MixWith, for instance, be a semigroup? In order to be a semigroup, the binary operation must be associative, and while it can be demanding to prove that an operation is always associative, it only takes a single counter-example to prove that it's not:

[Fact]
public void MixWithIsNotAssociative()
{
    // Counter-example
    var x = new RgbColor( 67, 108,  13);
    var y = new RgbColor( 33, 114, 130);
    var z = new RgbColor( 38, 104, 245);
 
    Assert.NotEqual(
        x.MixWith(y).MixWith(z),
        x.MixWith(y.MixWith(z)));
}

This xUnit.net unit test passes, thereby demonstrating that MixWith is not associative. When you mix x with y, you get #326F48, and when you mix that with z you get #2C6C9E. On the other hand, when you mix y with z you get #246DBC, which, combined with x, gives #346C64. #2C6C9E is not equal to #346C64, so the NotEqual assertion passes.

Because of this counter-example, MixWith isn't associative, and therefore not a semigroup. Since monoid requires associativity as well, we can also rule out that MixWith is a monoid.

Lack of invertibility #

While MixWith isn't a semigroup, could it be a quasigroup? In order to be a quasigroup, a binary operation must be invertible. This means that for any two elements a and b, there must exist two other elements x and y that turns a into b.

This property must hold for all values involved in the binary operation, so again, a single counter-example suffices to demonstrate that MixWith isn't invertible, either:

[Fact]
public void MixWithIsNotInvertible()
{
    // Counter-example
    var a = new RgbColor( 94,  35, 172);
    var b = new RgbColor(151, 185,   7);
 
    Assert.False(RgbColor.All.Any(x => a.MixWith(x) == b));
    Assert.False(RgbColor.All.Any(y => y.MixWith(a) == b));
}

This xUnit.net-based test also passes. It uses brute force to demonstrate that for all RgbColor values, there's no x and y that satisfy the invertibility property. The test actually takes a while to execute, because All returns all 16,777,216 possible RgbColor values:

private static RgbColor[] all;
private readonly static object syncLock = new object();
 
public static IReadOnlyCollection<RgbColor> All
{
    get
    {
        if (all == null)
            lock (syncLock)
                if (all == null)
                {
                    var max = 256 * 256 * 256;
                    all = new RgbColor[max];
                    foreach (var i in Enumerable.Range(0, max))
                        all[i] = (RgbColor)i;
                }
 
        return all;
    }
}

For performance reasons, the All property uses lazy initialisation with double-checked locking. It simply counts from 0 to 256 * 256 * 256 (16,777,216) and converts each integer to an RgbColor value using this explicit conversion:

public static explicit operator RgbColor(int i)
{
    var red = (i & 0xFF0000) / 0x10000;
    var green = (i & 0xFF00) / 0x100;
    var blue = i & 0xFF;
    return new RgbColor((byte)red, (byte)green, (byte)blue);
}

The bottom line, though, is that the test passes, thereby demonstrating that for the chosen counter-example, no x and y satisfies the invertibility property. Therefore, MixWith isn't a quasigroup.

Lack of identity #

Since MixWith is neither associative nor invertible, it's not really any named algebraic construct, other than a magma. It's neither group, semigroup, quasigroup, monoid, loop, groupoid, etc. Does it have any properties at all, apart from being a binary operation?

It doesn't have identity either, which you can illustrate with another counter-example:

[Fact]
public void MixWithHasNoIdentity()
{
    var nearBlack = new RgbColor(1, 1, 1);
 
    var identityCandidates = from e in RgbColor.All
                             where nearBlack.MixWith(e) == nearBlack
                             select e;
    // Verify that there's only a single candidate:
    var identityCandidate = Assert.Single(identityCandidates);
    // Demonstrate that the candidate does behave like identity for
    // nearBlack:
    Assert.Equal(nearBlack, nearBlack.MixWith(identityCandidate));
    Assert.Equal(nearBlack, identityCandidate.MixWith(nearBlack));
 
    // Counter-example
    var counterExample = new RgbColor(3, 3, 3);
    Assert.NotEqual(
        counterExample, 
        counterExample.MixWith(identityCandidate));
}

The counter-example starts with a near-black colour. The reason I didn't pick absolute black (new RgbColor(0, 0, 0)) is that, due to rounding when mixing, there are eight candidates for absolute black, but only one for nearBlack. This is demonstrated by the Assert.Single assertion. identityCandidate, by the way, is also new RgbColor(1, 1, 1), and further Guard Assertions demonstrate that identityCandidate behaves like the identity for nearBlack.

You can now pick another colour, such as new RgbColor(3, 3, 3) and demonstrate that identityCandidate does not behave like the identity for the counter-example. Notice that the assertion is Assert.NotEqual.

If an identity exists for a magma, it must behave as the identity for all possible values. That's demonstrably not the case for MixWith, so it doesn't have identity.

Commutativity #

While MixWith is neither associative, invertible, nor has identity, it does have at least one property: it's commutative. This means that the order of the input values doesn't matter. In other words, for any two RgbColor values x and y, this assertion always passes:

Assert.Equal(
    x.MixWith(y),
    y.MixWith(x));

Since x.MixWith(y) is equal to y.MixWith(x), MixWith is commutative.

Summary #

The MixWith operation is a commutative magma, but while, for example, we call an associative magma a semigroup, there's no fancy word for a commutative magma.

In this article, you got another, fairly realistic, example of a binary operation. Throughout the overall article series on monoids, semigroup, and other group-like algebraic structures, you've seen many examples, and you've learned how to analyse binary operations for the presence or absence of various properties. The present article concludes the series. You can, however, continue reading the even more overall article series.

Next: Functors, applicatives, and friends

Comments

• ← Previous
• Archive
• Next →