Sign in Subscribe
8 min read

Higher Kinds in C# with language-ext [Part 1]

Higher Kinds in C# with language-ext [Part 1]
Language-ext 5. A new dawn

Those who have been following the language-ext repo will know that I am building up to a really massive version 5 release. I am looking at the release notes that I have been trying to keep up to date as I go (so that I don't forget anything) and they're already up to nearly 1000 lines of text. And although there's quite a lot of content [in the release notes], there's also 100s of lines of just headings (waiting for the content)! So, the final release notes are going to be huge and a lot to take in.

Version 5 of language-ext is about as close to a rewrite as it's ever going to get. So there's a lot to cover.

Rather than have a big surprise on day 1 of the release, I figured I'd start this blog to try and prepare the ground and whet the appetite somewhat – and also terrify you enough that you upgrade with caution!

It will also allow me to keep the release notes a little lighter and just link to this blog where appropriate.

I have been talking a lot over the past year or so about bringing Transducers into language-ext – and I suspect that's the feature that most followers think is going to have the biggest impact. Well, that isn't the case anymore. Transducers will be in v5 – but their role has been greatly reduced over the past month.

I will go into Transducers in more detail in a later post, but the main reason why their role has reduced is because they didn't play nice with my attempt to bring higher-kinds into language-ext, whereas another technique exceeded my expectations – and so I'm pushing ahead with that.

Traits

Before we get on to higher-kinded types, we need to take a little aside into traits (aka type-classes).

A recent C# feature is static interface members – this opens up some new possibilities for bending C# to make trait like functionality work. You may have already seen the technique:

public interface Addable<SELF> where SELF : Addable<SELF>
{
    public static abstract SELF Add(SELF x, SELF y);
}

Note, how the Add member is static abstract and that the interface has a constraint that SELF is forced to inherit Addable<SELF>, meaning this trait can't stand alone (i.e. be ad-hoc like in other languages).

We can then create two distinct types that inherit the Addable trait:

public record MyList<A>(A[] values) : 
    Addable<MyList<A>>
{
    public static MyList<A> Add(MyList<A> x, MyList<A> y) => 
        new (x.values.Append(y.values).ToArray());
}

public record MyString(string value) : 
    Addable<MyString>
{
    public static MyString Add(MyString x, MyString y) => 
        new (x.value + y.value);
}

They both inherit Addable and pass themselves as the argument to construct the concrete Addable implementation.

We can then create a function that adds anything – as long a the type is Addable:

A AddAnything<A>(A x, A y) where A : Addable<A> =>
    A.Add(x, y);

And now we can call AddAnything with either one of the list types we made:

var mx = new MyList<int>([1, 2, 3]);
var my = AddAnything(mx, mx);        // [1, 2, 3, 1, 2, 3]

var nx = new MyString("Hello");
var ny = AddAnything(nx, nx);        // "HelloHello"

You may think: "so what, we could create addable interfaces before?" – and you'd be right. But, the difference here is that the static members don't need an instance. So, now we can do this:

public interface Addable<SELF> where SELF : Addable<SELF>
{
    public static abstract SELF Empty { get; }
    public static abstract SELF Add(SELF x, SELF y);
}

We've added an Empty property that presumably returns the 'zero' value for for SELF.

Now we can extend our types:

public record MyList<A>(A[] values) : 
    Addable<MyList<A>>
{
    public static MyList<A> Empty { get; } = new ([]);
    
    public static MyList<A> Add(MyList<A> x, MyList<A> y) => 
        new (x.values.Append(y.values).ToArray());
}

public record MyString(string value) : 
    Addable<MyString>
{
    public static MyString Empty { get; } = new("");
    
    public static MyString Add(MyString x, MyString y) => 
        new (x.value + y.value);
}

With that we can write some more general functions that work with Addable values. First, we'll create FoldMap which iterates over a sequence of values, mapping them into Addable values, and then aggregating them as it goes using Add:

B FoldMap<A, B>(IEnumerable<A> xs, Func<A, B> f) where B : Addable<B>
{
    var r = B.Empty;
    foreach (var x in xs)
    {
        r = B.Add(r, f(x));
    }
    return r;
}

Once we have that we can write a general concatenation function:

A Concat<A>(IEnumerable<A> xs) where A : Addable<A> =>
    FoldMap(xs, x => x);

And so we've managed to generalise folding and concatenation (for completely distinct types) in a way that wasn't possible before in C# (other than with the ad-hoc polymorphism trick leveraged in language-ext v4, but let's ignore that for now as it's not particularly attractive as a technique) .

Another major improvement is the return types from the members are the concrete value and not a (potentially boxed) Addable<A> – which has been a classic problem of using interfaces in C#.

The eagle-eyed amongst you will recognise that the Addable structure is a Monoid. In fact a Semigroup does 'adding' (in reality any associative binary operation) and a Monoid inherits Semigroup and extends it with an identity element (Empty).

So, let's refactor Addable:

public interface Semigroup<A> 
    where A : Semigroup<A>
{
    public static abstract A operator+ (A x, A y);
}

public interface Monoid<A> : Semigroup<A>
    where A : Monoid<A>
{
    public static abstract A Empty { get; }
}
This is the first major change in language-ext v5. Semigroups and Monoids are now types that you must inherit to make something into a semigroup or monoidal. You can see the new implementations here and here.

The big problem here is that we can't make types, that we don't own, into semigroups and monoids. That is, we don't have ad-hoc polymorphism. And so, we can't make string monoidal, or integers, or any type that is not under our control.

However, we can use the technique I have already shown above, of wrapping up an existing type in a small container type that does have the traits we need. It necessitates a small conversion step at the point of monoidal-usage, but other than that, it's relatively painless, if not entirely elegant.

This decision is a major shift from the ad-hoc polymorphism approach of earlier versions of language-ext. I believe it's the pragmatic decision that leads to more elegant code. The slightly less elegant part is when using types that don't belong to you, but I feel the trade is the right one.

Monoids are relatively simple types, what about something more complex? Could we make Select from LINQ into something more concrete and not a hack in the compiler?

Let's try the same trait-like technique from before, let's call the trait Mappable for no apparent reason (some of you will know where I'm going with this!):

public interface Mappable<SELF>
    where SELF : Mappable<SELF>
{
    public static abstract SELF Select<A, B>(SELF list, Func<A, B> f);
}

If we try to implement this everything goes wrong. We can't get the X in the array and transform it into an A to give to the mapping function f:

public record MyList<X>(X[] values) : 
    Mappable<MyList<X>>
{
    public static MyList<X> Select<A, B>(MyList<X> list, Func<A, B> f) => 
        // Can't map an X to an A
}

What if we remove the A argument from Select and instead embed it in the trait:

public interface Mappable<SELF, A>
    where SELF : Mappable<SELF, A>
{
    public static abstract SELF Select<B>(SELF list, Func<A, B> f);
}

It gets us closer, but now the A is baked into the return type of Select:

public record MyList<A>(A[] values) : 
    Mappable<MyList<A>, A>
{
    public static MyList<A> Select<B>(MyList<A> list, Func<A, B> f) =>
        new(list.values.Select(f).ToArray()); 
}    // ^^^ MyList<B> doesn't type check

The problem now is that the A is baked into the trait, everything must work with A – so even the most basic mapping of values within a collection cannot be achieved with C#.

And the reason that this can't be done is because C# doesn't have higher-kinded types...

What are higher kinds?

Simply, higher-kinded types are types that are parameterised by other types. Option<int> is a lower-kinded type, because it is entirely concrete. Option<A> is a higher-kinded type, because it has a parameter A that can be used to construct a new type (like Option<int>, Option<string>, etc.)

If you think of types like functions, it's a function that takes one argument (a type) and returns a result (a type). These are the fundamentals of generics.

Obviously, we already have this capability in C#, so why am I trying so hard to get higher-kinds into C#? Well, it's the generalisation of the principle of parameterisation that is desired. That is, if we can make the A in Option<A> a parameter, why can't we make the Option part a parameter: F<A> ? This isn't allowed in C#. And, it's really needed!

It's not just that I want to add functors, applicatives, and monads to our ecosystem. The C# compiler itself is crying out for higher-kinds...

There are loads of 'magic functions' in the language: Select, SelectMany, Where, Join, GroupJoin, GetEnumerator, GetAwaiter, Add (on collections that implement IEnumerable), index initialisers [this], the new collection initialisers...

There are more of these magic functions, but I have forgotten them all – which highlights a major problem with this 'magic' approach – total lack of discoverability. The magic functions are all hacks by the C# language team to bring in higher-kinded – ad-hoc – traits into C# without doing the heavy-lifting of making it an actual feature that we can all use.

It seems each time the C# team needs higher-kinds – as evidenced by these magic functions – they just hack the compiler and leave the rest of us wanting. I find this really sad, because it's clear there's a need and they won't address it.

K<F, A>

This is the most important new type in language-ext v5. It may possibly turn out to be the most impactful type ever added to language-ext.

This is the entirety of its definition:

public interface K<F, A>;

Say what? How can a type, that has no members at all, be so important? Well, it allows:

  • For the removal of 300,000 lines of generated and hand-written code that tried to give the impression of generalised traits.
  • It allows users to write their own functors, applicatives, traversables, foldables, alternatives, monads, and monad-transformers that all gain default behaviours written for those traits.
  • Namely, it allows for higher-rank polymorphism – higher kinds.

That's enough for part 1. For the rest of this story, check out for part 2!

Don't you just hate it when there's a cliffhanger like that at the end of an episode? This isn't Twin Peaks or something, it's not like you're desperate to find out who killed Laura Palmer – you just want to know how to do higher-kinds in C# – This is how binges happen!

Subscribe

This site is an independent publication launched in February 2024 by Paul Louth. If you subscribe today, you'll get full access to the website as well as email newsletters about new content when it's available. Your subscription makes this site continue to exist. Thank you!

Fresh content, delivered

Stay up to date with new content sent straight to your inbox! No more worrying about whether you missed something because of a pesky algorithm or news feed.

Published by:

Paul Louth