[LINQ via C# series]#

[Category Theory via C# series]#

Latest version: https://weblogs.asp.net/dixin/category-theory-via-csharp-3-functor-and-linq-to-functors#

Functor Category#

Given 2 categories C and D, functors C → D forms a functor category, denoted DC:

• ob(DC): those functors C → D
• hom(DC): natural transformations between those functors
• ∘: natural transformations F ⇒ G and G ⇒ H compose to natural transformations F ⇒ H

Here is an example of natural transformations composition:

1
// [Pure]
2
public static partial class NaturalTransformations
3
{
4
    // Lazy<> => Func<>
5
    public static Func<T> ToFunc<T>
6
        (this Lazy<T> lazy) => () => lazy.Value;
7

8
    // Func<> => Nullable<>
9
    public static Nullable<T> ToNullable<T>
10
        (this Func<T> function) => new Nullable<T>(() => Tuple.Create(true, function()));
11
}

These 2 natural transformation Lazy<> ⇒ Func<> and Func<> ⇒ Nullable<> can compose to a new natural transformation Lazy<> ⇒ Nullable<>:

1
// Lazy<> => Nullable<>
2
public static Nullable<T> ToNullable<T>
3
    (this Lazy<T> lazy) =>
4
        // new Func<Func<T>, Nullable<T>>(ToNullable).o(new Func<Lazy<T>, Func<T>>(ToFunc))(lazy);
5
        lazy.ToFunc().ToNullable();

Endofunctor category#

Given category C, endofunctors C → C forms an endofunctor category, denoted CC, or End(C):

• ob(End(C)): the endofunctors C → C
• hom(End(C)): the natural transformations between endofunctors: C → C
• ∘: 2 natural transformations F ⇒ G and G ⇒ H can composte to natural transformation F ⇒ H

Actually, all the above C# code examples are endofunctors DotNet → DotNet. They form the endofunctor category DotNetDotNet or End(DotNet).

Monoid laws for endofunctor category, and unit tests#

An endofunctor category C is a monoid (C, ∘, Id):

• Binary operator is ∘: the composition of 2 natural transformations F ⇒ G and G ⇒ H is still a natural transformation F ⇒ H
• Unit element: the Id natural transformation, which transforms any endofunctor X to itself - IdX: X ⇒ X

Apparently, Monoid (hom(CC), ∘, Id) satisfies the monoid laws:

1. left unit law: IdF: F ⇒ F ∘ T: F ⇒ G ≌ T: F ⇒ G, T ∈ ob(End(C))
2. right unit law: T: F ⇒ G ≌ T: F ⇒ G ∘ IdG: G ⇒ G, T ∈ ob(End(C))
3. associative law: (T1 ∘ T2) ∘ T3 ≌ T1 ∘ (T2 ∘ T3)

Take the transformations above and in previous part as example, the following test shows how natural transformations Lazy<> ⇒ Func<>, Func<> ⇒ Nullable<>, Nullable<> ⇒ => IEnumerable<> composite associatively:

1
[TestClass()]
2
public partial class NaturalTransformationsTests
3
{
4
    [TestMethod()]
5
    public void CompositionTest()
6
    {
7
        Lazy<int> functor = new Lazy<int>(() => 1);
8
        Tuple<Func<Lazy<int>, IEnumerable<int>>, Func<Lazy<int>, IEnumerable<int>>> compositions = Compositions<int>();
9
        IEnumerable<int> x = compositions.Item1(functor);
10
        IEnumerable<int> y = compositions.Item2(functor);
11
        Assert.AreEqual(x.Single(), y.Single());
12
    }
13

14
    private Tuple<Func<Lazy<T>, IEnumerable<T>>, Func<Lazy<T>, IEnumerable<T>>> Compositions<T>()
15
    {
16
        Func<Lazy<T>, Func<T>> t1 = NaturalTransformations.ToFunc;
17
        Func<Func<T>, Nullable<T>> t2 = NaturalTransformations.ToNullable;
18
        Func<Nullable<T>, IEnumerable<T>> t3 = NaturalTransformations.ToEnumerable;
19
        Func<Lazy<T>, IEnumerable<T>> x = t3.o(t2).o(t1);
20
        Func<Lazy<T>, IEnumerable<T>> y = t3.o(t2.o(t1));
21
        return Tuple.Create(x, y);
22
    }
23
}