[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 m₁: X → Y, m₂: Y → Z,  m₁ and m₂ can compose as m₂ ∘ m₁: X → Z.
  • The name of m₁ of m₂ also implies the order. m2 ∘ m1 can be read as m₂ after m₁.

and satisfies 2 category laws:

1. The ability to compose the morphisms associatively: For m₁: W → X, m₂: X → Y and m₃: Y → Z, there is (m₃ ∘ m₂) ∘ m₁ ≌ m₃ ∘ (m₂ ∘ m₁).
                                                                                                                                   
2. The existence of an identity morphism for each object: id_x : X → X. For m: X → Y, there is id_Y ∘ m ≌ m ≌ m ∘ id_X.
   

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

public interface ICategory<TCategory> where TCategory : ICategory<TCategory>
{
    // o = (m2, m1) -> composition
    [Pure]
    IMorphism<TSource, TResult, TCategory> o<TSource, TMiddle, TResult>(
        IMorphism<TMiddle, TResult, TCategory> m2, IMorphism<TSource, TMiddle, TCategory> m1);

    [Pure]
    IMorphism<TObject, TObject, TCategory> Id<TObject>();
}

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

    [Pure]
    TResult Invoke(TSource source);
}

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:

public class DotNet : ICategory<DotNet>
{
    [Pure]
    public IMorphism<TObject, TObject, DotNet> Id<TObject>
        () => new DotNetMorphism<TObject, TObject>(@object => @object);

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

    private DotNet()
    {
    }

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

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

    public DotNetMorphism(Func<TSource, TResult> function)
    {
        this.function = function;
    }

    public DotNet Category
    {
        [Pure]get {return DotNet.Category;}
    }

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

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<string>, Id<int>(), id<bool>(), etc. (This is also called code explosion in .NET):