Please Add Type Classes to C#

[gafter]

See

• https://github.com/MattWindsor91/roslyn/blob/master/concepts/docs/concepts.md
• https://c10109cf-a-62cb3a1a-s-sites.googlegroups.com/site/mlworkshoppe/2016-7.pdf
• https://github.com/MattWindsor91/roslyn

[bbarry]

Neat.

The additional method groups visible inside the method seems weird as does the generic arity when calling these from external code:

concept IOrd<A> {
  int Compare(A a, A b);
}

instance CmpStrInvariant : IOrd<string> {
  int Compare(string a, string b) => string.Compare(a, b, StringComparison.InvariantCulture); 
}
instance CmpStrInvariantIgnoreCase : IOrd<string> {
  int Compare(string a, string b) => string.Compare(a, b, StringComparison.InvariantCultureIgnoreCase); 
}

...
public static void qsort<T>(T[] arr, int a, int b)
  where IOrdT : IOrd<T> {
...

How do I call that algorithm?

I would prefer something more explicit:

public static void qsort<T, instance IOrdT>(T[] arr, int a, int b) // <-- keyword denotes something special here
  where IOrdT : IOrd<T> { 
  // sort arr[a..b]            
  if (a < b) {
    int i = a, j = b;
    T x = arr[(i + j) / 2];
    do {
      while (IOrdT.Compare(arr[i], x) < 0) i++; // <-- explicit receiver
      while (IOrdT.Compare(x, arr[j]) < 0) j--; // <-- explicit receiver
      if (i <= j) {
        swap<T>(arr, i, j);
        i++; j--;
      }
    } while (i <= j);
    qsort(arr, a, j); // <-- implicit type arguments? there is only one possible
    qsort<T, IOrdT>(arr, i, b); // <-- or explicit type arguments (optional)
  }
}

combined with better generic inference in cases where there is only one possible instance to choose from.

Given an additional in scope:

instance CmpInt : IOrd<int> { int Compare(int a, int b) => a - b; }

I could call:

int[] Ints = ...
string[] Strings1 = ...
string[] Strings2 = ...

qsort(Ints, 0, Ints.Count - 1);
qsort<string, CmpStrInvariant>(Strings1, 0, Strings1.Count - 1);
qsort<string, CmpStrInvariantIgnoreCase>(Strings2, 0, Strings2.Count - 1);

[orthoxerox]

See also https://github.com/MattWindsor91/roslyn-concepts-issues/issues/3

Should we use this as the master issue for all type class/trait/compile-time polymorphism issues?

[gafter]

This is the master issue for whether or not we add this particular cluster of features approximately as described in the linked design documents.

[KodrAus]

@bbarry That initial example should definitely be rejected since IOrdT isn't bound by any input parameters. Better generic inference across the board would be good for the cases where type bounds and arguments constrain to a single possible value in scope.

Implementing a concept for a new type instead of adding methods to existing types, the way Rust does for example, probably makes the most sense for C#. I like it :+1:

[orthoxerox]

Related issues (either about type classes (bold) or resolved by type classes or have to be taken into account during implementation (italics)):

• 60 [Proposal] Add support for traits and/or mixins

• #154 Add class templates (contracts or structural interfaces) to force consistent implementation the way interfaces do.

• 2204 Proposal: Static Interfaces

• #2212 Higher Kinded Polymorphism / Generics on Generics

• 3391 Force a generic type to support numeric operations

• #5023 REQUEST: Pattern matching/better type inferencing with generics.

• 5624 [Proposal] Operator overloading on Interfaces

• 7844 [Proposal][Roslyn] Add structural typing support

• 8871 (idea) Adding a 'static if' construct to support generic specialization

• 8986 Proposal: Statically resolved type parameters

• 11773 [Proposal] C# generic constraint (where TSelf : this) to facilitate typing members with TSelf / THISTYPE and the CRT pattern

• 13488 Improve the incomplete generic type constraint implementation

• #15166 Better generic type inference based on type parameter constraints.

[dsaf]

Are instance and concept keywords temporary? I am confused by presence of both "C#" and "Concept C#" code snippets in the first link.

Instance declarations are decoupled from their associated types, allowing post-hoc interface ascription.

What does this mean? I can make an existing compiled type support a new interface?

For C#, we call them concepts, as a nod to C++ and its (abandoned) but related concepts.

Nod means same feature or something different? C++ one to me kind of sounds like compile-time method contracts #119.

[orthoxerox]

@dsaf

"С#" means C# vNow, "Concept C#" means "C# with three new keywords, implicit generic types and an additional step in the generic type inference algorithm". You can write type classes in C# vNow, but you'll have to specialize the types of every generic call.

What does this mean? I can make an existing compiled type support a new interface?

It's not an interface, it's a concept/typeclass/trait. And yes, you can make an existing compiled type support a new concept using an instance/witness.

Nod means same feature or something different? C++ one to me kind of sounds like compile-time method contracts #119.

C++ doesn't use instances/witnesses, IIRC, it uses structural typing for its concepts (if the signature matches, the concept is implemented). I agree that "concept" might be a confusing name for the feature, but changing the keyword is the minormost issue. There are probably some really tricky backward compatibility issues with the new type inference algorithm that haven't cropped up yet.

[iam3yal]

@dsaf

Nod means same feature or something different? C++ one to me kind of sounds like compile-time method contracts #119.

C++ concepts are not really method contracts as described in #119 because the contract is made between the argument and the parameter of a template, however, it is a form of Design by Contract.

[dsaf]

@orthoxerox @eyalsk thank you for explaining.

[BreyerW]

Imho you shouldnt reuse generic syntax if it should function as traits or however it is called, since this is different than generic feature with exception to constraints (filtering classes based on traits might be useful). Remember that during compile time you can always transform new syntax to generic implementation. Such big transforms already happen in c# (if im not mistaken async is such an example).

For now i dont have idea for syntax but i will try to come with something or link to already proposed syntaxes in the past for traits/however it is called.

EDIT: #129 seems wasnt directly linked and i think is worth mentioning since this is another attempt on concept syntax. I dont like everything there (since most look like f#) but that can be revisited.

[iam3yal]

@BreyerW What do you mean by "you shouldnt reuse generic syntax"? where it's reused?

[BreyerW]

@eyalsk for example under Instance Inference on main page i see this:

bool Equals<A>(A a, A b) where EqA:Eq<A>

  Equals({{1},{1,2},{1,2,3}},{{1,2,3},{1,2},{1}}) // type checks: instance inferrable from inferred type arguments

  Equals< int[][] >({{1},{1,2},{1,2,3}},{{1,2,3},{1,2},{1}}) // also checks(used when C# type inference fails)

  Equals< int[][], EqArray<int[],EqArray<int,EqInt>> >({{1},{1,2},{1,2,3}},{{1,2,3},{1,2},{1}}) // also checks (used when instance inference fails).

  (bool Equals<A>(A a, A b) where EqA:Eq<A>  ~~ bool Equals<A,[ConceptParameter] EqA>(A a, A b) where EqA:Eq<A>)

there, in 3rd example, EqArray concept is explicitly passed as second generic, but definition of Equals have only one generic called A (this is what @bbarry mentioned: no explicitness in definition; but im against reusing generic syntax which he proposed, being explicit is good but reusing generic syntax is wrong direction imho). Or this example is contrived and should look differently?

[KodrAus]

@BreyerW IMHO generic syntax is exactly the correct syntax to use here, because it's all about binding a concrete type from the caller that you can describe with bounds. Just like we already do with generics now. Generics are a suitable mechanism for all kinds of type constructors, so I'd be surprised if it used anything else.

EDIT: Whoops, wrong @-mention! While I'm at it though, the thing I don't really like is introducing a new binding in the form of IEq<A> in the where clause. That seems like it could easily end up unconstrained when there is more than 1 inhabitant of IEq<A> in scope. How is the caller supposed to specify the right one?

[iam3yal]

@BreyerW So you basically mean that instances shouldn't be passed as a type argument?

EqArray concept is explicitly passed as second generic

As far as I understand it you don't pass concepts, concepts are the types you model that are used as constraints for the generic type parameters, finally instances implements concepts that are passed as a type argument.

[BreyerW]

After hours of thinking i changed my mind.

But i would like to see this proposal being more explicit than now, at least on definition side. TBH i had to reread some examples triple in order to understand whats going on.

However im not satisfied with instance solution. As far as i understand it should be possible to apply many concepts. In which case instance become tedious quickly. Other syntaxes that i came with in my mind arent great either, like:

public static void qsort<T, concepts [IOrdT [, ...]]>(T[] arr, int a, int b) // <-- [, ...] here means optional array of concepts separated with ,
  where IOrdT : IOrd<T> { 

looks like attributes too much imho.

so maybe, just maybe different approach for more explicitness?

like:

public static void qsort<T>(T[] arr, int a, int b) apply IOrdT 
  where IOrdT : IOrd<T> { //note apply keyword

explicit call would look like:

qsort<string> apply CmpStrInvariant (Strings1, 0, Strings1.Count - 1);

under the hood it still would be generics, just compiler had to transform this to desired implementation.

[orthoxerox]

@BreyerW the idea behind instances is that they link together an existing type and a concept. Implicit concepts are a good idea, especially since most types will have a single instance per concept.

Integers have at least two common rings defined on them, so I wouldn't mind being able to pick one specific instance when passing an int to something that applies it to itself using the operation of the ring.

[iam3yal]

@BreyerW

public static void qsort<T>(T[] arr, int a, int b) apply IOrdT 
  where IOrdT : IOrd<T> { //note apply keyword

You're thinking that changing symbols to words implies explicitness but this doesn't make it so, it just makes it more verbose besides this doesn't seems like idiomatic C#.

qsort<string> apply CmpStrInvariant (Strings1, 0, Strings1.Count - 1);

I wouldn't want to write this.

[BreyerW]

If that so then i guess it should be discarded.

I have question though: do we really need two new keywords? I mean current concept keyword seems functioning like interfaces, why dont reuse them? (remove instance and use concept for those special classes)

[orthoxerox]

@BreyerW to simplify the cognitive load on the programmer and the compiler. A concept is implemented as an interface, but no real type implements it. INumeric<T> is technically an interface (though I guess it should be called something like TNumeric<T> to avoid confusion), but int or float do not implement it, instances TNumericInt and TNumericFloat do.

If you see this is not an ordinary interface, you immediately realize when writing your BigRational library that you shouldn't implement TNumeric<T> in your BigRational struct, you have to create an instance TNumericBigRational which links the concept with its implementation.

Similarly, the compiler can take a shortcut in the specialized type inference routine when it knows the type parameter requires an instance and not a type.

[akutruff]

This is really great work, and it's pretty straightforward. I think there is a strong use case for solving this problem that every C# developer eventually bumps up against.. I hope this gets serious consideration.

[bondsbw]

The implicit type is nice but it's weird that it looks unused. EqA /IOrdT look like they are unreferenced, but are somehow necessary for importing static members from a different type (the concept)? It's confusing and took me a few times to read over it and explanations just to realize that I wasn't missing something.

Instead, how about reusing the implicit keyword* to substitute for the implied type parameter:

public static void qsort<T>(T[] arr, int a, int b) 
  where implicit : IOrd<T> {
...
      while (implicit.Compare(arr[i], x) < 0) i++;
      while (Compare(x, arr[j]) < 0) j--;  // implied, equivalent to `implicit.Compare(...)`
...
}

* (or perhaps instance since it would now be a keyword)

[bondsbw]

And for two or more concepts, bringing their members into scope could become ambiguous, requiring named implicit types:

public concept ISquare<T> {
  T Calculate(T x);
}
public concept ICube<T> {
  T Calculate(T x);
}

instance IntSquare : ISquare<int> {
  public int Calculate(int x) => x * x;
}
instance IntCube : ICube<int> {
  public int Calculate(int x) => x * x * x;
}

public static (A, B) SquareCube<A, B>(A a, B b)
  where implicit SquareA :ISquare<A>
  where implicit CubeB : ICube<B>{
...
      var aSquared = SquareA.Calculate(a);
      var bCubed = CubeB.Calculate(b);
      return (aSquared, bCubed);
...
}

Named implicit types could also work in the single-concept case, and thus it may not be worth using the syntax in my previous comment. Then again, I presume that single-concept generic methods would be used much more often and the shorter syntax may be justified.

[KodrAus]

I like having the concept in the generic bindings, like it currently is in the concept samples:

static A M<A, implicit NumA>(A x) where NumA : Num<A>

I'd also support making implicit itself implicit. I don't see why you couldn't just always allow static methods on a generic if the bounds prove that method exists:

static A M<A, NumA>(A x) where NumA : Num<A>

Couple that with generic type inference and you could define something like:

public concept Square<T> 
{
    T Calculate(T x);
}

instance SquareInt : Square<int> 
{
    public int Calculate(int x) => x * x;
}

public static T SquareValue<SquareT, T>(T a)
    where SquareT : Square<T> 
{
    ...
    var aSquared = SquareT.Calculate(a);
    ...
}

// Full inference
SquareValue(x);

// Partial inference
SquareValue<SquareInt>(x);

// No inference
SquareValue<SquareInt, int>(x);

Then if we had multiple instance of Square<T> available:

// Error: cannot infer type for SquareT
SquareValue(x);

// Partial inference
SquareValue<SquareInt>(x);
SquareValue<FastSquareInt>(x);

// No inference
SquareValue<SquareInt, int>(x);
SquareValue<FastSquareInt, int>(x);

[Thaina]

Is it possible to have anonymous concept at generic constraint?

[orthoxerox]

@Thaina that would be structural typing a la cpp concepts, not type classes. I guess it's possible, but is more or less a different feature.

[iam3yal]

@orthoxerox I don't know if it's a different feature, I'd say it just a different approach, I like the proposed feature though.

[Thaina]

@orthoxerox @eyalsk I just want to close my #9595 request. If concept is a keyword that would be used anywhere include generic constraint then it already include that in this proposal

public void SetPosition<T>(T pos) where T : concept{ float X,Y,Z; }
{
    x = pos.X;
    y = pos.Y;
    z = pos.Z;
}

[iam3yal]

@Thaina concept { float X,Y,Z; } this seems like it contains fields and you can't have fields in an interface so my guess is this wouldn't be allowed in the same way.

[be5invis]

But didn't we already have interfaces?

interface Functor for F<A> { // concept syntax
    public F<B> FMap<A, B>(this F<A> obj, Func<A, B> mor);
}
Functor<List> {
    FMap(obj, mor) = obj.Map(mor)
}
interface Applicative for F<A> where F : Functor { // concept syntax with constraints
    static F<A> Pure<A>(A obj);
    public F<B> Ap<A, B>(this F<A> obj, F<Func<A, B>> mor);
}
interface Show { // convintinal interface
    String ShowAsString()
}
String describe<A> (F<A> obj) where F : Functor, A : Show {
    return obj.FMap((a) => a.ShowAsString())
}

[orthoxerox]

@be5invis Could you explain the difference between your proposal and the OP in more detail, please?

[be5invis]

@orthoxerox I am replying some other replies introduces too many keywords. @MattWindsor91’s proposal looks very Idris-ish...

[vczh]

This means that in the future, when I create a new type which is comparable, besides having to implement：

• IEquitable
• IComparable
• IEquitable<T>
• IComparable<T>
• And I have to do the same thing with IOrd<T> again ... which is painful.

Since we already have:

• IComparable<T>
• void DoSomething<T>(T t) where T:IComparable<T> { ... }
• Partial Class (implementing IOrd<T> outside of T is just add a partial class of T which extends IOrd<T>)

Instead of having the idea of "adding concept", what about adding C++'s partial instantiation (without adding dependent type)? And then we have all the power from concept.

[SamPruden]

@orthoxerox You referenced my issue https://github.com/dotnet/roslyn/issues/11773 as being solved by type classes in https://github.com/dotnet/roslyn/issues/16312#issuecomment-271152541, could you please explain how type classes solve this? Perhaps I'm missing something, but I don't think they do. Particularly and specifically, https://github.com/dotnet/roslyn/issues/11773 allows functionality (a method implementation) in the base to be specialised based on the type of the inheriting type. For a concise example outside of the code dump in the original issue see https://github.com/dotnet/roslyn/issues/11773#issuecomment-223838616 and note MakeFriends(TSelf other) in the base class.

[orthoxerox]

@TheOtherSamP If MakeFriends(T @this, T other) is a method defined in a type class, you can add instances that implement it for every class in the hierarchy without destroying substitution rules as you would with a virtual method with TSelf.

[SamPruden]

@orthoxerox Okay, I understand where you're coming from. I don't think this is really the same thing though as it needs to be implemented each time. That's fairly different from a non virtual method implemented in the base.

Thank you for clarifying though, much appreciated.

[gafter]

We are now taking language feature discussion on https://github.com/dotnet/csharplang for C# specific issues, https://github.com/dotnet/vblang for VB-specific features, and https://github.com/dotnet/csharplang for features that affect both languages.

Type classes are under consderation at https://github.com/dotnet/csharplang/issues/110