[LINQ via C# series]#

[Category Theory via C# series]#

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

This post and the following posts will introduce category theory and its important concepts via C# and LINQ, including functor, applicative functor, monoid, monad, etc. Categories were first introduced by Samuel Eilenberg and Saunders Mac Lane in 1942–45. It might be tedious, as Wikipedia pointed:

A term dating from the 1940s, “general abstract nonsense”, refers to its high level of abstraction.

so these posts will have minimum theory, and a lot of C#/LINQ code to make some “specific intuitive sense”.

Category and category laws#

A category C consists of:

• A collection of objects, denoted ob(C). This is not the objects in OOP.
• A collection of morphisms between objects, denoted hom(C).
  • A morphism m from object A to object B is denoted m: X → Y:
    • X is called source object.
    • Y is called target object. To align to C# terms, Y will be called result object in these posts.
• Composition operation of morphisms, denoted ∘.
  • For objects X,Y, Z, and morphisms m1: X → Y, m2: Y → Z, m1 and m2 can compose as m2 ∘ m1: X → Z.
  • The name of m1 of m2 also implies the order. m2 ∘ m1 can be read as m2 after m1.

and satisfies 2 category laws:

1. The ability to compose the morphisms associatively: For m1: W → X, m2: X → Y and m3: Y → Z, there is (m3 ∘ m2) ∘ m1 ≌ m3 ∘ (m2 ∘ m1).
2. The existence of an identity morphism for each object: idx : X → X. For m: X → Y, there is idY ∘ m ≌ m ≌ m ∘ idX.

To make above general definitions more intuitive, category and its morphism can be represented by:

1
public interface ICategory<TCategory> where TCategory : ICategory<TCategory>
2
{
3
    // o = (m2, m1) -> composition
4
    [Pure]
5
    IMorphism<TSource, TResult, TCategory> o<TSource, TMiddle, TResult>(
6
        IMorphism<TMiddle, TResult, TCategory> m2, IMorphism<TSource, TMiddle, TCategory> m1);
7

8
    [Pure]
9
    IMorphism<TObject, TObject, TCategory> Id<TObject>();
10
}
11

12
public interface IMorphism<in TSource, out TResult, out TCategory> where TCategory : ICategory<TCategory>
13
{
14
    [Pure]
15
    TCategory Category { get; }
16

17
    [Pure]
18
    TResult Invoke(TSource source);
19
}

For convenience, the composition function is uncurried with 2 arity. But this is no problem, because any function cannot curried or uncurried.

All members in above interfaces are tagged as [Pure] to indicate all their are all pure functions (C# property will be compiled to get/set functions too). The purity will be explained later.

The .NET category and morphism#

Instead of general abstraction, in C#, the main category to play with is the .NET category:

• ob(DotNet) are .NET types, like int (System.Int32), bool (System.Boolean), etc.
• hom(DotNet) are C# pure functions, like f : int → bool, etc.
• Composition operation of morphisms is the composition of C# functions introduced in previous lambda calculus part.

Now it starts to make more sense:

1
public class DotNet : ICategory<DotNet>
2
{
3
    [Pure]
4
    public IMorphism<TObject, TObject, DotNet> Id<TObject>
5
        () => new DotNetMorphism<TObject, TObject>(@object => @object);
6

7
    [Pure]
8
    public IMorphism<TSource, TResult, DotNet> o<TSource, TMiddle, TResult>
9
        (IMorphism<TMiddle, TResult, DotNet> m2, IMorphism<TSource, TMiddle, DotNet> m1) =>
10
            new DotNetMorphism<TSource, TResult>(@object => m2.Invoke(m1.Invoke(@object)));
11

12
    private DotNet()
13
    {
14
    }
15

16
    public static DotNet Category {[Pure] get; } = new DotNet();
17
}
18

19
public class DotNetMorphism<TSource, TResult> : IMorphism<TSource, TResult, DotNet>
20
{
21
    private readonly Func<TSource, TResult> function;
22

23
    public DotNetMorphism(Func<TSource, TResult> function)
24
    {
25
        this.function = function;
26
    }
27

28
    public DotNet Category
29
    {
30
        [Pure]get {return DotNet.Category;}
31
    }
32

33
    [Pure]
34
    public TResult Invoke
35
        (TSource source) => this.function(source);
36
}

As expected, DotNetMorphism<TSource, TResult> become just a wrapper of Func<TSource, TResult> function.

And the DotNet category satisfies the category laws:

1. The associativity of morphisms’ (C# functions’) composition is already proven before.
2. The morphism returned by Id() is a wrapper of generic function (@object => @object), but it can be compiled to a copy for each closed type (each object ∈ ob(DotNet)), like Id, Id(), id(), etc. (This is also called code explosion in .NET):