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

In part 1 of this series I introduced the type K<F, A> and left you all hanging with the promise that it would bring higher kinds to C#. So, let's dig in a little to see how it works.

Just a quick reminder that this series is previewing some of the big changes that are coming in the next version of language-ext. It's not yet available! There's probably about a month to go until the v5-beta – hopefully that's enough time for me to cover everything!

Firstly, you'll recall (from part 1) that we couldn't implement Mappable – using the traits technique – because it baked-in the bound-value type A and didn't allow us to map to a new bound-value type of B.

So, it should be clear that a type like List<A> can't ever inherit a trait that bakes in the A [if it wants to implement an generic version of Select]– we need a Mappable trait that has no A.

Let's try that:

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

But, we already know we can't use: F<A> and F<B> – where F would be List and A and B would be the type of the items in the list. Why? Because C# doesn't support higher kinds!

What we can do though is use the new magic type: K<F, A>:

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

This allows us to use F as an 'anchor' for an another type that will help us understand something about the structure of the 'mappable thing'.

If you haven't worked it out yet – K is short for Kind. I wanted to keep the type concise because it's needed a lot and I want the focus to be on the generic parameters, not the type-name. You'll see why this is important when we start filling in the generic parameters with concrete types.

First, let's create a simple list type:

public record List<A>(A[] Items) : K<List, A>;

Notice, how it inherits: K<List, A> – but we don't have a type called List, just List<A>. List is the type that will implement the Mappable<F> trait – let's start to make it:

public class List : Mappable<List>
{
    public static K<List, B> Select<A, B>(K<List, A> list, Func<A, B> f)
    {
        throw new NotImplementedException();
    }
}

OK, that's looking very interesting! We have a K<List, A> that maps to a K<List, B>. If you look back at the implementation of List<A> you'll see that it inherits a K<List, A> – so we can downcast a K<List, A> knowing it's a List<A>:

public class List : Mappable<List>
{
    public static K<List, B> Select<A, B>(K<List, A> list, Func<A, B> f) =>
        new List<B>(((List<A>)list)
                        .Items
                        .Select(f)
                        .ToArray());
}

And that works! We have a general case Mappable implementation for List<A>.

The casting is a little ugly though, so let's add a simple extension method to do the downcast:

public static class ListExtensions
{
    public static List<A> As<A>(this K<List, A> ma) =>
        (List<A>)ma;
}

Now, we can remove the cast from the implementation:

public class List : Mappable<List>
{
    public static K<List, B> Select<A, B>(K<List, A> list, Func<A, B> f) =>
        new List<B>(list.As().Items.Select(f).ToArray());
}

And everything starts to look really elegant.

Seasoned developers might wince at the down-casting, but we should only ever derive one type from K<List, A> – so it must be a List<A>. Obviously, if you did something silly and derived two types from K<List, A> then you'd get a failure on first usage, so it's not really a systemic risk to your code if you make a mistake. I'm OK with this.

We can then take that further, by creating the – one and only – Select extension method. Yes, you only need to write this extension once!

public static class MappableExtensions
{
    public static K<F, B> Select<F, A, B>(this K<F, A> fa, Func<A, B> f)
        where F : Mappable<F> =>
        F.Select(fa, f);
}

And, that's it – the extension method to end all extension methods. We can now use that like any other LINQ extension. And it will work for all types that implement Mappable:

var list = new List<int>([1, 2, 3]);

var nlist = list.Select(x => x + 1)
                .Select(x => x * 2);

As long as your data-type inherits K<F, A> and you have a sibling type that implements Mappable<F> then you will automatically gain the Select LINQ operator.

K<F, A> creates the hook to a higher-kinded type: F that allows us to parameterise with any type we want in place of A.

Now the downside. In the last example, Select returns a K<List, int> - not a List<int>. So, whilst we're able to chain many Select calls together, we can't assign the result directly to List<int>. But, we can use our downcast method to do that!

List<int> nlist = list.Select(x => x + 1)
                      .Select(x => x * 2)
                      .As();

This isn't ideal, of course, but it has a tiny overhead – it's just casting after all – and it's not too intrusive. The only way to avoid this is for the C# team to add higher-kinds proper (or allow implicit casting of interfaces – that's another discussion!); but for now this works and gives us all of the same benefits.

One thing I've noticed, as I build out this capability in language-ext, is how little I am needing to call .As() – because if you stay in the 'abstract state' then you can continue to rely on the higher-kinded extensions to 'just work'. It's only when you need to go back to a concrete value that .As() is needed.

Let's try implementing another Mappable type:

public abstract record Maybe<A> : K<Maybe, A>;
public record Just<A>(A Value) : Maybe<A>;
public record Nothing<A>() : Maybe<A>;

Here we create a simple discriminated-union type called Maybe<A> that has two states: Just and Nothing.

It's the same as Option<A> in language-ext, I just wanted to keep the example separate for now. Just is Some and Nothing is None.

Now, let's create the trait-implementing Maybe type:

public class Maybe : Mappable<Maybe>
{
    public static K<Maybe, B> Select<A, B>(K<Maybe, A> list, Func<A, B> f) =>
        list.As() switch
        {
            Just<A> (var x) => new Just<B>(f(x)),
            Nothing<A>      => new Nothing<B>()
        };
}

And add the downcast extension:

public static class MaybeExtensions
{
    public static Maybe<A> As<A>(this K<Maybe, A> ma) =>
        (Maybe<A>)ma;
}

Now we can leverage the – already existing – Select extension method:

var mx = new Just<int>(100);
var my = new Nothing<int>();

var r1 = mx.Select(x => x + 1)
           .Select(x => x * 3); // Just(303)

var r2 = my.Select(x => x + 1)
           .Select(x => x * 3); // Nothing

You may think "So what? We could do this with extension methods and only have to write 1 method for each type." – what we couldn't do is write generic functions that work with any Mappable type; we'd have to implement Foo(Maybe<string> mx), Foo(List<string> mx), etc.

Now we can write those functions once:

public static K<F, int> Foo<F>(K<F, string> ma) 
    where F : Mappable<F> =>
    ma.Select(x => x.Length);

Those of you that have been paying attention will notice that Mappable<F> is, of course, a Functor<F>! Yes, I realise this was hardly the reveal of the century, but for those of you who are relatively new to functional programming, terms like Functor might be a bit too much to take in whilst learning about a new technique for higher kinds! Now when you hear "Functor" just think "Mappable".

Anyway, Mappable is Functor and Select should be called Map. Let's do that:

public interface Functor<F> 
    where F : Functor<F>
{
    public static abstract K<F, B> Map<A, B>(K<F, A> fa, Func<A, B> f);
}

If we put our definition of Functor side-by-side with the Haskell definition of Functor – because Haskell is a language that has higher-kinds, traits, and probably has done more to promote this style of abstract programming than any other language...

class Functor f where
  fmap :: (a -> b) -> f a -> f b

You might notice a striking similarity!

• Functor f == Functor<F>
• f a == K<F, A>
• f b == K<F, B>
• (a -> b) == Func<A, B>

They're not just strikingly similar – but, barring the order of the arguments, they're exactly the same!

In the final version in language-ext, even the order of the arguments is the same. I will go into the reasons for that in a later article.

OK, so it's worth stopping to reflect right now – is this really higher-rank polymorphism? My answer to that is "100% yes!". Are there some compromises? Yeah, some, but they're pretty mild for what we gain.

It's also worth remembering that our original data-types haven't been modified at all.

// List<A>
public record List<A>(A[] Items) : K<List, A>;

// Maybe<A>
public abstract record Maybe<A> : K<Maybe, A>;
public record Just<A>(A Value) : Maybe<A>;
public record Nothing<A>() : Maybe<A>;

All of the 'action' is in the trait implementation types: List and Maybe. This is very similar to how class-instances work in Haskell (class instances are implementations of type-classes – i.e. traits). You create a data-type that represents the 'shape' and the trait-implementations represent the 'capability' – this is a nice separation of concerns and leaves the data-type being a pure structure that can travel anywhere.

The primary difference for us, in C#, is the need for the data type to derive from K<F, A> – this is unavoidable, brings some limitations, but still allows us to build very powerful generic code. One way to mentally process this (especially if you've never spent time in a language with higher-kinds) is imagine C# without generics – those of you who have been programming C# from v1.0 won't find that very hard to imagine! – could you imagine having a type-less List that only took object? Could you imagine the code explosion as you need to write 100 functions (all doing basically the same thing) for different types? Well, when you step up another rank with your generics, you gain a similar leap in power.

A perfect example is the implementations of Traverse and Sequence in language-ext v4 – I have written over 400 functions and over 1200 unit-tests by hand (actually, I got some help from the community – thank you, community!), that all do the same thing, but with different types. And guess what, if you decide to write a type that should be traversable – it won't work with any of the language-ext traversables or applicatives, you'd have to write n variants of traverse yourself. All because we can't write this type: T<F<A>> – where the T is Traversable and F is an Applicative.

In v5 I can write: K<T, K<F, A>> which allows for a single implementation of Traverse per type written (i.e. you implement your Traversable trait, once, like with Functor). And, if you decide to write a traversable or applicative type, it will automatically work with the traversable and applicative types in language-ext: you're not just limited to what I can provide [in the library] any more. True extensibility.

But that's for a later, we need to build up to that! I think that's enough for part 2. It's worth trying to digest the implications of this approach before moving on. Obviously Functor is a rather trivial type – so it may appear that we don't get a lot from this, but you'll quickly see how this technique gives us functional programming super powers!

In Part 3 we look at foldables!