Higher Kinded Polymorphism / Generics on Generics

[gafter]

@diab0l commented on Thu Apr 23 2015

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 commented on Thu Apr 23 2015

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 commented on Fri Apr 24 2015

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 commented on Wed Apr 29 2015

@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 commented on Sat May 02 2015

@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 commented on Sun May 03 2015

@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 commented on Sun May 03 2015

@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 commented on Sun May 03 2015

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?

---

@asd-and-Rizzo commented on Mon May 04 2015

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 commented on Mon May 11 2015

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

---

@DrPizza commented on Mon Jun 20 2016

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 commented on Fri Sep 04 2015

@TonyValenti Please suggest that in a new issue.

---

@aluanhaddad commented on Wed Sep 16 2015

I would love to see this addition if some future version of the framework enables it.

---

@oscarvarto commented on Mon Jun 20 2016

+1 I am also craving for some bacon!

---

@mooman219 commented on Thu Jun 23 2016

+1 Ran into an issue where I needed this today

---

@aluanhaddad commented on Thu Jun 23 2016

It's too bad this is one of those things that definitely is going to require CLR support. But then again maybe it's a good opportunity for the CLR to evolve.

---

@Pauan commented on Fri Sep 23 2016

Please excuse the F#, but here is an example of where higher-kinded polymorphism would help out a lot.

There is a function called map which is used quite a lot in F#:

List.map : ('a -> 'b) -> list<'a> -> list<'b>
Array.map : ('a -> 'b) -> array<'a> -> array<'b>
Seq.map : ('a -> 'b) -> seq<'a> -> seq<'b>
Option.map : ('a -> 'b) -> option<'a> -> option<'b>
Event.map : ('a -> 'b) -> Event<'a> -> Event<'b>
Async.map : ('a -> 'b) -> Async<'a> -> Async<'b>

Its behavior is fairly simple. It allows you to take a "container" (like a list, array, dictionary, etc.) and transform every element inside of the container:

List.map (fun x -> x + 10) [1; 2; 3; 4]

The end result of the above code is [11; 12; 13; 14]. In other words, for every element in the list, we added 10 to it.

As you can see, map is used for many different types. It would be nice to be able to write functions that can work on any type as long as that type has a map function.

Because F# has interfaces (just like C#), you might try this:

type IMap<'T> = interface
  abstract member Map: ('a -> 'b) -> 'T<'a> -> 'T<'b>
end

// This is just for convenience: it is easier to use and auto-casts to the IMap interface
let map fn (a : IMap<'T>) =
  a.Map(fn, a)

And then you could implement the IMap interface on any class or discriminated union:

type Option<'a> =
  | None
  | Some of 'a

  interface IMap<Option> with
    member this.Map(fn, a) =
      match a with
      | None -> None
      | Some a -> Some (fn a)

You can then use the map function on anything which implements the IMap interface. And you can write generic code which uses the map function:

let mapadd a b =
  map (fun x -> x + b) a

// Examples of using it:
mapadd (Some 1) 5   // the end result is (Some 6)
mapadd [1; 2; 3] 5  // the end result is [6; 7; 8]

The mapadd function will work on any type which implements IMap. This is marvelous: without interfaces, we would need to write the mapadd function multiple times: once per type. In other words, we would need List.mapadd, Array.mapadd, Option.mapadd, Async.mapadd, etc.

But with interfaces, we can write it once and reuse it for many types! And of course static typing is fully preserved: you get a compile-time error if you make any mistakes, such as calling mapadd on a type which does not implement IMap.

The mapadd function is very simple, but this also works with more complex functions: you can write a complex function which works with anything which implements IMap, rather than needing to copy-paste the complex code for each type.

Unfortunately, this does not work, because .NET lacks higher-kinded polymorphism:

error FS0712: Type parameter cannot be used as type constructor

In other words, you cannot specify the type 'T<'a> where 'T is a type parameter (like in the IMap interface).

This also applies to other functions as well, like bind, filter, flatten, fold, iter, etc.

Quite a lot of the list and array functions would benefit from this. In fact, any "container" (list, seq, Async, Option, etc.) can benefit a lot from higher-kinded polymorphism. Of course there's plenty of other examples where this is useful (monads, arrows, etc.) but those examples tend to be familiar only to functional programmers.

Unfortunately I do not know C# well enough to give any examples of where higher-ordered polymorphism would be useful in C#, but I hope that map is familiar enough that C# programmers can see how this would be useful.

So, in short: higher-kinded polymorphism is simply a more powerful form of generics. It is useful for precisely the same reason why generics and interfaces are useful: it allows us to write code which can be reused, rather than reimplemented over and over again.

P.S. If somebody with more C# experience than me could translate the above F# code into equivalent C# code, that may help others with understanding what higher-kinded polymorphism is, how to use it, and what it's good for.

---

@orthoxerox commented on Fri Sep 23 2016

This repo demonstrates a quite interesting approach to typeclasses in c#: https://github.com/CaptainHayashi/roslyn

---

@Alxandr commented on Tue Sep 27 2016

Actually, both C# and F# has higher kinded polymorphism to an extent. It's what allows computational expressions in F#, and LINQ in C# to work. For instance, when you in C# do

for item in list
select item + 2

this gets converted into something like

list.Select(item => item + 2)

or in F#

List.map (fun item -> item + 2) list

This is done through some compile-time constraints that we are unfortunately unable to extend within the language. Basically what we're asking for is the ability to create interfaces like this:

interface ILinqable<TSelf<..>> {
  TSelf<T1> Select(Func<T1, T2> func);
}

class List<T> : ILinqable<List<..>> {
  // need to implement select
}

---

@orthoxerox commented on Tue Sep 27 2016

@Alxandr not really, LINQ query expressions are a purely syntactic convention.

---

@aluanhaddad commented on Tue Sep 27 2016

@orthoxerox yes they are but the result is higher kinded typing for a very limited subset of operations. Consider:

static class EnumerableExtensions
{
    public static List<R> Select<T, R>(this List<T> list, Func<T, R> selector) => 
        list.asEnumerable().Select(f).ToList();

    public static List<T> Where<T>(this List<T> list, Func<T, bool> predicate) =>
        list.asEnumerable().Where(predicate).ToList();

    public static HashSet<R> Select<T, R>(this HashSet<T> set, Func<T, R> selector) => 
        new HashSet<R>(set.asEnumerable().Select(f));

    public static HashSet<T> Where<T>(this HashSet<T> set, Func<T, bool> predicate) =>
        new HashSet<T>(set.asEnumerable().Select(f));
}

var numbers = new List<int> { 0, 1, 2, 3, 4 };

List<string> values = 
    from n in numbers
    where n % 2 == 0
    select $"{n} squared is {n * n}";

var distinctNumbers = new HashSet<int> { 0, 1, 2, 3, 4 };

HashSet<int> distinctSquares = 
    from n in distinctNumbers
    select n * n;

---

@aluanhaddad commented on Tue Sep 27 2016

The problem is that it has to implemented for every collection type in order to be transparent. In Scala operations like map and filter take an implicit parameter which is used as a factory to create new collections choosing the correct collection type based on the source.

---

@OzieGamma commented on Tue Sep 27 2016

@aluanhaddad

Indeed overloading lets you use functions as if it was higher-kinded polymorphism.

But you still have to write all those overloads. That's what we'd like to avoid.

---

@isaacabraham commented on Tue Sep 27 2016

This isn't even overloading. There is the ability to "hijack" the LINQ keywords if your types have method that have certain names and signatures - same as foreach really.

So in that way I suppose there's some similarity but in my limited understanding of HKTs, it's not the same - you don't have the reuse that they give you.

---

@aluanhaddad commented on Tue Sep 27 2016

I am not suggesting equivalence. I am suggesting that it is possible to slightly abstract over the type that is itself parameterized by using LINQ method patterns. I was not proposing this as an alternative to higher kinded types as it clearly is not. If Rx is not hijacking LINQ keywords, I hardly think this is, but it is certainly surprising and I would avoid this pattern.

---

@Pauan commented on Tue Sep 27 2016

@Alxandr It's true that LINQ/computation expressions allow you to use the same syntax on multiple different types, but it is a hardcoded syntax trick.

Here is an example in C# where LINQ will not help you:

http://www.sparxeng.com/blog/software/an-example-of-what-higher-kinded-types-could-make-possible-in-c

This is the reason why higher kinded types are useful. I know you're already aware of this, I'm mentioning this for the sake of other people who think that LINQ is "good enough".

---

It's also possible to hackily add in support for overloaded functions in F# by abusing inline functions and statically resolved type parameters:

https://github.com/gmpl/FsControl

This is essentially using the same trick that LINQ is using: any type which happens to implement a static method with the right name and right type will work.

But unlike interfaces:

• All of the functions need to be inline, including any functions which use inline functions (this can cause code bloat and long compilation times).
• The method names can collide (you can't define two different "interfaces" with the same method name).
• This trick only works in F#, it doesn't work in C#.

So we still need higher-kinded types.

---

@Alxandr commented on Wed Sep 28 2016

@Pauan I am very well aware of this. I just tried to make a really simple explanation explaining to people who do not know what we want. LINQ is as you said a hardcoded compiler trick. Inline in F# is a bit more of a flexible compiler trick. We would like the CLR to support higher kinded generics. Although, you could make higher-kinded a compiler-only feature it would be better if the CLR supports it.

---

@diab0l commented on Wed Sep 28 2016

I would like to add some more clarification, especially since what I originally wrote may not be clear enough for people unfamiliar with higher kinded types. So here's some theory. Somebody correct me if I'm wrong.

Proper Types Proper types are those inhabited by values which are not types themselves. Examples are int, bool, string and any other value (struct) or reference type (class). Generic types closed over all their type arguments (such as List<int> or KeyValuePair<string, int>) are also proper types.

Kinds Kinds are a formalization for type-level functions. There's * which reads as type, which is no coincidence, because all proper types are of kind *. There's also the operator -> which allows us to create kinds like * -> * which is a type function taking a proper type as parameter and returning a proper type as result. (Examples: List<> and Set<>)

Such type functions are also called type constructors, since you give them some parameters and they 'construct' a type for you. In other words, applying the proper type int to the type constructor List<> yields the proper type List<int>.

Generic types So, * -> * is the kind of generic types with arity 1 (List<>, Set<>, etc.), * -> * -> * is the kind of generic types with arity 2 (Tuple<,>, KeyValuePair<,>, Dictionary<,>). and so on. These are things we can already express within C# and the CLR and we call them generic types.

To slightly complicate the picture, we also have generic methods which are in a sense function constructors. They are like type constructors, except they do not return a proper type, but instead a proper function.

Higher kinded types What we cannot express are higher-kinded types. An example would be (* -> *) -> * -> *, which is a type function taking a type constructor and a proper type as argument and returning a type. Here's what the signature could look like in C#:

T<U> Foo<T<>, U>();

Another useful kind would be (* -> *) -> (* -> *) which could be used to have a general mapping from one type constructor to another. To make this meaningful, we would need to know something about the types constructors and the way to do that would be constraints. We can currently neither have a type argument which is a type constructor itself and even if we could, we couldn't meaningfully constrain it.

There are other things we cannot express. For example you can't have a variable of type Action<> or of type Func<,>, so you can have generic methods, but not generic lambda methods.

Tl;dr; To sum it up, today we can range over the U in T<U>. What I want is to be able to range over the T in a meaningful way (with constraints).

---

@Alxandr commented on Wed Sep 28 2016

While I (think) I perfectly understood all of that (I've done haskell), I think the * -> * and (* -> *) -> * annotation is confusing for people who are not used to functional programming languages. I remember starting in F# and reading int -> int -> int is confusing if you're not used to it.

To translate the same into something akin to TypeScript (C# doesn't really have a func annotation) it could look something like this:

List: (T: *) => List<T>
Dictionary: (Key: *, Value: *) => Dictionary<Key, Value>

whereas what we would like to express is

Mappable: (T: (* => *)) => Mappable<T<>>

Not sure about the syntax, but I do believe we might want to try to write things in a format thats more similar to what most C# devs are used to (at least while we're in the roslyn repo).

Or if an interface would help:

interface IMappable<T<>, A> {
  T<B> Map<B>(Func<A, B> func);
}

class List<T> : IMappable<List<>, T> {
  List<B> IMappable.Map<B>(Func<A, B> func) {
    List<B> result = new List<B>(Count);
    int index = 0;
    foreach (T item in this) {
      result[index++] = func(item);
    }
  }
}

Syntax is obviously something that should be discussed, and I don't know what works best, but personally I think figuring out how things should work on the CLR level first is probably the best idea. Also, I haven't written C# in a while, so apologies if there are any glaring errors in my snippets :)

---

@diab0l commented on Thu Sep 29 2016

@Alxandr I do agree completely and gosh, I hope this stuff eventually makes it's way into typescript.

The interface is probably the best analogy. There are also proposals for 'static interfaces' which would allow for similar abstractions.

---

@toburger commented on Wed Oct 12 2016

it seems that there's a light at the end of the tunnel: https://www.youtube.com/watch?v=hK5GJoH4PlI

---

@gusty commented on Wed Oct 12 2016

@toburger That technique doesn't cover Higher Order Kinds. It allows you to define 'first-order-kind typeclasses' like Monoid and generalize over numeric types, but in order to be able to represent functors, applicatives or monads you still need to do something at the CLR level.

---

@Opiumtm commented on Wed Oct 12 2016

Your example is perfectly possible using current C# syntax

        public static T ConvertTo<T, TItem>(this IEnumerable<TItem> src)
            where T : ICollection<TItem>, new()
        {
            var result = new T();
            foreach (var item in src)
            {
                result.Add(item);
            }
            return result;
        }

        public static void Test()
        {
            var data = Enumerable.Range(1, 10);
            var list = data.ConvertTo<List<int>, int>();
            var set = data.ConvertTo<HashSet<int>, int>();
        }

---

@sideeffffect commented on Wed Oct 12 2016

if you haven't heard, there's this for HKT in F#

https://github.com/palladin/Higher

now I'm wondering, that this should also work in C# of course, this is more like a hack/workaround, but until we have a proper implementation of HKT in the language(s) and/or CLR, this could aleviate some problems

---

@Opiumtm commented on Wed Oct 12 2016

And from mentioned above article.

Example:

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;
}

Exact generic logic to example above:

static IEnumerable<TItem3> CombineCheck<TArg1, TArg2, TItem1, TItem2, TItem3>(TArg1 a, TArg2 b, Func<TItem1, TItem2, TItem3> combine, Func<TItem1, TItem2, bool> check)
    where TArg1 : IEnumerable<TItem1>
    where TArg2 : IEnumerable<TItem2>
{
    return from item1 in a
        from item2 in b
        where check(item1, item2)
        select combine(item1, item2);
}

So, T<?> seems to be just short-hand for existing type constraints that require to explicitly declare type arguments of TItem1, TItem2 item types and TArg1, TArg2 enumerables.

And LINQable<?> here isn't possible and not a case of higher-order polymorphism because LINQ queries use structural typing (LINQable is every type which provide standard Where(), Select() and so on methods - it isn't bound to exact interfaces, it use structural typing instead)

So, C# should officially support some forms of structural typing as it already support structural typing for awaitables and LINQ-ables and don't support general-purpose structural typing

---

@gabomgp commented on Thu Nov 10 2016

@Opiumtm I think structural typing is a very big change for C#, maybe something similar to traits/type classes/protocols would be better. Traits in Rust are very similiar to extension methods, but think in interfaces than extends the behavior instead of methods.

---

@asd-and-Rizzo commented on Thu Nov 17 2016

I am not sure, but seems case like next could also get use of HKT.

Given next usage of CsvHelper:

        /// <summary>
        /// Gets the csv string for the given models.
        /// </summary>
        /// <param name="models">The data models.</param>
        /// <returns>The csv string.</returns>
        [SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures", Justification = "OK")]
        public static string ToCsvString<TEntity, TMap>(IEnumerable<TEntity> models) where TMap : CsvClassMap<TEntity>
        {
            using (var content = new MemoryStream())
            {
                var textWriter = new StreamWriter(content, Encoding.UTF8);
                var config = new CsvConfiguration();
                config.RegisterClassMap<TMap>();
                var writer = new CsvWriter(textWriter, config);
                writer.WriteHeader<TEntity>();
                models.ForEach(writer.WriteRecord);
                textWriter.Flush();
                content.Position = 0;
                return new StreamReader(content).ReadToEnd();
            }
        }

And call:

ToCsvString<MyEnitty,MyMap>(...)

With HKT is seems would be next:

public static string ToCsvString<TMap<TEntity>>(IEnumerable<TEntity> models) where TMap : CsvClassMap<TEntity>

With HKT we will get less code to type when method is called - only 1 name of class, instead of 2:

ToCsvString<MyMap>(...)

And I do not understand Microsoft CodeAnalysis(CA) errors I see - may be will have no reason for these given HKT in place:

Severity    Code    Description Project File    Line    Suppression State
Error   CA1004  Consider a design where 'CsvBuilder.ToCsvString<TEntity, TMap>(IEnumerable<TEntity>)' doesn't require explicit type parameter 'TMap' in any call to it. CsvBuilder.cs   10  Active

Does CA suggest to make HKT into C# for proper design?

---

@bondsbw commented on Wed Dec 14 2016

The following DateTimeCollection type appears to satisfy the requirements for T in the original example:

public class DateTimeCollection<U> : ICollection<U>
    where U : DateTime

But DateTimeCollection has a type parameter constraint, so it would need to fail when that constraint is not satisfied:

var data = Enumerable.Range(0, 20);
var dtCollection = data.To<DateTimeCollection<>, int>();  // int does not inherit DateTime

The primary location of the problem is in the return type:

public static T<A> ... // Should be an error here, cannot construct 'T' with parameter 'A'

Because there is no guarantee that A is allowed as a parameter of T. So that should be specified in the type constraints for T:

public static T<A> To<T, A>(this IEnumerable<A> xs)
    where T : <A>, new(), ICollection<> 

---

@bondsbw commented on Wed Dec 14 2016

Perhaps the type constraint for ICollection<> needs to be specified as well:

public static T<A> To<T, A>(this IEnumerable<A> xs)
    where T : <A>, new(), ICollection<A> 

Otherwise wouldn't this line fail?

ta.Add(x);

---

@alexandru commented on Thu Feb 02 2017

@aluanhaddad OOP subtyping / overloading doesn't help with the most useful operation of all, which is bind / flatMap (I think it's called SelectMany in .NET) because in OOP you have co/contra-variance as a natural effect of subtyping + generics and function parameters are contra-variant, which means you'll lose type info.

In practice this means you can't describe such operations by means of inheritance (and please excuse the Scala syntax, I'm just a newbie in F#):

trait Monad[F[_]] {
  // ...
  def flatMap[A,B](source: F[A])(f: A => F[B]): F[B]
}

object FutureMonad extends Monad[Future] {
  def flatMap[A,B](source: Future[A])(f: A => Future[B]): Future[B] = ???
}

Well, in Scala you can describe flatMap with inheritance, but then you need another feature in the type-system, called F-bounded types. Scala can do that too, but this is another feature you don't see in other OOP languages, since this also needs higher-kinded types to be useful, (see article with details):

trait MonadLike[+A, Self[+T] <: MonadLike[T, Self]] { self: Self[A] =>
  def flatMap[B](f: A => Self[B]): Self[B]
}

class Future[+A] extends MonadLike[A,Future] {
  def flatMap[B](f: A => Future[B]): Future[B] = ???
}

Looks ugly but it is very useful for sharing implementation while not downgrading to the super-type in all those operations.

[Pzixel]

We also need better type inference because no one wants to specify all template parameters. And with current generic resolution we just should specify all paramters if only one is unknown for compiler. Thus, without this feature this request seems to be quite impractical.

[laicasaane]

@Pzixel I agree. I had suffered from specifying a bunch of type params every time I call complex generic methods. It's very unnatural since anyone would expect the compiler knows which types are needed because all information has been provided already.

The LDM really need to do something to surpass their fear of breaking changes or we won't have any wondrous thing in C# for eternity.

[Joe4evr]

It's very unnatural since anyone would expect the compiler knows which types are needed because all information has been provided already.

Except that's not at all true.

[Pzixel]

@Joe4evr do not mess types declaration with types usage. There is no problem in latter case.

[gafter]

I am championing it so that it is considered in conjunction with the cluster of features #110

[orthoxerox]

@gafter do you have an idea how to implement them on the current CLR, or are you willing to lobby for a CLR upgrade?

[gafter]

I'm assuming a CLR change would be required.

[vukovinski]

@gafter now I will try to completely derail you :) well not derail, but probably overload.

Sure, I would love typeclasses and HKP in .NET, and was investigating the limits of the C# type system against Haskell, Coq, Idris, F*, Zig and some others.

I have two recommendations to consider if the CLR is going to be touched for #110

1. Consider implementing a Propositions type/sort a la Coq that would rival the System.Object hierarchy. The members of this type/sort could only be constructed from traditional objects and would serve to prove properties about them (distinct for compile-time/run-time/dynamic properties).

Not only would this open a whole new area of program verification for .NET, but it could also be the base for a more powerful constraints system. Not sure, but I believe that dependent typing features would be possible if we had constructors which would inspect such Propositions and parameterize themselves accordingly (they'd be closed under all statically compiled Propositions).

For the developer, these would enrich the interactive development loop and debugging experience. For the compiler, these would allow for new kinds of speculative optimization via program extraction.

public class Nat
{
    // we hint to the proposition system, that these are static ctor's
    public static hint Nat O() => new Nat();
    public static hint Nat S(Nat pred) => new Nat(pred);

    private Nat() => Value = 0;
    private Nat(Nat pred) => unchecked(Value = pred.Value + 1);
    // new access level, only accessed by propositions
    provable Nat(int value) => Value = value;

    protected int Value { get; private set; }

    public Nat Add(Nat right)
    {
        switch (Nat_IsZero(this))
        { 
            case Holds:
                return right;
            default:
                Value += right.Value;
                return this;
        }
        // alternatively, when in Rome...
        Holds(Nat_IsZero(this)) return right;
        Value += right.Value; return this;
        //Holds is a proposition of all propositions
    }
}

public proposition Nat_IsZero(Nat x)
{    
    given x; when x.Value == 0;
}

public proposition Nat_IsSuccOf(Nat x, Nat y)
{
    // y is successor of x
    given x, y; when y.Value - x.Value == 1;
    // y is predecessor of x, linked proposition definition
    adjoint Nat_IsPredOf(Nat x, Nat y) when Holds(Nat_IsSuccOf(y, x));
}

public proposition Nat_AddZero_Idem(Nat x, Nat y)
{
    given x, y; when Holds(Nat_IsZero(y));
}

EDIT: Part two, with static propositions about implicit coercing conversions

// provides implicit conversion to Nat for any int
public static proposition Nat_Identity(Nat x, int y)
{
    given y;
    // speculatively tries constructing x by trying all the static constructors,
    // in this case, the hinted static method Nat.O() should produce the desired x
    exists x => Holds(Nat_IsZero(x));
    replacing y = x.Add(new Nat(y));
}

public static proposition EventId_Identity<T>(Nat next, T prev)
{
   given prev => Holds(Nat_Identity(prev));
   // here, the hinted static method Nat.S(Nat pred) expects an argument,
   // since only prev is given, we try only with prev, then
   // we check if it fits, by ensuring it is a successor of the given
   exists next => Holds(Nat_IsSuccOf(prev, next));
   replacing prev = new EventId(next);
} 

It'd be a task to fit these into the type theory of .NET, but I think it's just a stepping stone to HPK.

[HaloFour]

There's only one thing I don't like about these HKT proposals:

1. T is constrained to be a generic type definition with one type parameter.

I'm not sure I understand why HKTs would put such a limitation on T. Why must it be a generic type of any specific arity, or a generic type at all, as long as it meets the other requirements of being both instantiatable and implementing ICollection<?>? Wouldn't this prevent using non-generic concrete types that implement the generic collection interfaces? What if I had a container type class StringList : ICollection<string>?

Maybe I'm missing something obvious/functional here?

[gafter]

The generic code that uses the generic wants to instantiate it, and in order to do that it needs to provide the correct number of type parameters. So the number of type parameters needs to be statically known.

[diab0l]

@HaloFour In the sample, the constraint on the type constructor is supposed to read T can be used to construct types T<A> where A is any type. Without it, the compiler would not know that it is legal to use T as a type constructor. The compiler could possibly infer the constraint, but that's complicated and a seperate issue.

Edit Yes, it does prevent using non-generic types such as StringList : ICollection<string>. The premise of HKTs is to be able to range over either String, List or both to create new types. In StringList there is no obvious way to plug either String or List with a different type.

Tl;dr By limitting the generic parameters with constraints, you actually enable the code to do more with them. It is the same with higher kinded types.

There are two sides to the coin of Constraints.

As an illustrating example, consider a container-preserving variant of Enumerable.Select:

?? Select<TContainer, TX, TY>(?? xs, Func<TX, TY> f) {
  // ...
}

The usage should be along the lines of:

  {  // List
    var input = new List<string> { "a", "foo", "barbaz" };
    var expected = new List<int> { 1, 3, 6 };
    var actual = Select<List, string, int>(input, x => x.Length);
    // expected and actual should be equal
  }
  { // Stack
    var input = new Stack<double> { 0.5, 1.2, 2.3 };
    var expected = new Stack<int> { 1, 1, 2 };
    var actual = Select<Stack, double, int>(input, x => Math.round(x));
    // expected and actual should be equal
  }

Because TContainer is unconstrained, from the outside we can plug in any type. However, from inside the function there is not much we can do because statically we do not know how to pry xs apart or how to construct out output. We cannot even specify that xs should be of type TContainer<TX> or the return type should be TContainer<TY>, since the compiler has no guarantee that TContainer is a type-constructor. Remember that we can plug in any type for TContainer, even nonsense like int.

In a sense, from the outside, the constraints are limitations, but on the inside they are the opposite: they widen the range of operations because the compiler has more information about constrained types than unconstrained types.

Let's see that in action. If we add a constraint to tell the compiler that TContainer is a type-constructor..

?? Select<TContainer, TX, TY>(?? xs, Func<TX, TY> f) where TContainer: <> {
  // ...
}

..the compiler knows that it is legal to use TContainer as a type-constructor, so we can use it to construct our input and return types:

TContainer<TY> Select<TContainer, TX, TY>(TContainer<TInput> xs, Func<TX, TY> f) where TContainer: <> {
  // ...
}

We need some more constraints to actually implement the function and end up with something like

TContainer<TY> Select<TContainer, TX, TY>(TContainer<TInput> xs, Func<TX, TY> f) 
  where TContainer: <>, new(), IEnumerable<>, ICollection<> {

  var result = new TContainer<TY>(); // requires the constraint new()

  foreach (var x in xs) { // requires the constraint TContainer<A> : IEnumerable<A>
    var y = f(x);
    result.Add(y); // // requires the constraint TContainer<A> : ICollection<A> or similar
  }

  return result;
}

So we end up with 4 constraints. While they impose limitations on the types we can use with the function, they enable our critically important operations:

1. specify the types of input and output
2. allow us to take the input apart into bite-sized pieces
3. allow us to create a new container of the output type
4. allow us to puzzle together the transformed pieces

Sorry for the long post, but I hope it clears up any confusion about constraints. Also I hope it provides a motivating example.

[orthoxerox]

@HaloFour I agree, something like partially specialized types would be a welcome addition, although now we're probably venturing into the tail end of a Zipf's distribution of feature usefulness.

[TonyValenti]

This isn't quite the same as partially specified types, but this is something I've used in the past that gets me pretty close to what I need.

public class Class1 {

        public void Test() {
           //This is how you normally do things
            var StringInt1 = Relationship<String, int>.Create();
           //Create a default implementation (object, object)
            var Default = Relationship.Create();

           //Start with the default and then customize the type members.
            var StringInt2 = Relationship
                .WithParent<String>
                .WithChild<int>
                .Create()
                ;

        }

    }


    public class Relationship<TParent, TChild> {

        public static Relationship<TParent, TChild> Create() {
            return new Relationship<TParent, TChild>();
        }

        public class WithParent<TOther> : Relationship<TOther, TChild> {

        }

        public class WithChild<TOther> : Relationship<TParent, TOther> {

        }


    }

    public class Relationship : Relationship<object, object> {

    }

[masonwheeler]

Any new generic constraints should be implemented in the same place as the old generic constraints--the CLR type system--and not as a big hack inside the C# compiler. It's important to remember that CLR does not stand for "C# Language Runtime." If we add something as big as higher-kinded types, it should be added inside the CLR, to minimize the amount of work that the maintainers of other languages have to do in order to get up to speed on the new features.

This would likely require a new CLR major version and the addition of at least one new metadata table. Backwards compatibility would be trivial (if your assembly doesn't have the new table(s), just don't worry about it.) Forwards compatibility, not so much, but it would be worth the pain. The last time we added new metadata, we were able to deal with the compatibility break just fine, and it brought the CLR into a major leap forward. But after 12 years, the CLR 2.0 architecture is really starting to show its limitations. If we're going to do this, we should do it right, instead of even more piling of hacks upon hacks upon hacks.

[masaeedu]

This would be useful for being able to write typeclass instances corresponding to existing types in the base class library. For example dictionaries are traversable, and it's often handy to be able to pull a Dictionary<K, IEnumerable<V>> into a IEnumerable<Dictionary<K, V>>, or a Dictionary<K, Task<V>> into a Task<Dictionary<K, V>>.

Right now this can be accomplished with ad-hoc overloading of methods, but it requires a lot of useless boilerplate:

using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

namespace FPUtils
{
    using static EnumerableUtils;
    using static DictUtils;
    using static TaskUtils;
    using System;

    public static class TaskUtils
    {
        // Monad
        public static Task<A> Pure<A>(A a)
            => Task.FromResult(a);

        public static async Task<B> Bind<A, B>(this Task<A> a, Func<A, Task<B>> f)
            => await f(await a);

        public static Task<B> Map<A, B>(this Task<A> a, Func<A, B> f)
            => a.Bind(x => Pure(f(x)));

        public static Task<C> Lift2<A, B, C>(Func<A, B, C> f, Task<A> fa, Task<B> fb)
            => fa.Bind(a => fb.Map(b => f(a, b)));
        public static Task<B> Ap<A, B>(this Task<Func<A, B>> af, Task<A> av)
            => Lift2((f, v) => f(v), af, av);
    }

    public static class EnumerableUtils
    {
        // Misc
        public static bool HasDuplicatesBy<X, K>(Func<X, K> f, IEnumerable<X> a)
            => a.Map(f).Distinct().Count() != a.Count();

        // Monoid
        public static IEnumerable<A> Empty<A>()
            => new A[] { };
        public static IEnumerable<A> Append<A>(IEnumerable<A> a, IEnumerable<A> b)
            => a.Concat(b);

        // Monad
        public static IEnumerable<A> Pure<A>(A a)
            => new[] { a };

        public static IEnumerable<B> Bind<A, B>(this IEnumerable<A> a, Func<A, IEnumerable<B>> f)
            => a.SelectMany(f);

        public static IEnumerable<B> Map<A, B>(this IEnumerable<A> a, Func<A, B> f)
            => a.Select(f);

        public static IEnumerable<C> Lift2<A, B, C>(Func<A, B, C> f, IEnumerable<A> fa, IEnumerable<B> fb)
            => fa.Bind(a => fb.Map(b => f(a, b)));
        public static IEnumerable<B> Ap<A, B>(this IEnumerable<Func<A, B>> af, IEnumerable<A> av)
            => Lift2((f, v) => f(v), af, av);

        // Foldable
        public static B Fold<A, B>(this IEnumerable<A> xs, B z, Func<B, A, B> f)
            => xs.Aggregate(z, f);
    }

    public static class DictUtils
    {
        // Misc
        public static IReadOnlyDictionary<K, V> Insert<K, V>(K k, V v)
            => new Dictionary<K, V>() { [k] = v };

        // Monoid
        public static IReadOnlyDictionary<K, V> Empty<K, V>()
            => new Dictionary<K, V>();
        public static IReadOnlyDictionary<K, V> Append<K, V>(IReadOnlyDictionary<K, V> x, IReadOnlyDictionary<K, V> y)
            => x.Concat(y).ToDictionary(d => d.Key, d => d.Value);

        // Traversable
        public static IEnumerable<IReadOnlyDictionary<K, V>> Sequence<K, V>(IReadOnlyDictionary<K, IEnumerable<V>> dict)
            => dict.Keys
            .Map(k => dict[k].Map(v => Insert(k, v)))
            .Fold(EnumerableUtils.Pure(Empty<K, V>()), (e1, e2) => Lift2(Append, e1, e2));
        public static Task<IReadOnlyDictionary<K, V>> Sequence<K, V>(IReadOnlyDictionary<K, Task<V>> dict)
            => dict.Keys
            .Map(k => dict[k].Map(v => Insert(k, v)))
            .Fold(TaskUtils.Pure(Empty<K, V>()), (e1, e2) => Lift2(Append, e1, e2));
    }
}

The last two are especially egregious, because the only difference between them is s/IEnumerable/Task/. You can see that the value level implementation of most things is fairly simple, but the types expressions start blowing up. A system that allows us to abstract over higher kinded types and infer things better would be very helpful.

For example, in the code above it should be possible to write:

public static T<IRD<K, V>> Sequence<T, K, V>(IRD<K, T<V>> dict) where T : Applicative
    => dict.Keys
    .Map(k => dict[k].Map(v => Insert(k, v)))
    .Fold(T.Pure(Empty<K, V>()), (a, b) => T.Lift2(Append, a, b))

and have just one definition suffice for both enumerables and tasks (and in fact any other sort of applicative).

[travis-leith]

Can we get an update on this? Even if only an indication of when triage is likely to occur.

[gafter]

We've been doing triage as time permits. Hopefully we'll be able to triage again in a couple of weeks.

I expect this will be tagged "C# 9.0", because we have a proposed implementation for the runtime support and need to at least design the language feature enough to ensure we are OK with the runtime approach. Having said that, I'd give it a 30% chance to happen in C# 9.0.

[Frassle]

I'd give it a 30% chance to happen in C# 9.0.

Very exciting!

we have a proposed implementation for the runtime support

Is that my proposal from the coreclr issue, or is there something new?

[FWest98]

Just to mention another possible use case: This might also be useful in implementing the basic LINQ functions for the new async enumerables as well. Currently the team decided to skip the implementation of those, since it would add too many functions in the library and take too much time to properly maintain, but I would assume this makes it much easier and cleaner for those to be implemented.

I think it'd be very interesting to see features like these pop up in more "mainstream" languages like C#!

[gafter]

I would assume this makes it much easier and cleaner for those to be implemented

Can you please explain how?

[Pzixel]

I believe with functor/applicative/monad/monoid/... traits LINQ could be based on them so async enumerable just could reuse AsyncMonad + ListMonad composition.

[borseno]

how about this one? Yet it isn't "true" HKT, but I think it solves the problem in the example (meaning it's probably fine without HKT in C# or the example is not quite good to describe the problem) in a pretty concise way

public static T To<T, A>(this IEnumerable<A> xs)
        where T : ICollection<A>, new()
{
    var ta = new T();

    foreach (var x in xs)
    {
        ta.Add(x);
    }

    return ta;
}

public static void DoSmth()
{
    var data = Enumerable.Range(0, 20);

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

    foreach (var _ in _set.Take(1))
        Console.WriteLine("good");

    foreach (var _ in linkedList.Take(1))
        Console.WriteLine("good");

    foreach (var _ in list.Take(1))
        Console.WriteLine("good");
}

[Pzixel]

@borseno That's no sorcery. you specify HashSet<int> explicitly. Specifying types explicitly won't allow you do to the most amazing stuff. For example

public static T<int> CreateSomethingOfInts<T>() where T<> : new() => new T<int>();

Is not expressible.

[borseno]

@Pzixel thank you for this interesting example, this indeed explains the significance of HKT

[realvictorprm]

I hope C# gets this soon so F# gets this soon too :)

[realvictorprm]

Can't wait to make better monads in F# then :D

[Happypig375]

Oh no! Not the m-word!

[antagonist112358]

Any new generic constraints should be implemented in the same place as the old generic constraints--the CLR type system--and not as a big hack inside the C# compiler. It's important to remember that CLR does not stand for "C# Language Runtime." If we add something as big as higher-kinded types, it should be added inside the CLR, to minimize the amount of work that the maintainers of other languages have to do in order to get up to speed on the new features.

This would likely require a new CLR major version and the addition of at least one new metadata table. Backwards compatibility would be trivial (if your assembly doesn't have the new table(s), just don't worry about it.) Forwards compatibility, not so much, but it would be worth the pain. The last time we added new metadata, we were able to deal with the compatibility break just fine, and it brought the CLR into a major leap forward. But after 12 years, the CLR 2.0 architecture is really starting to show its limitations. If we're going to do this, we should do it right, instead of even more piling of hacks upon hacks upon hacks.

Would it be better to implement this as a constraint or perhaps some new type (e.g. a type-constructor) or something else entirely?

Given an answer to the above, where would someone start looking in the CLR to implement this change?

I'm not really sure where to begin, but I've been waiting years for this change to the CLI/CLR, and frankly am tired of waiting.

[Frassle]

Given an answer to the above, where would someone start looking in the CLR to implement this change?

I put together a prototype for this (just the clr changes, no language support) and have some comments at https://github.com/dotnet/runtime/issues/6408

[antagonist112358]

@Frassle - thanks a bunch. I'll take a look at this later today / tonight.

I'm going to assume you started implementing this as a type parameter constraint (GenConstraint I think its called in the CLI spec) - this should work, and is probably the most sane starting point.