Search code examples
dartgenericscomparable

Adding the generic type to a comparable type in Dart

This is a followup question after reading this Q&A:

I have a class like so:

class BinarySearchTree<E extends Comparable> { ... }

so I can create an instance like this:

final tree = BinarySearchTree<int>();

My question is about using Comparable vs Comparable<E>. When I do this:

class BinarySearchTree<E extends Comparable> { ... }

then the type defaults to E extends Comparable<dynamic>. I normally try to avoid dynamic, so in order to be more explicit about the type that is being compared, it seems like I should write it this:

class BinarySearchTree<E extends Comparable<E>> { ... }

But in that case I get an error here:

final tree = BinarySearchTree<int>();
// 'int' doesn't conform to the bound 'Comparable<int>' of the type parameter 'E'.
// Try using a type that is or is a subclass of 'Comparable<int>'.

This demonstrates my lack of understanding of generics. What am I missing?

Solution

  • In Dart, a class cannot implement 2 different concrete instances of a generic interface:

    abstract class Foo<T> {}

// error: Foo can only be implemented once
class Bar implements Foo<String>, Foo<int> {}

    num implements Comparable<num>, because it would be slightly absurd for the built-in number types to not be comparable. However, since int is a subtype of num (and therefore inherits Comparable<num>, it cannot have Comparable<int>.

    This leads to the slightly weird consequence that int does not implement Comparable<int>.

    The problem you're facing is that from the language's point of view, there are 2 types involved: the type of the elements being compared, and the type of the elements they are being compared to.

    As such, your type will need 2 type parameters:

    class Tree<T extends Comparable<S>, S> {
  T get foo;
}

final intTree = Tree<int, num>();
final foo = intTree.foo;  // returns an int

    Admittedly, this isn't a super clean solution, but if you're using Dart 2.13 or higher, you can use typedefs to make it a bit nicer:

    typedef IntTree = Tree<int, num>;
typedef RegularTree<T> = Tree<T, T>;

final intTree = IntTree();
final stringTree = RegularTree<String>();

intTree.foo  // is an int
stringTree.foo  // is a String

    There is another option, which is to just drop some type safety and use Comparable<dynamic>, but personally I'd recommend against it. BTW, if you want to avoid accidentally missing type parameters you can disable implicit-dynamic as described here: https://dart.dev/guides/language/analysis-options#enabling-additional-type-checks

    This will give an error any time the type dynamic is inferred from context without the programmer actually typing the word dynamic