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.

[aluanhaddad]

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

[oscarvarto]

+1 I am also craving for some bacon!

[mooman219]

+1 Ran into an issue where I needed this today

[aluanhaddad]

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]

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]

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

[Alxandr]

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]

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

[aluanhaddad]

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

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]

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

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]

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]

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

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

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]

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]

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

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

[gusty]

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

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]

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]

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]

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

[dzmitry-lahoda]

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]

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]

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]

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

[gafter]

Issue moved to dotnet/csharplang #339 via ZenHub