If you’re like me, you spend a lot of time in Visual Studio cranking away at C# code. You follow the updates to the language with each release, learn the new things that are possible and how it can make your life easier. But you also investigate other languages in your free time and see what features other languages have that you may be missing out on. If you’re especially into the functional aspects of C#, and you look at Haskell or Scala in your free time, you may have seen the term “Higher-Kinded Types”. You may have read a definition or two, looked at a couple papers, maybe-kinda understood it, but not really seen how it applies to real-world problems.
That’s the situation I was in for a while, interested in the concept of higher-kinded types, kinda-maybe understanding them, but not really seeing any ways I’d even use such a feature in a language. Until such a need occurred.
If you’re familiar with Haskell you’re certainly familiar with the term monad. And if you’re also a C# worker, you most definitely know the epitome of C# monads–LINQ[1]. If you’re in both of those camps, likely you also know the big #2 monad in C#, Erik Meijer’s Reactive Extensions (Rx). If so, great; if not, just know that Rx is like LINQ-for-events, where you can write select clauses and where clauses and etc, and it all combines to give you a new event (IObservable), just like LINQ does for IEnumerable.
So now, with that background, say you have the following task. You’ve got a Person class, with ID and Name, and you’ve got a Purchase class with PersonId and ItemName. Now, say you have two lists, people and purchases, and you need to design a LINQ query that creates a bunch of log entries of the form “PersonName purchased a ItemName”. Easy, right[2]?
|
1 2 3 4 5 6 7 8 9 |
static IEnumerable<string> GetPurchaseLogs( IEnumerable<Person> people, IEnumerable<Purchase> purchases) { return from person in people from purchase in purchases where person.Id == purchase.PurchaserId select person.Name + " purchased " + purchase.ItemName; } |
Great. Now say you have a new “streaming” feature, where “people” and “purchases” are now IObservable streams, and you want to use Rx to create a *stream* of log strings. What would that look like? Well you think about it, and decide that’s not so hard either:
|
1 2 3 4 5 6 7 8 9 |
static IObservable<string> GetPurchaseLogs( IObservable<Person> people, IObservable<Purchase> purchases) { return from person in people from purchase in purchases where person.Id == purchase.PurchaserId select person.Name + " purchased " + purchase.ItemName; } |
But wait. Doesn’t that look oddly familiar? Why yes, it’s the exact same code that went into your LINQ query! So in accordance with the DRY principle, we don’t want to repeat logic anywhere, so we look for a way to combine these two pieces of code into one. And we look. And we look. And we look. And it turns out there’s no way to do this[3]. We have to write this query out twice, once for the LINQ case, and once for the Rx case, because C# (and F# and .NET in general) has no support for higher-kinded types.
Higher-kinded types are essentially a way to “invert” the generic parameter. With higher-kinded types, you could essentially write your function like this:
|
1 2 3 4 5 6 7 8 9 10 |
static T<string> GetPurchaseLogs( T<Person> people, T<Purchase> purchases) where T<?> : LINQable<?> { return from person in people from purchase in purchases where person.Id == purchase.PurchaserId select person.Name + " purchased " + purchase.ItemName; } |
This would allow your function to work with any “kind” that supports the LINQable “typeclass”.
Unfortunately this post does not have a happy ending. Other than some hacks mentioned in the footnote, there is no general solution for eliminating this logic repetition in .NET. So until the CLR team implements higher-kinded types on the CLR, we’re stuck with code repetition. In my next post I’ll give an example of how the situation is different in Haskell.
[1] In reality, LINQ (and Rx) is not merely a Monad, but rather a MonadPlus. MonadPlus is a monad with support for guards (a.k.a. filtering, or where-clauses).
[2] Join syntax may be more efficient here in a real app. I use a where clause however to elucidate the similarities.
[3] In this specific case you could hack a solution with ToEnumerable and ToObservable, but these only work on a case-by-case basis, and not as a general solution.
I’ve stumbled upon this interesting post, and I’d just like to point out that very few things actually need to be implemented in the VM layer. Scala runs on the JVM, which implements a very poor type system on its own (much poorer than the CLR). It doesn’t support type parameters of any kind, let alone type constructors. The amazing richness in the Scala type system is accomplished using compile-time checking only, and a lot of code transformations. The virtual machine is completely oblivious to it.
In fact, Microsoft Research is currently working on a .NET language which does support higher-kinded types, as well as dependent types and other things. The language is called F*, and it is currently in (working) alpha. It’s a bit unclear whether Micorosft intends this to be a practical language, but hopefuly at least some aspects of the advanced type system will trickle down to C#.
@Greg Yes it’s a counter-intuitive bit of luck that the less-rich JVM type system allows for Scala’s richness. Since it doesn’t keep type parameters anyway, Scala could do its own thing and not worry about how to interop.
Since the CLR keeps track of type parameters, that means F# had to choose between solid interop with other CLR languages or doing it better but losing some of the seamlessness of the interop.
Possible real case for this is next.
1. We have vehicle which drives for a long time with black box storage. It obtains several gigabytes of data from sensor. This data downloaded later and queried using LINQ and plotted.
2. We attach our application client to the car while driving and see real time data plots out of events.
We could reuse some query logic with higher kinded types.
Note:
Seems C# viewer plugin is broken as it shows
LINQable<?>.