Category Theory via C# (2) Monoid

1435 words

7 minutes

Category Theory via C# (2) Monoid

2018-12-03

.NET

/

.NET Core

/

.NET Standard

/

C#

/

LINQ

[LINQ via C# series]#

[Category Theory via C# series]#

Latest version: https://weblogs.asp.net/dixin/category-theory-via-csharp-2-monoid#

Monoid and monoid laws#

A monoid, denoted a 3-tuple (M, ⊙, I), is a set M with

a binary operator ⊙ : M ⊙ M → M
- This operation M ⊙ M → M is denoted μ
and a special element unit, denoted I, I ∈ M
- I → M is denoted η

satisfying:

left unit law λX: I ⊙ X ≌ X
right unit law ρX: X ≌ X ⊙ I
associative law αX, Y, Z: (X ⊙ Y) ⊙ Z ≌ X ⊙ (Y ⊙ Z)

so that:

the triangle identity commutes:
and the pentagon identity commutes::
and apparently:

This is quite general and abstract. A intuitive example is the set of all integers, with operator + and unit 0. So this 3-tuple (integer, +, 0) satisfies:

0 + x ≌ x
x ≌ x + 0
(x + y) + z ≌ x + (y + z)

where x, y, z are elements of the set of integers. Therefore (integer, +, 0) is a monoid.

A monoid can be represented in C# as:

1
public partial interface IMonoid<T>
2
{
3
    T Unit { [Pure] get; }
4

5
    Func<T, T, T> Binary { [Pure] get; }
6
}

A default implementation is straight forward:

1
public partial class Monoid<T> : IMonoid<T>
2
{
3
    public Monoid(T unit, [Pure] Func<T, T, T> binary)
4
    {
5
        this.Unit = unit;
6
        this.Binary = binary;
7
    }
8

9
    public T Unit { [Pure] get; }
10

11
    public Func<T, T, T> Binary { [Pure] get; }
12
}

C#/.NET monoids#

First of all, an extension method is created for convenience:

1
[Pure]
2
public static class MonoidExtensions
3
{
4
    public static IMonoid<T> Monoid<T>(this T unit, Func<T, T, T> binary)
5
    {
6
        return new Monoid<T>(unit, binary);
7
    }
8
}

Void and Unit monoids#

Theoretically System.Void can be a monoid. Its source code is:

1
public struct Void
2
{
3
}

which leads to only one way to get the Void value:

1
Void value = new Void();

So a monoid can be constructed as:

1
IMonoid<Void> voidMonoid = new Void().Monoid((a, b) => new Void());

However, C# compiler does not allow System.Void to be used like this. There are 2 workarounds:

Copy above Void definition to local
Use Microsoft.FSharp.Core.Unit to replace System.Void

F#’s unit is equivalent to C#’s void, and Microsoft.FSharp.Core.Unit is semantically close to System.Void. Unit’s source code is:

1
type Unit() =
2
    override x.GetHashCode() = 0
3
    override x.Equals(obj:obj) =
4
        match obj with null -> true | :? Unit -> true | _ -> false
5
    interface System.IComparable with
6
        member x.CompareTo(_obj:obj) = 0
7

8
and unit = Unit

The difference is, Unit is a class, and its only possible value is null.

1
Unit unit = null;

So a monoid can be constructed by Unit too:

1
IMonoid<Unit> unitMonoid = ((Unit)null).Monoid((a, b) => null);

More examples#

As fore mentioned, (int, +, 0) is a monoid:

1
IMonoid<int> addInt32 = 0.Monoid((a, b) => a + b);
2
Assert.AreEqual(0, addInt32.Unit);
3
Assert.AreEqual(1 + 2, addInt32.Binary(1, 2));
4

5
// Monoid law 1: Unit Binary m == m
6
Assert.AreEqual(1, addInt32.Binary(addInt32.Unit, 1));
7
// Monoid law 2: m Binary Unit  == m
8
Assert.AreEqual(1, addInt32.Binary(1, addInt32.Unit));
9
// Monoid law 3: (m1 Binary m2) Binary m3 == m1 Binary (m2 Binary m3)
10
Assert.AreEqual(addInt32.Binary(addInt32.Binary(1, 2), 3), addInt32.Binary(1, addInt32.Binary(2, 3)));

Brian Beckman had a clock monoid in a video - consider numbers on the clock:

If a ⊙ b is defined as a => b => (a + b) % 12, then 12 becomes the unit. So:

1
IMonoid<int> clock = 12.Monoid((a, b) => (a + b) % 12);

Here are more similar examples:

(int, *, 1)
(string, string.Concat, string.Empty)
(bool, ||, false)
(bool, &&, true)
(IEnumerable, Enumerable.Concat, Enumerable.Empty())

Nullable monoid#

And monoid (Nullable, ⊙, I) is interesting.

First of all, the built-in System.Nullable<> only works for value type, since reference type can naturally be null. Here for the category theory discussion, a Nullable for any type can be reinvented:

1
public class Nullable<T>
2
{
3
    private readonly Lazy<Tuple<bool, T>> factory;
4

5
    public Nullable(Func<Tuple<bool, T>> factory = null)
6
    {
7
        this.factory = factory == null ? null : new Lazy<Tuple<bool, T>>(factory);
8
    }
9

10
    public bool HasValue
11
    {
12
        [Pure]
13
        get
14
        {
15
            return this.factory?.Value != null && this.factory.Value.Item1 && this.factory.Value.Item2 != null;
16
        }
17
    }
18

19
    public T Value
20
    {
21
        [Pure]
22
        get
23
        {
24
            // Message is copied from mscorlib.dll string table, where key is InvalidOperation_NoValue.
25
            Contract.Requires<InvalidOperationException>(this.HasValue, "Nullable object must have a value.");
26

27
            return this.factory.Value.Item2;
28
        }
29
    }
30
}

This Nullable’s constructor takes a factory function which returns a tuple of bool and T value:

When factory function is not provided (null), Nullable does not have value.
When factory function is provided, the function returns a tuple if executed.
- The tuple’s bool value indicates there is a value available (because when T is a value type, the other item in the tuple cannot be null).
- When the bool is true and the other T value is not null, Nullable has a value.

Below is one way to define the binary operator ⊙, taking new Nullable() - a Nullable has no value - as the unit:

1
[Pure]
2
public static partial class MonoidExtensions
3
{
4
    public static IMonoid<T> Monoid<T>
5
        (this T unit, Func<T, T, T> binary) => new Monoid<T>(unit, binary);
6

7
    public static IMonoid<Nullable<TSource>> MonoidOfNullable<TSource>
8
        (this IMonoid<TSource> monoid) =>
9
            new Monoid<Nullable<TSource>>(
10
                new Nullable<TSource>(),
11
                (a, b) => new Nullable<TSource>(() =>
12
                    {
13
                        if (a.HasValue && b.HasValue)
14
                        {
15
                            return Tuple.Create(true, monoid.Binary(a.Value, b.Value));
16
                        }
17

18
                        if (a.HasValue)
19
                        {
20
                            return Tuple.Create(true, a.Value);
21
                        }
22

23
                        if (b.HasValue)
24
                        {
25
                            return Tuple.Create(true, b.Value);
26
                        }
27

28
                        return Tuple.Create(false, default(TSource));
29
                    }));
30
}

So that (Nullable, ⊙, Nullable()) becomes a monoid.

Unit tests#

These unit tests demonstrate how the monoids are constructed and how the monoid laws are satisfied:

1
[TestClass]
2
public class MonoidTests
3
{
4
    [TestMethod()]
5
    public void StringTest()
6
    {
7
        IMonoid<string> concatString = string.Empty.Monoid((a, b) => string.Concat(a, b));
8
        Assert.AreEqual(string.Empty, concatString.Unit);
9
        Assert.AreEqual("ab", concatString.Binary("a", "b"));
10

11
        // Monoid law 1: Unit Binary m == m
12
        Assert.AreEqual("ab", concatString.Binary(concatString.Unit, "ab"));
13
        // Monoid law 2: m Binary Unit == m
14
        Assert.AreEqual("ab", concatString.Binary("ab", concatString.Unit));
15
        // Monoid law 3: (m1 Binary m2) Binary m3 == m1 Binary (m2 Binary m3)
16
        Assert.AreEqual(concatString.Binary(concatString.Binary("a", "b"), "c"), concatString.Binary("a", concatString.Binary("b", "c")));
17
    }
18

19
    [TestMethod()]
20
    public void Int32Test()
21
    {
22
        IMonoid<int> addInt32 = 0.Monoid((a, b) => a + b);
23
        Assert.AreEqual(0, addInt32.Unit);
24
        Assert.AreEqual(1 + 2, addInt32.Binary(1, 2));
25

26
        // Monoid law 1: Unit Binary m == m
27
        Assert.AreEqual(1, addInt32.Binary(addInt32.Unit, 1));
28
        // Monoid law 2: m Binary Unit == m
29
        Assert.AreEqual(1, addInt32.Binary(1, addInt32.Unit));
30
        // Monoid law 3: (m1 Binary m2) Binary m3 == m1 Binary (m2 Binary m3)
31
        Assert.AreEqual(addInt32.Binary(addInt32.Binary(1, 2), 3), addInt32.Binary(1, addInt32.Binary(2, 3)));
32

33
        IMonoid<int> multiplyInt32 = 1.Monoid((a, b) => a * b);
34
        Assert.AreEqual(1, multiplyInt32.Unit);
35
        Assert.AreEqual(1 * 2, multiplyInt32.Binary(1, 2));
36

37
        // Monoid law 1: Unit Binary m == m
38
        Assert.AreEqual(2, multiplyInt32.Binary(multiplyInt32.Unit, 2));
39
        // Monoid law 2: m Binary Unit == m
40
        Assert.AreEqual(2, multiplyInt32.Binary(2, multiplyInt32.Unit));
41
        // Monoid law 3: (m1 Binary m2) Binary m3 == m1 Binary (m2 Binary m3)
42
        Assert.AreEqual(multiplyInt32.Binary(multiplyInt32.Binary(1, 2), 3), multiplyInt32.Binary(1, multiplyInt32.Binary(2, 3)));
43
    }
44

45
    [TestMethod()]
46
    public void ClockTest()
47
    {
48
        // Stolen from: http://channel9.msdn.com/Shows/Going+Deep/Brian-Beckman-Dont-fear-the-Monads
49
        IMonoid<int> clock = 12.Monoid((a, b) => (a + b) % 12);
50
        Assert.AreEqual(12, clock.Unit);
51
        Assert.AreEqual((7 + 10) % 12, clock.Binary(7, 10));
52

53
        // Monoid law 1: Unit Binary m == m
54
        Assert.AreEqual(111 % 12, clock.Binary(clock.Unit, 111));
55
        // Monoid law 2: m Binary Unit == m
56
        Assert.AreEqual(111 % 12, clock.Binary(111, clock.Unit));
57
        // Monoid law 3: (m1 Binary m2) Binary m3 == m1 Binary (m2 Binary m3)
58
        Assert.AreEqual(clock.Binary(clock.Binary(11, 22), 33), clock.Binary(11, clock.Binary(22, 33)));
59
    }
60

61
    [TestMethod()]
62
    public void BooleanTest()
63
    {
64
        IMonoid<bool> orBoolean = false.Monoid((a, b) => a || b);
65
        Assert.IsFalse(orBoolean.Unit);
66
        Assert.AreEqual(true || false, orBoolean.Binary(true, false));
67

68
        // Monoid law 1: Unit Binary m == m
69
        Assert.AreEqual(true, orBoolean.Binary(orBoolean.Unit, true));
70
        Assert.AreEqual(false, orBoolean.Binary(orBoolean.Unit, false));
71
        // Monoid law 2: m Binary Unit == m
72
        Assert.AreEqual(true, orBoolean.Binary(true, orBoolean.Unit));
73
        Assert.AreEqual(false, orBoolean.Binary(false, orBoolean.Unit));
74
        // Monoid law 3: (m1 Binary m2) Binary m3 == m1 Binary (m2 Binary m3)
75
        Assert.AreEqual(orBoolean.Binary(orBoolean.Binary(true, false), true), orBoolean.Binary(true, orBoolean.Binary(false, true)));
76

77
        IMonoid<bool> andBoolean = true.Monoid((a, b) => a && b);
78
        Assert.IsTrue(andBoolean.Unit);
79
        Assert.AreEqual(true && false, andBoolean.Binary(true, false));
80

81
        // Monoid law 1: Unit Binary m == m
82
        Assert.AreEqual(true, andBoolean.Binary(andBoolean.Unit, true));
83
        Assert.AreEqual(false, andBoolean.Binary(andBoolean.Unit, false));
84
        // Monoid law 2: m Binary Unit == m
85
        Assert.AreEqual(true, andBoolean.Binary(true, andBoolean.Unit));
86
        Assert.AreEqual(false, andBoolean.Binary(false, andBoolean.Unit));
87
        // Monoid law 3: (m1 Binary m2) Binary m3 == m1 Binary (m2 Binary m3)
88
        Assert.AreEqual(andBoolean.Binary(andBoolean.Binary(true, false), true), andBoolean.Binary(true, andBoolean.Binary(false, true)));
89
    }
90

91
    [TestMethod()]
92
    public void EnumerableTest()
93
    {
94
        IMonoid<IEnumerable<int>> concatEnumerable = Enumerable.Empty<int>().Monoid((a, b) => a.Concat(b));
95
        Assert.IsFalse(concatEnumerable.Unit.Any());
96
        int[] x = new int[] { 0, 1, 2 };
97
        int[] y = new int[] { 3, 4, 5 };
98
        EnumerableAssert.AreEqual(concatEnumerable.Binary(x, y), x.Concat(y));
99

100
        // Monoid law 1: Unit Binary m == m
101
        EnumerableAssert.AreEqual(concatEnumerable.Binary(concatEnumerable.Unit, x), x);
102
        // Monoid law 2: m Binary Unit == m
103
        EnumerableAssert.AreEqual(concatEnumerable.Binary(x, concatEnumerable.Unit), x);
104
        // Monoid law 3: (m1 Binary m2) Binary m3 == m1 Binary (m2 Binary m3)
105
        EnumerableAssert.AreEqual(
106
            concatEnumerable.Binary(concatEnumerable.Binary(x, y), x),
107
            concatEnumerable.Binary(x, concatEnumerable.Binary(y, x)));
108
    }
109

110
    [TestMethod()]
111
    public void NullableTest()
112
    {
113
        IMonoid<int> addInt32 = 0.Monoid((a, b) => a + b);
114
        IMonoid<Nullable<int>> addNullable = addInt32.MonoidOfNullable();
115
        Assert.IsFalse(addNullable.Unit.HasValue);
116
        Assert.AreEqual(addInt32.Binary(1, 2), addNullable.Binary(1.Nullable(), 2.Nullable()).Value);
117
        Assert.AreEqual(1, addNullable.Binary(1.Nullable(), new Nullable<int>()).Value);
118
        Assert.AreEqual(2, addNullable.Binary(new Nullable<int>(), 2.Nullable()).Value);
119
        Assert.IsFalse(addNullable.Binary(new Nullable<int>(), new Nullable<int>()).HasValue);
120

121
        // Monoid law 1: Unit Binary m == m
122
        Assert.AreEqual(1, addNullable.Binary(addNullable.Unit, 1.Nullable()).Value);
123
        // Monoid law 2: m Binary Unit == m
124
        Assert.AreEqual(1, addNullable.Binary(1.Nullable(), addNullable.Unit).Value);
125
        // Monoid law 3: (m1 Binary m2) Binary m3 == m1 Binary (m2 Binary m3)
126
        Nullable<int> left = addNullable.Binary(addNullable.Binary(1.Nullable(), 2.Nullable()), 3.Nullable());
127
        Nullable<int> right = addNullable.Binary(1.Nullable(), addNullable.Binary(2.Nullable(), 3.Nullable()));
128
        Assert.AreEqual(left.Value, right.Value);
129
    }
130
}