Category Theory via C# (4) Functor And IEnumerable<>

[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 and functor laws#

A functor F: C → D is a structure-preserving mapping from category C to category D:

As above diagram represented, F:

maps objects X, Y ∈ ob(C) to objects F(X), F(Y) ∈ ob(D)
also maps morphism mC: X → Y ∈ hom(C) to a new morphism mD: F(X) → F(Y) ∈ hom(D)
- To align to C#/.NET terms, this mapping ability of functor will be called “select” instead of “map”. That is, F selects mC to mD .

and satisfies the functor laws:

F(idX) ≌ idF(X), see above image
Select(m2 ∘ m1) ≌ Select(m2) ∘ Select(m1)

So the general functor should be like:

1
// Cannot be compiled.
2
public interface IFunctor<in TSourceCategory, out TTargetCategory, TFunctor<>>
3
    where TSourceCategory : ICategory<TSourceCategory>
4
    where TTargetCategory : ICategory<TTargetCategory>
5
    where TFunctor<> : IFunctor<TSourceCategory, TTargetCategory, TFunctor<>>
6
{
7
    IMorphism<TFunctor<TSource>, TFunctor<TResult>, TTargetCategory> Select<TSource, TResult>(
8
        IMorphism<TSource, TResult, TSourceCategory> selector);
9
}

A TFunctor<>, which implements IFunctor<…> interface, should have a method Select, which takes a morphism from TSource to TResult in TFromCategory, and returns a morphism from TFunctor to TFunctor in TToCategory.

C#/.NET functors#

A C# functor can select (maps) a morphism in DotNet category to another morphism still in DotNet category, such functor maps from a category to itself is called endofunctor.

Endofunctor#

A endofunctor can be defined as:

1
// Cannot be compiled.
2
public interface IEndofunctor<TCategory, TEndofunctor<>>
3
    : IFunctor<TCategory, TCategory, TEndofunctor<>>
4
    where TCategory : ICategory<TCategory>
5
    where TEndofunctor<> : IFunctor<TEndofunctor, TEndofunctor<>>
6
{
7
    IMorphism<TEndofunctor<TSource>, TEndofunctor<TResult>, TCategory> Select<TSource, TResult>(
8
        IMorphism<TSource, TResult, TCategory> selector);
9
}

So an endofunctor in DotNet category, e.g. EnumerableFunctor, should be implemented as:

1
// Cannot be compiled.
2
// EnumerableFunctor<>: DotNet -> DotNet
3
public class EnumerableFunctor<T> : IFunctor<DotNet, DotNet, EnumerableFunctor<>>
4
{
5
    public IMorphism<EnumerableFunctor<TSource>, EnumerableFunctor<TResult>, DotNet> Select<TSource, TResult>(
6
        IMorphism<TSource, TResult, DotNet> selector)
7
    {
8
        // ...
9
    }
10
}

Unfortunately, all the above code cannot be compiled, because C# does not support higher-kinded polymorphism. This is actually the biggest challenge of explaining category theory in C#.

Kind issue of C# language/CLR#

Kind is the (meta) type of a type. In another word, a type’s kind is like a function’s type. For example:

int’s kind is *, where * can be read as a concrete type or closed type. This is like function (() => 0)’s type is Func.
IEnumerable is a closed type, its kind is also *.
IEnumerable<> is a open type, its kind is * → *, which can be read as taking a closed type (e.g. int) and constructs another closed type (IEnumerable). This is like function ((int x) => x)’s type is Func<int, int>.
In above IFunctor<TFromCategory, TToCategory, TFunctor<>> definition, its type parameter TFunctor<> has a kind * → *, which makes IFunctor<TFromCategory, TToCategory, TFunctor<>> having a higher order kind: * → * → (* → *) → *. This is like a function become a higher order function if its parameter is a function.

Unfortunately, C# does not support type with higher order kind. As Erik Meijer mentioned in this video, the reasons are:

CLR does not support higher order kind
Supporting higher order kind causes more kind issues. For example, IDictionary<,> is a IEnumerble<>, but they have different kinds: * → * → * vs. * → *.

So, instead of higher-kinded polymorphism, C# recognizes the functor pattern of each functor, which will be demonstrated by following code.

The built-in IEnumerable<> functor#

IEnumerable is the a built-in functor in C#/.NET. Why it is a functor and How is this implemented? First, in DotNet category, if IEnumerable<> is a functor, it should be an endofunctor IEnumerable<>: DotNet → DotNet.

1
public static IMorphism<IEnumerable<TSource>, IEnumerable<TResult>, DotNet> Select<TSource, TResult>(
2
    IMorphism<TSource, TResult, DotNet> selector)
3
{
4
    // ...
5
}

IEnumerable should be able to do the above select/map from DotNet category to DotNet category.

Second, in DotNet category, morphisms are functions. That is, IMorphism<TSouece, TResult, DotNet> and Func<TSouece, TResult> can convert to each other. So above select/map is equivalent to:

1
// Select = selector -> (source => result)
2
public static Func<IEnumerable<TSource>, IEnumerable<TResult>> Select<TSource, TResult>(
3
    Func<TSource, TResult> selector)
4
{
5
    // ...
6
}

Now Select’s type is Func<T1, Func<T2, TResult>>, so it is a curried function. It can be uncurried to a equivalent Func<T1, T2, TResult>:

1
// Select = (selector, source) -> result
2
public static IEnumerable<TResult> Select<TSource, TResult>( // Uncurried
3
    Func<TSource, TResult> selector, IEnumerable<TSource> source)
4
{
5
    // ...
6
}

The positions of 2 parameters can be swapped:

1
// Select = (source, selector) -> result
2
public static IEnumerable<TResult> Select<TSource, TResult>( // Parameter swapped
3
    IEnumerable<TSource> source, Func<TSource, TResult> selector)
4
{
5
    // ...
6
}

The final step is to make Select an extension method by adding a this keyword:

1
// Select = (this source, selector) -> result
2
public static IEnumerable<TResult> Select<TSource, TResult>( // Extension method
3
    this IEnumerable<TSource> source, Func<TSource, TResult> selector)
4
{
5
    // ...
6
}

which is just a syntactic sugar and does not change anything. The above transformation shows:

In DotNet category, IEnumerable<>’s functoriality is equivalent to a simple familiar extension method Select
If the last Select version above can be implemented, then IEnumerable is a functor.

IEnumerable’s Select extension method is already implemented as System.Linq.Enumerable.Select. But it is easy to implement manually:

1
[Pure]
2
public static partial class EnumerableExtensions
3
{
4
    // C# specific functor pattern.
5
    public static IEnumerable<TResult> Select<TSource, TResult>( // Extension
6
        this IEnumerable<TSource> source, Func<TSource, TResult> selector)
7
    {
8
        foreach (TSource item in source)
9
        {
10
            yield return selector(item);
11
        }
12
    }
13

14
    // General abstract functor definition of IEnumerable<>: DotNet -> DotNet.
15
    public static IMorphism<IEnumerable<TSource>, IEnumerable<TResult>, DotNet> Select<TSource, TResult>
16
        (this IMorphism<TSource, TResult, DotNet> selector) =>
17
            new DotNetMorphism<IEnumerable<TSource>, IEnumerable<TResult>>(
18
                source => source.Select(selector.Invoke));
19
}

So IEnumerable is a functor, The both Select functions are implemented as extension method for convenience.

Functor pattern of LINQ#

Generally in C#, if a type F:

have a instance method or extension method Select, taking a Func<TSource, TResult> parameter and returning a F

then:

F<> is an endofunctor F<>: DotNet → DotNet
- F<> maps objects TSource, TResult ∈ ob(DotNet) to objects F, F ∈ ob(DotNet)
- F<> also selects morphism selector : TSource → TResult ∈ hom(DotNet) to new morphism : F → F ∈ hom(DotNet)
F<> is a C# functor, its Select method can be recognized by C# compiler, so the LINQ syntax can be used:

1
IEnumerable<int> enumerableFunctor = Enumerable.Range(0, 3);
2
IEnumerable<int> query = from x in enumerableFunctor select x + 1;

which is compiled to:

1
IEnumerable<int> enumerableFunctor = Enumerable.Range(0, 3);
2
Func<int, int> addOne = x => x + 1;
3
IEnumerable<int> query = enumerableFunctor.Select(addOne);

IEnumerable<>, functor laws, and unit tests#

To test IEnumerable<> with the functor laws, some helper functions can be created for shorter code:

1
[Pure]
2
public static class MorphismExtensions
3
{
4
    public static IMorphism<TSource, TResult, DotNet> o<TSource, TMiddle, TResult>(
5
        this IMorphism<TMiddle, TResult, DotNet> m2, IMorphism<TSource, TMiddle, DotNet> m1)
6
    {
7
        Contract.Requires(m2.Category == m1.Category, "m2 and m1 are not in the same category.");
8

9
        return m1.Category.o(m2, m1);
10
    }
11

12
    public static IMorphism<TSource, TResult, DotNet> DotNetMorphism<TSource, TResult>
13
        (this Func<TSource, TResult> function) => new DotNetMorphism<TSource, TResult>(function);
14
}

The above extension methods are created to use ∘ as infix operator instead of prefix, for fluent coding, and to convert a C# function to a morphism in DotNet category.

And an Id helper function can make code shorter:

1
[Pure]
2
public static partial class Functions
3
{
4
    // Id is alias of DotNet.Category.Id().Invoke
5
    public static T Id<T>
6
        (T value) => DotNet.Category.Id<T>().Invoke(value);
7
}

Finally, an assertion method for IEnumerable:

1
// Impure.
2
public static class EnumerableAssert
3
{
4
    public static void AreEqual<T>(IEnumerable<T> expected, IEnumerable<T> actual)
5
    {
6
        Assert.IsTrue(expected.SequenceEqual(actual));
7
    }
8
}

The following is the tests for IEnumerable as a general functor - selecting/mapping between objects and morphisms:

1
[TestClass()]
2
public partial class FunctorTests
3
{
4
    [TestMethod()]
5
    public void EnumerableGeneralTest()
6
    {
7
        IEnumerable<int> functor = new int[] { 0, 1, 2 };
8
        Func<int, int> addOne = x => x + 1;
9

10
        // Functor law 1: F.Select(Id) == Id(F)
11
        EnumerableAssert.AreEqual(functor.Select(Functions.Id), Functions.Id(functor));
12
        // Functor law 2: F.Select(f2.o(f1)) == F.Select(f1).Select(f2)
13
        Func<int, string> addTwo = x => (x + 2).ToString(CultureInfo.InvariantCulture);
14
        IMorphism<int, int, DotNet> addOneMorphism = addOne.DotNetMorphism();
15
        IMorphism<int, string, DotNet> addTwoMorphism = addTwo.DotNetMorphism();
16
        EnumerableAssert.AreEqual(
17
            addTwoMorphism.o(addOneMorphism).Select().Invoke(functor),
18
            addTwoMorphism.Select().o(addOneMorphism.Select()).Invoke(functor));
19
    }
20
}

And the following is the tests for IEnumerable as a C# functor:

1
public partial class FunctorTests
2
{
3
    [TestMethod()]
4
    public void EnumerableCSharpTest()
5
    {
6
        bool isExecuted1 = false;
7
        IEnumerable<int> enumerable = new int[] { 0, 1, 2 };
8
        Func<int, int> f1 = x => { isExecuted1 = true; return x + 1; };
9

10
        IEnumerable<int> query1 = from x in enumerable select f1(x);
11
        Assert.IsFalse(isExecuted1); // Laziness.
12

13
        EnumerableAssert.AreEqual(new int[] { 1, 2, 3 }, query1); // Execution.
14
        Assert.IsTrue(isExecuted1);
15

16
        // Functor law 1: F.Select(Id) == Id(F)
17
        EnumerableAssert.AreEqual(enumerable.Select(Functions.Id), Functions.Id(enumerable));
18
        // Functor law 2: F.Select(f2.o(f1)) == F.Select(f1).Select(f2)
19
        Func<int, string> f2 = x => (x + 2).ToString(CultureInfo.InvariantCulture);
20
        EnumerableAssert.AreEqual(
21
            enumerable.Select(f2.o(f1)),
22
            enumerable.Select(f1).Select(f2));
23
        // Functor law 2: F.Select(f2.o(f1)) == F.Select(f1).Select(f2)
24
        EnumerableAssert.AreEqual(
25
            from x in enumerable select f2.o(f1)(x),
26
            from y in (from x in enumerable select f1(x)) select f2(y));
27
    }
28
}

IEnumerable<> is like the List functor in Haskell.