Implement type classes

[MarvinHannott]

I think type classes would be a great addition to Dart, and its extension methods already lay the ground work.

Why though? Because typical OOP struggles to model different capabilities of an object on the type level. Consider the Iterator class: it's a simple iterator that produces values in only one direction. But one could easily think of a bidirectional iterator that can also go backwards or an iterator that knows its own length, or a mixture of both. And you might ask yourself: "Alright, where's the problem? I can easily do that with interfaces." Except, you can't. Just try to implement operators like map or filter, and you'll easily spot the problem. You basically need to "conditionally" implement interfaces depending on the wrapped iterator's type. And that's the problem type classes solve! You don't need to just smash all these interfaces together into one and implement the methods inefficiently (like Iterable) or throw UnsupportedException.

Type classes could be implemented by leveraging existing syntax and concepts.

// Bidirectional can only be implemented for a type that also implements Iterator
type class Bidirectional<T> implements Iterator<T> {
  T get currentBack;
  bool moveBack();
}

// Type classes can have default implementations
type class ExactLength<T> implements Iterator<T> {
  int get length => 42;
}

// RandomAccess can only be implemented when also both Bidirectional and ExactLength are implemented
type class RandomAccess<T,K> with Bidirectional<T>, ExactLength{
  T operator[](K key);
}


final class Wrapper<T, R extends Iterator<R>> implements Iterator<T>{
  final R _source;

  T get current => _source.current;
  bool moveNext() => _source.moveNext()

}

// This is how an instance of a type class is created. Generic type parameters can be constrained by 'where' clause. This only works for type classes. Notice that R is implicitly constrained by Iterator<T>.
extension<T, R> on Wrapper<T,R> implements Bidirectional<int>
where R: Bidirectional<T>{
  T get currentBack => _source.currentBack;
  bool moveBack() => _source.moveBack();
}

// Generic type parameters can still be further constrained by 'extends' (though redundant in this case). This still only works for classes. 
extension<T, R extends Iterator<T>> on Wrapper<T,R> implements ExactLength<T>
where R: ExactLength<T>{
  int get length => _source.length;
}

// Generic type parameters can have multiple constraints (though redundant in this case)
extension<T,K,R> on Wrapper<T,R> implements RandomAccess<T>
where R: ExactLength<T>, RandomAccess<T,K>{
  T operator[](K key) => _source[key];
}

// Ambiguity between instances of type classes or class methods can be resolved similarly to regular extension methods.
void useIterator<T, R>(R iter)
where R: Bidirectional<T>{
  final back = Bidirectional(iter).back;
}

// When only one type constraint is necessary then we can simplify the syntax, but it's exactly the same as useIterator
void useIterator2<T>(Bidirectional<T> iter){
}

Type classes essentially look exactly like regular classes, but they can only be instantiated either in the same library that defines that type class or in the library that defines the type the type class get's implemented for. Otherwise there would be ambiguity between multiple instances. But with Dart's new extension types it becomes trivial to create cheap wrapper types.

But where's the difference between type classes and interfaces/subtyping? Interfaces/subtyping allow runtime polymorphism while type classes don't. Type classes only work on type parameters and a known type at compile time. That's why the Wrapper class requires a second type parameter for the type of the wrapped iterator.