Category Theory via C# (1) Fundamentals - Category, Object And Morphism

[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 ∘.
    image
    • 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).
    image                                                                                                                                
  2. The existence of an identity morphism for each object: idx : X → X. For m: X → Y, there is idY ∘ m ≌ m ≌ m ∘ idX.
    image


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:

image

  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):

17 Comments

Add a Comment

As it will appear on the website

Not displayed

Your website