Inherited return type with contravariant type parameter

user_3264147 0
Viewed 156

I have a trait with covariant type A that declares (among others) this method:

sealed trait MaxPQ[+U] {
...
def insert[K >: U : Ordering](v: K): this.type
...
}

abstract class AbstractMaxPQ[U : Ordering] extends MaxPQ[U]

I also have this mix-in that I need to use:

trait FindMin[U] {

  self: AbstractMaxPQ[U] =>

I am returning this.type because I want Node or Array based implementations of the priority queue to return current types and not MaxPQ[U].

In the array based implementation I have the following:

class ArrayMaxPQ[U : Ordering : ClassTag] ...extends AbstractMaxPQ[U] with FindMin[U]{
...
override def insert[K >: U : Ordering](v: K): ArrayMaxPQ[U] = ???
...

this is what is auto-generated by my IDE. Of course I need this method to return ArrayMaxPQ[K]. this.type doesn't take type parameters. Using higher-kinded types here also wouldn't work

def insert[K >: U : Ordering, G[_] <: MaxPQ[_]](v: K): G[K]

since G cannot be parameterized with self type in children.

I am a bit confused since this feels like a simple requirement but I cannot find language feature/syntax required to implement it.

variance contravariance scala inheritance generics
2 Answers

You can actually use higher-kinded types to do this. It's called F-bounded polymorphism.

sealed trait MaxPQ[+U, F[_]] { self: F[_ <: U] =>
  def insert[K >: U: Ordering](v: K): F[K]
}

abstract class AbstractMaxPQ[U: Ordering, F[_]] extends MaxPQ[U, F] {
  self: F[U] =>
}

class ArrayMaxPQ[U: Ordering: ClassTag] extends AbstractMaxPQ[U, ArrayMaxPQ] {
  override def insert[K >: U: Ordering](v: K): ArrayMaxPQ[K] = ???
}

Scastie demo

Instead of passing G into insert, use it as a type parameter of the class/trait itself, and then make sure that this extends that. That's what the self-type is for (self: F[U]). Another useful question

user_118820020

Maybe you want the return type to be wider than this.type but narrower than just MaxPQ[U]. Then try to introduce a type member

sealed trait MaxPQ[+U] {
  type This <: MaxPQ[U]
  // type This >: this.type <: MaxPQ[U] { type This = MaxPQ.this.This }

  def insert[K >: U : Ordering](v: K): This
}

abstract class AbstractMaxPQ[U : Ordering] extends MaxPQ[U] {
  override type This <: AbstractMaxPQ[U]
  // override type This >: this.type <: AbstractMaxPQ[U] { type This = AbstractMaxPQ.this.This }
} 

class ArrayMaxPQ[U : Ordering : ClassTag] extends AbstractMaxPQ[U] {
  override type This = ArrayMaxPQ[U]

  override def insert[K >: U : Ordering](v: K): ArrayMaxPQ[U] = ???
}

Returning the "Current" Type in Scala

If you want the return type to be parametrized with an upper bound of U try to make This higher-kinded

sealed trait MaxPQ[+U] {
  type This[K >: U] <: MaxPQ[K]
  // type This[K >: U] <: MaxPQ[K] { type This[K1 >: K] = MaxPQ.this.This[K1] }

  def insert[K >: U : Ordering](v: K): This[K]
}

abstract class AbstractMaxPQ[U : Ordering] extends MaxPQ[U] {
  override type This[K >: U] <: AbstractMaxPQ[K]
  // override type This[K >: U] <: AbstractMaxPQ[K] { type This[K1 >: K] = AbstractMaxPQ.this.This[K1] }
}

class ArrayMaxPQ[U : Ordering : ClassTag] extends AbstractMaxPQ[U] {
  override type This[K >: U] = ArrayMaxPQ[K]

  override def insert[K >: U : Ordering](v: K): ArrayMaxPQ[K] = ???
}
user_52496210
Related