Bounded polymorphism

[bamarsha]

From microsoft/qsharp-language#149:

Is your feature request related to a problem? Please describe. When writing a polymorphic function in Q#, the type variables are fully general. They are opaque types with no properties that the function can rely on.

But there are many cases where a function needs a type to have certain properties. For example, a function may need its type variables to be equatable or comparable to store/retrieve them from a list or map. Arithmetic functions may also require that the types are numeric.

Describe the solution you'd like Q# needs some form of bounded polymorphism to be able to write functions that are valid for only certain types. I believe type classes are the best solution for this: they are very flexible and fit with Q#'s functional style.

Describe alternatives you've considered Overloading functions based on type (microsoft/qsharp-compiler#29) would solve the naming problem (e.g. PlusI, PlusD, PlusL could be overloaded to Plus), but this solution doesn't scale. Because the numeric types are not formally grouped, there is no way to write a single polymorphic function that calls the right Plus automatically - it similarly needs to be overloaded for each numeric type, creating unnecessary code duplication.

[sezna]

I agree that typeclasses are the right solution here. Here's a potential the haskell-style approach, modified for Q# syntax*:

typeclass Display {
  function display(a: Self) : String;
}

newtype MyType = (myNumber: Int);

instance Display of MyType {
  function display(a: Self) : String{ toString(a::myNumber) }
}

// generic bounded polymorphic callable
function Foo<'A: Display>(a: 'A): Unit {
  let stringified = display(a);
}

function Main() : Unit {
  let myType = MyType(1);
  Foo(myType);
}

*: All keywords and syntax is subject to later bikeshedding. This comment serves only for semantic outline purposes.

[sezna]

It is really quite difficult to write most abstractions without bounded polymorphism. I think this task can be split up into smaller tasks:

1. Allow specifying of bounds for existing built-in classes
2. Allow definition of custom classes
3. Allow implementing custom classes for arbitrary types

Number 1 gets us a lot of functionality, and may be enough for a while. For example, being able to constrain inputs to being Eq + Show would unblock things like a testing framework. Numbers 2 and 3 could be done eventually.