Bounded polymorphism

[bamarsha]

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

Additional context This would solve microsoft/qsharp-language#147. Equatable types would have an instance of the equatable type class.

[cgranade]

I really love the idea of using typeclasses to solve the overloading problem in a much more scalable way. This feature would be an absolute marvel for the libraries, to be sure!

Thinking through a few examples of what this could look like:

concept 'Self is UnwrappableTo<'Inner> when {
    // Alternatively, function (!) if we allow operators as functions.
    function Unwrapped(self : 'Self) : 'Inner;
}

example LittleEndian of UnwrappableTo<Qubit[]> {
    function Unwrapped(self : LittleEndian) : Qubit[] {
        // compiler generated
    }
}

function UnwrappedTwice<'T, 'U, 'V where 'T is UnwrappableTo<'U>, 'U is UnwrappableTo<'V>>(value : 'T) : 'V;

For a more practical example than UnwrappedTwice, this would help a lot with both classical and quantum arithmetic.

concept 'Self is EquatableTo<'Other> when {
    function Equals(self : 'Self, other : 'Other) : Bool;

    invariant Reflexive(self : 'Self) : Unit {
        Fact(Equals(self, self));
    }

    invariant Symmetric(self : 'Self, other : 'Self) : Unit {
        EqualityFact(Equals(self, other), Equals(other, self));
    }

    invariant Transitive(self : 'Self, middle : 'Self, other : 'Self) : Unit {
        if (Equals(self, middle) and Equals(middle, other)) {
            Fact(Equals(self, other));
        }
    }
}

concept 'Self is Monoid where 'Self is EquatableTo<'Self> when {
    function Plus(self : Self, other : Self) : Self;
    function AdditiveIdentity() : Self;

    // similar invariants for checking additive identity...
}
concept 'Self is Group where 'Self is Monoid when {
    function Inverse(self : Self) : Self;
}
concept 'Self is Field where 'Self is EquatableTo<'Self>, 'Self is Group { ... }
concept 'Self is Numeric where 'Self is Field when {
    function As(number : Double) : 'Self;
    // alternatively, use new ConvertableAs concept and make when empty.
}

example Int is Numeric { ... }
example Double is Numeric { ... }
example Bool is Numeric {
    function Plus(self : Bool, other : Bool) : Bool {
        return Xor(self, other);
    }
    function AdditiveIdentity() : Bool {
        return false;
    }
}

// Can now use to define new numeric types.
newtype Complex = (Real: Double, Imag: Double);
example Complex is Monoid {
    function Plus(self : Complex, other : Complex)  : Complex {
        return Complex(self::Real + other::Real, self::Imag + other::Imag);
    }

    function AdditiveIdentity() : Complex {
        return Complex(0.0, 0.0);
    }
}

newtype Fraction = (Numerator: Int, Denominator: Int);
example Fraction is EquatableTo<Fraction> {
    function Equals(self : Fraction, other : Fraction) : Bool {
        return Equals(
            self::Numerator * other::Denominator,
            self::Denominator * other::Numerator
        );
    }
}

function Sum<'T where 'T is Monoid>(elements : 'T[]) : 'T {
    return Folded(
        Plus<'T>,
        elements,
        AdditiveIdentity
    );
}

function Product<'T where 'T is Group>(elements : 'T[]) : 'T {
    // ...
}

// Quantum analogue
concept 'Self is QNumeric<'Classical> where 'Classical is Numeric when {
    operation Add(constant : 'Classical, register : 'Self); 
    // ...
}

example LittleEndian is QNumeric<Int> {
    // ...
}

newtype FixedPoint = (Int, Qubit[]);
example FixedPoint is QNumeric<Double> {
    // ...
}

(Apologies, that wound up longer than I hoped...!)

[crazy4pi314]

This looks so freaking cool, and would help remove so much cognitive load with the functions/ops that have to have separate definitions for each type. 💖🎉

[cgranade]

If you don't mind one more example of a concept that could be useful in helping to organize the libraries:

concept 'Collection is Mappable<'Input> when {
    function Map<'Output>(fn : ('Input -> 'Output), collection : 'Collection) : 'Output[];
    operation ApplyToEach<#Characteristics>(op : ('Input => Unit is #Characteristics), collection : 'Collection) : Unit;

    // NB: may want a different name for this concept if the following functions are also
    // included.
    function Length(collection : 'Collection) : Int;
    function Head(collection : 'Collection) : Maybe<'Input>;
    function Tail(collection : 'Collection) : Maybe<'Input>;
    function Most(collection : 'Collection) : 'Collection;
    function Rest(collection : 'Collection) : 'Collection;
}

example 'T[] of Mappable<'T> { ... }
example Range of Mappable<Int> { ... }

// Now the following can both be used, without needing SequenceI in the first case.
Mapped((x : Int) -> x * x, 0..5);
Mapped((x : Int) -> x * x, [0, 1, 10, 101]);

[bamarsha]

Maybe Map can be split out into its own concept, and have the collection functions in one or more other concepts (e.g. Foldable, Traversable, etc.).

    function Map<'Output>(fn : ('Input -> 'Output), collection : 'Collection) : 'Output[];

Shouldn't this be:

    function Map<'Output>(fn : ('Input -> 'Output), collection : 'Collection<'Input>) : 'Collection<'Output>;

since the collection is not necessarily an array? Requires HKTs though.

function Tail(collection : 'Collection) : Maybe<'Input>;

Tail is generally everything but the head, rather than the last element, right?

[cgranade]

Maybe Map can be split out into its own concept, and have the collection functions in one or more other concepts (e.g. Foldable, Traversable, etc.).

That makes a lot of sense, yeah; I'll readily admit this was a rough thought to try and establish another usecase.

    function Map<'Output>(fn : ('Input -> 'Output), collection : 'Collection) : 'Output[];

Shouldn't this be:

    function Map<'Output>(fn : ('Input -> 'Output), collection : 'Collection<'Input>) : 'Collection<'Output>;

since the collection is not necessarily an array? Requires HKTs though.

Allowing Map to return a different kind of collection than an array does seem like a good improvement, yeah. In the Range example, what would be the type of the output from Mapped((x : Int) -> x * x, 0..10);?

(As a side note, I really should have used Mapped from the start; I blame a lack of coffee.)

function Tail(collection : 'Collection) : Maybe<'Input>;

Tail is generally everything but the head, rather than the last element, right?

We went with Mathematica-style Head/Tail for first and last, Most/Rest for all-but-first/all-but-last in this case, but happy for feedback on that before we hit 1.0.

[bamarsha]

Allowing Map to return a different kind of collection than an array does seem like a good improvement, yeah. In the Range example, what would be the type of the output from Mapped((x : Int) -> x * x, 0..10);?

It looks like Range should not be directly mappable, but you could convert it into a more general sequence type first.

We went with Mathematica-style Head/Tail for first and last, Most/Rest for all-but-first/all-but-last in this case, but happy for feedback on that before we hit 1.0.

Hmm. Using the body part analogy, tails are longer than heads, so I would expect head to return a single item and tail to return a list. I think the last item in an array could just be Last. Using Tail to mean Last seems to go against the convention in most functional languages.

[alan-geller]

I'm going to transfer this issue to the qsharp-language repo, since that's now the proper place for language suggestions.