[LINQ via C# series]

[Category Theory via C# series]

Latest version: https://weblogs.asp.net/dixin/category-theory-via-csharp-4-natural-transformation

Natural transformation

If F: C -> D and G: C -> D are both functors from categories C to category D, a mapping can be constructed between F and G, called natural transformation and denoted η : F ⇒ G.

η: F ⇒ G is a family of morphisms from F to G, satisfying:

• ∀ X ∈ ob(C), there is a morphism η_X: F(X) → G(X) associated to X, called the component of η at X.
• ∀ m: X → Y ∈ hom(C), there is η_Y ∘ F(m) ≌ G(m) ∘ η_X

Natural transformations for LINQ

Previous parts demonstrated IEnumerable<> is the built-in functor, and Tuple<>, Lazy<>, Func<>, Nullable<> are functors too. C# has full LINQ support for IEnumerable<> because all the required extension methods are built-in in .NET. In other functors, taking the simplest Id<> as example:

// Cannot be compiled.
Nullable<int> query = from x in nullable
                      where x > 0
                      select x + 1;

This cannot be compiled. Apparently C# compiler does not know how to handle “where”. The C# language spec requires a list query methods to be implemented for corresponding LINQ syntax support, like Where is required for the above query to be compiled. It would be nice if the other functors can be mapped to IEnumerable<> by some natural transformations, so that the built in IEnumerable<> query methods can be leveraged. Actually, with the yield syntactic sugar, these natural transformations are really easy to implement:

[Pure]
public static partial class NaturalTransformations
{
    // Lazy<> => IEnumerable<>
    public static IEnumerable<T> ToEnumerable<T>(this Lazy<T> lazy)
    {
        yield return lazy.Value;
    }

    // Func<> => IEnumerable<>
    public static IEnumerable<T> ToEnumerable<T>(this Func<T> function)
    {
        yield return function();
    }

    // Nullable<> => IEnumerable<>
    public static IEnumerable<T> ToEnumerable<T>(this Nullable<T> nullable)
    {
        if (nullable.HasValue)
        {
            yield return nullable.Value;
        }
    }
}

Now full LINQ support are available for all those functors too, with the laziness remains.

IEnumerable<int> query = from x in function.ToEnumerable() 
                         where x > 0 
                         select x + 1;

Unit tests

Please notice the query itself becomes IEnumerbale<> too, either empty or containing 1 item.

[TestClass()]
public class NaturalTransformationsTests
{
    [TestMethod()]
    public void LazyToEnumerableTest()
    {
        Lazy<int> functor = new Lazy<int>(() => 1);
        IEnumerable<int> query1 = from x in functor.ToEnumerable()
                                  where x > 0
                                  select x;
        Assert.IsTrue(query1.Any());
        Assert.AreEqual(1, query1.Single());
        IEnumerable<int> query2 = from x in functor.ToEnumerable()
                                  where x < 0
                                  select x;
        Assert.IsFalse(query2.Any());
    }

    [TestMethod()]
    public void FuncToEnumerableTest()
    {
        Func<int> functor = () => 1;
        IEnumerable<int> query1 = from x in functor.ToEnumerable()
                                  where x > 0
                                  select x;
        Assert.IsTrue(query1.Any());
        Assert.AreEqual(1, query1.Single());
        IEnumerable<int> query2 = from x in functor.ToEnumerable()
                                  where x < 0
                                  select x;
        Assert.IsFalse(query2.Any());
    }

    [TestMethod()]
    public void NullableToEnumerableTest()
    {
        Nullable<int> functor = new Nullable<int>(() => Tuple.Create(true, 1));
        IEnumerable<int> query1 = from x in functor.ToEnumerable()
                                  where x > 0
                                  select x;
        Assert.IsTrue(query1.Any());
        Assert.AreEqual(1, query1.Single());
        IEnumerable<int> query2 = from x in functor.ToEnumerable()
                                  where x < 0
                                  select x;
        Assert.IsFalse(query2.Any());

        IEnumerable<int> query3 = from x in new Nullable<int>().ToEnumerable()
                                  select x;
        Assert.IsFalse(query3.Any());
    }
}