The case for type classes

[ggreif]

Type classes (first appearing in Haskell around 1991-92) are an elegant mechanism to make ad-hoc polymorphism (overloaded methods) disciplined and dx-friendly in a strongly-typed language. The concept has carried over to PureScript and later Rust (as traits).

The idea is to associate a dictionary to basic types (ground rules) and give parametrised types dictionary transformers. From these ingredients then the compiler can build (derive) such dictionaries for increasingly complex types with minimal user intervention.

To give an example

# Complex numbers are a pair of simpler numbers with fixed rules for addition and multiplication
instance Number<Complex<T can Number>> {
    func \+(a : Complex<T>, b : Complex<T>) : Complex<T> = (a.0 + b.0, a.1 + b.1);
    func \*(a : Complex<T>, b : Complex<T>) : Complex<T> = ...;
}

Above transformation only kicks in when the T can Number constraint kicks in. To make that happen we can declare Float as a `Number instance:

instance Number<Float> {
    let \+ : (Float, Float) -> Float = <builtin>;
    let \* : (Float, Float) -> Float = <builtin>;
}

This way we get valid Complex<Float> numbers. But there are complex integers too (they are called Gaussian integers), so for Number<Int> either we or the compiler has to provide a type class instance:

instance Number<Int> {
    let \+ : (Int, Int) -> Int = <builtin>;
    let \* : (Int, Int) -> Int = <builtin>;
}

Similarly Ordered constraints can be lifted from element types to collections (trees, etc.).

The pretty thing about type classes is that the programmer doesn't need to pass around dictionaries, the compiler does it transparently (as hidden arguments). The compiler also takes care of the other plumbing.

Problems

In a type system with subclassing ambiguities may arise because the user may define instances for overlapping subtypes. In such cases it is not automatic which instance the compiler should choose. Dylan has a similar problem with multiple dispatch and generic functions, but it just suppresses ambiguous specialisations and topologically sorts the viable ones.

[Kamirus]

Here is a couple of details to discuss:

1. Operators: these operator definitions let \+ are a separate issue, not implemented yet, right? We could just focus on simple identifiers, e.g. let add
2. What syntax for type class definitions? class is taken, typeclass then? Maybe it's worth leaning more towards rust and call it trait?
3. How to access type class members, e.g. Cls<T> { func m(): T }. How to invoke m? Should m become global? Or should it be accessed via the class like Cls.m? Always exporting all members to the global scope will clutter the global namespace creating ambiguities.
4. How to import classes and instances? import { Cls } "..."? Should instances be implicitly imported from the currently imported modules? e.g. import Nat "mo:base/Nat"; would import all instances defined in the Nat module? Or should we add a dedicated syntax for that?
5. How to solve ambiguity? There should be a syntax to explicitly provide the instance if the compiler can't. We don't have newtypes to disambiguate.
6. Orphan Instances: In Haskell and PureScript every instance Cls<T> must be defined next to the type class Cls or the type T. Since we don't have nominal types and we want to allow users to write their instances for classes defined elsewhere, we need to allow orphan instances. This means that an extra import might change the instance resolution -- create ambiguity or resolve a different instance suddenly.

[rvanasa]

Use cases for type classes (or anything similar to Rust-style traits) that we've encountered over time:

• Better alternative to debug_show to print debug information for data structures
• Simplified patterns for test libraries such as motoko-matchers and fuzz
• Better assertion error messages
• Extending do ? { ... } syntax to Result
• More convenient hashing / comparison for data structures without having to pass a function to each operation
• Simplified DX for converting between types