# 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 itmustbe 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!*

### 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.