Hardware, Software & Product Development | Sparx EngineeringHardware, Software & Product Development | Sparx EngineeringHardware, Software & Product Development | Sparx EngineeringHardware, Software & Product Development | Sparx Engineering
  • Home
  • Expertise
    • Software Engineering
    • Electrical Engineering
    • Chemical Products and Services
    • Biomedical Engineering
    • Mechanical Engineering
    • Production Management
    • Automation
    • Industrial Design
  • Blog
  • About Us
NextPrevious

An example of what higher-kinded types could make possible in C#

By dfohl | Software | 3 comments | 10 June, 2013 | 1

C# Programming LanguageIf 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.

.NET, C#, F#, haskell, linq, Programming
dfohl

dfohl

More posts by dfohl

Related Post

  • Routing in Nancy from F#

    By dfohl | 0 comment

    Nancy is my web framework of choice for .NET. It is free, lightweight, easy to use, and comes without all the bloat of the more common .NET frameworks. Nancy makes routing in C# simple. IfRead more

  • Higher-kinded fun in Haskell

    By dfohl | 0 comment

    In my previous post, I showed an example of where the lack of higher-kinded types in .NET (both C# and F#) induces the need for code repetition.  In this post I’ll show you how higher-kindedRead more

  • Reading line-by-line from a serial port (or other byte-oriented stream)

    By Ben Voigt | 9 comments

    With many .NET developers moving from the traditional (and broken) System.IO.Ports.SerialPort DataReceived event handling to either the correct and more efficient BaseStream.BeginRead / BaseStream.EndRead pair I promoted in my last post or the newer BaseStream.ReadAsyncRead more

  • If you *must* use .NET System.IO.Ports.SerialPort

    By Ben Voigt | 165 comments

    As an embedded developer who writes desktop software mostly for configuration of, and data download from, peripheral devices, I use serial data streams a lot.  Mostly USB virtual serial posts from FTDI, but also theRead more

  • Clojure: An improved workflow

    By dfohl | 0 comment

    Like many beginning Clojure programmers, I started off following Stuart Sierra’s “Reloaded” workflow guide. While it was a great starting point, there were a number of things that I wanted to change. If the projectRead more

3 comments

  • Avatar
    Greg Rosenbaum Reply September 23, 2013 at 8:57 am

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

  • Dax Fohl
    Dax Fohl Reply November 27, 2013 at 9:16 pm

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

  • Avatar
    Dzmitry.Lahoda Reply October 3, 2017 at 4:59 am

    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<?&gt.

Leave a Comment

Cancel reply

Your email address will not be published. Required fields are marked *

NextPrevious
  • Home
  • Expertise
  • Blog
  • About Us
Sparx Technologies, LLC. dba Sparx Engineering © 2009 - 2020 | All Rights Reserved
  • Home
  • Expertise
    • Software Engineering
    • Electrical Engineering
    • Chemical Products and Services
    • Biomedical Engineering
    • Mechanical Engineering
    • Production Management
    • Automation
    • Industrial Design
  • Blog
  • About Us
Hardware, Software & Product Development | Sparx Engineering