Higher Kinded Polymorphism / Generics on Generics

[diab0l]

tl;dr

Haskell has monads
Monads are like bacon
C# needs bacon

Introduction

I have a mad craving for higher kinded polymorphism in C#.
And I have no blog to call my own, so here's an essay on this stuff.

That's a fancy name with a lot of crazy type theory and papers behind it, but if you have an understanding of how generic types work in C#, the concept is not terribly hard to understand.

What C# with a taste of bacon would look like

public static T<A> To<T, A>(this IEnumerable<A> xs)
    where T : <>, new(), ICollection<> 
{
    var ta = new T<A>();
    foreach(var x in xs) {
        ta.Add(x);
    }
    return ta;
}

...
{
    var data = Enumerable.Range(0, 20);

    var set = data.To<HashSet<>, int>(); // sorcery!
    var linkedList = data.To<LinkedList<>, int>();
    var list = data.To<List<>, int>();
}

What is going on here?

where T : <>,           // 1
          new(),        // 2
          ICollection<> // 3

1. T is constrained to be a generic type definition with one type parameter.
   • In CLR lingo: T is a generic type of arity 1
   • In type theory lingo: T is a type constructor of kind * -> *
2. Also it should have a default constructor
3. And it should implement ICollection<> (meaning for each type X, T<X> implements ICollection<X>)

Using this you could convert an IEnumerable<T> to any other type that is a collection.
Even all the ones you have never thought about, including the weird ones from libraries which do not get a whole lot of support because nobody uses them (except of course you).

Like HashSet (such a weird collection) or LinkedList (you would need to be crazy).
They are fine citizens of System.Collections.Generic and very useful, yet they don't get the love they deserve, because they are not as famous as List<> and implementing To...() methods in Linq for all of them would be a painful task.

However, with higher kinded polymorphism, they could all get a general concise implementation.

Where's the rest of that bacon?

That general conversion function is just the tip of the iceberg.
You can do all kinds of crazy transformations with higher kinded polymorphism.
And since it allows for such lovely abstractions you only have to implement them once.

Or better yet: Somebody else implements them in a NuGet package and you don't need to care.
Composition over coding.

Haskell? Is that a dog's name?

That NuGet package could be called something neat and concise like, say, Prelude. Yes, what a fine name!
There are some other party poopers, but the lack of Higher Kinded Polymorphism is the biggest road block in stealing all the juicy bacon from the Haskell community.

You know how Linq is awesome?
Do you also know how Linq is an implementation of the List Monad? (kind of)
Well, there are lots of more Monads in Prelude and most of them are awesome.
And currently a bitch to implement in C#.

Plus, HKP would allow to abstract on the concept of Monads!
And on concepts like Tuples (never heard of them), Functors (not what you're thinking), Arrows, Categories and all the crazy math that comes with them.

I've put together a gist of how wonderful this would be in combination with some other features for implementing Maybe.

I don't know what you're talking about, but it sounds expensive

Let's first look at a summary of the benefits that HKP would bring to C#

1. This feature would make C# the most relevant functional programming language with sub-typing and strong static type checking
2. A natural extension to the work done by the Linq team
3. A natural extension to generics
4. Much more natural porting of Haskell code (think about it: years upon years of research on bacon finally in a consumable form)
5. A real implementation of the Maybe monad (about time)
6. More expressiveness without sacrificing static typing
7. HKPs allow something kind of Meta-programming without the nonsense. Whoever used C++ before knows how easily template programming becomes a nightmare. On the other hand, Haskell programmers are delighted by their juicy type system.
8. Have I mentioned bacon?

Now let's talk about work:

• Before anything else, a proper implementation would require CLR support
  • That would be quite involved, but not impossible. Also I believe it can be implemented as a strict extension to the current metadata without breaking existing libraries
  • As a consequence, the F# crowd would benefit from this. I bet they are overjoyed to hear about bacon
  • As another consequence, implementing Haskell on top of .Net would be much less of a pain
• C# Syntax
  • In C# we can already refer to generic type definitions in typeof() as in typeof(IDictionary<,>)
  • I think the where T : <,> clause seems neat, but is probably not powerful enough (no way to constrain variance on T's parameters or 'swap' parameters for implementations)
    • maybe more like where T<,> : <U, X>, IDictionary<X, U>
    • or rather void Foo<A<B, C>, D>() where A<B, C> : IDictionary<C, B> where B : class
  • Well, the syntax needs work.
• Type checking
  • it's not work if it's fun

But I'm a vegetarian

Think of Bacon as an abstract higher kinded type class with non-carnivorous implementations

[VSadov]

There is an obvious issue with CLR not supporting higher-kinded types.
Some languages (Scala, F*) seem to be able to get around such limitations of underlying runtimes, but I do not know how well that works in practice.

@MadsTorgersen if not already there, higher kinded generics may need to be added to the list of possible future directions. Perhaps next to the Meta-programming :-).

[diab0l]

From what I've seen on UserVoice and SO, there's encodings to do this stuff in F# using their inlining system.

But these encodings tend to be ugly, complex and compromising.
That definitely doesn't sound like something I want for C#.

It's also worth noting that the feature request has been rejected for F#, since it would require CLR support, it's costs outweigh it's benefits, etc., however that was before Core was open sourced and all this crazy open development started

[GSPP]

@diab0l can you give more examples for what this would be good for? I always wondered what practical things you can do with higher kinded types.

For C# 6 they are not going to touch the CLR but there are other potential changes queued up (e.g. structural types and default implementations for interface methods). Maybe C# 7 can batch all of them into a new incompatible runtime.

[isaacabraham]

@diab0l I don't think it's been rejected from F# because of lack of CLR support - I believe it could be done in a type erased style - it's simply not high up enough the feature list on uservoice.

I've also been hearing people in the F# community asking for GADTs first.

[diab0l]

@isaacabraham Of course it could be implemented type-erased style, but that's an unpleasant can of worms.

If it were implemented like C++ templates, it would be a source level feature, meaning you can't have higher kinded polymorphic methods in assemblies. I think we can reach consensus that such a feature would only pollute the language.

If it were implemented like Java generics, it would lead to all sorts of nonsense. For example you couldn't do typeof(M<>) inside the hkpm, since the type has been erased.

So to implement this feature in a reusable way, there would at least need to be a way for the C# compiler to

1. actually compile the hkpm to an assembly
2. encode the extra information about the type (via an attribute perhaps)
3. decode that extra information so the method from the assembly can actually be used
4. use some very clever IL hacks to make it "just work" for the implementing method and at the call site

Now since it has to happen at assembly level, that would essentially be a language-agnostic extension to the CLR's common type system.
And since the extra information would need to be encoded, it wouldn't be type erased at all, it would be reified, albeit in an ugly hack.

If we are going to extend the CLR's common type system with some cool feature anyway, then I would suggest we do it right: by adding it as a first-level feature to the standard and implementing it right instead of via (clever or not) ugly hacks.

[diab0l]

@GSPP To be frank: I can't give you a whole lot of examples.
Until recently I just haven't given it any thought.

However, what I can tell you is that, as an abstraction feature which abstracts over abstract data structures it would primarily allow us to write some neat libraries.
Also, in Haskell it's used quite natural as part of every day programming for everything, so it allows for a different style in coding.

The best example I can currently come up with is abstracting over the Linq Zoo.
Consider you write a function which only relies on the shared semantics of Linq-to-Objects (IEnumerable<>), Database Linq (IQueryable<>), PLinq (IParallelEnumerable<>), Reactive extensions (IObservable<>), wherever IQobservable<> lives and whichever other crazy Linq-style APIs everybody whips up.

The only difference in the shared methods of these APIs (Select(), First(), ...) is
a) the data type they operate on (IEnumerable<>, IQueryable<>, ...) and
b) whether they straight up take Func<> or Expression<Func<>> as arguments.

We cannot currently abstract over a) or b) :(

Currently, as a library author who intends to write a method which works on either of these APIs, you would have to write your function each time for each API (without casting to IEnumerable<> which forces a query to lose it's semantics, for example), even if your function does not care whether it queries an IEnumerable<> or an IParallelEnumerable<> or even an IQueryable<>.

With the introduction of HKPMs, and a retrofitted static interface ILinq<> for Linq implementations, you could write your awesome function once and it would work not only on these 5 Linq implementations, but on every future implementation as well.

[diab0l]

Please do not understand me wrong.
I am well aware that implementing this feature is going to be a big undertaking and not going to happen anytime soon, if at all.
At least not until the CLR ports have become stable and established.

Also, it's not clear whether higher kinded polymorphism would be a good fit for C#.
Maybe there's some better way to raise the bar on abstraction.

What I think is clear is that C# and the CLR have incorporated features from functional languages with great success and the trend for using C# as a functional language is strong.

Having all this in mind, I think it's worthwhile to explore how C# would benefit from first-level support for Higher Kinded Polymorphism and what such a syntax would be like.

Also I think that, along with related issues it raises the question: Should the common type system as a one-size-fits-all solution be all that common?

[dzmitry-lahoda]

There is the example for HKT in C# http://www.sparxeng.com/blog/software/an-example-of-what-higher-kinded-types-could-make-possible-in-c.

[MI3Guy]

Another advantage would be the ability to use value type collections (e.g. ImmutableArray) without boxing them or writing a method that uses that specific collection.

[DrPizza]

Also, it's not clear whether higher kinded polymorphism would be a good fit for C#.

Template template parameters are a good fit for C++, so it's natural enough that generic generic parameters would be a good fit for C#. Being able to make Linq methods independent of concrete classes seems nice enough.

[gafter]

@TonyValenti Please suggest that in a new issue.