Achieving covariant return types on type level in presence of a non-finitary class graph

user_1544278 0
Viewed 44

Imagine a pretty ordinary piece of code:

    trait Template[X, +T] {
        def m :T
    }
    trait Root[X] extends Template[X, Wrap[X]] {
        override def m = new Wrap[X]
    }
    trait Sub[X] extends Root[X] with Template[X, Wrap2[X]] {
        override def m = new Wrap2[X]
    }
    trait Wrap[X] extends Root[Option[X]]
    trait Wrap2[X] extends Sub[X]

Root is a base class of a class hierarchy which happens to have method m the return type of which is occasionally narrowed by subclasses, as per Sub. An additional requirement is that I need that return type encoded somehow in the type of any C <: Root[_], so I can generalize over it. This is done through trait Template: I can in my implicits declare type parameters [X, T, W <: Template[X, T]] (forget for now problems with type inference here).

The problem is, the code above does not compile - the class graph is non-finitary. It is because:

Root[X] <: Template[X, Wrap[X]] <: Template[X, Root[Option[X]]]

For reasons unbeknownst to me, it is a good idea to expand the last type in the compiler by substituting Root[Option[X]] recursively with X. Now, if someone can explain why eager expanding of the subtype relation is done here, and not in Root[X] <: Template[X, Root[X]], for example, it would be great to know, but is not my main question here. Which is: how to refactor it? I see two options: 1.

trait Template[X, +T[_]] {
    def m :T[X]
}

This won't work, because the kind of the return type is not always the same: even adding a bound on a type parameter will break it.

  1. The second alternative, are of course, member types:
trait Root[X] {
    type Result <: Wrap[X]
    def m :Wrap[X]
}
trait Sub[X] extends Root[Option[X]] {
    type Result <: Wrap2[X]
}

But member types come always with one huge problem: the only possible way of achieving covariance is by declaring the return type Result as an upper bound. However, in that case, I cannot implement method m within that class in any other way than throwing an exception, because Result is unknown in that place. If I want to keep the hierarchy open for extension, for every interface trait I have to have a separate implementation class, i.e.

class RootImpl[X] extends Root[X] {
    override type Result = Wrap[X]
    override def m = new Wrap[X]
}
class SubImpl[X] extends Sub[X] {
    override type Result = Wrap2[X]
    override def m = new Wrap2[X]
}

Even if I extract the above bodies to mix in traits, so I don't have to cut and paste the implementation in every Root subclass which would like to use the default implementation, it is still quite inconvenient compared to having the implementation within the actual interface traits.

Is there anything I didn't think of?

covariance scala
2 Answers

Would something like this work?

sealed trait Template[X, +T] {
  def m(implicit ops: TemplateOps[X, T]): T = ops.m
}
sealed trait TemplateOps[X, +T] {
  def m: T
}

object TemplateOps {
  implicit def rootOps[X] = new TemplateOps[X, Option[X]] {
    def m: Option[X] = ???
  }
  implicit def subOps[X] = new TemplateOps[X, X] {
    def m: X = ???
  }
}
class Root[T] extends Template [T,Option[T]
class Sub[T] extends Template [T,T]
user_92011810

Well, I have since thought of and tried another solution, so I thought I'd answer my question for posterity. It doesn't solve my real issue well, so I won't accept it though, but more on that later.

What I forgot, because as most people I do not really use structural types as I view them as a shabby solution, this actually might be a sensible, minimalistic application for them. Scala allows to refine a type not only by specifying its member types, but also methods (and values). We could get rid of Template completely and use plain hardcoded covariance:

    trait BaseSignature {
        def m :Any
    }
    trait Root[X] extends BaseSignature {
        override def m = new Wrap[X]
    }
    trait Sub[X] extends Root[X] {
        override def m = new Wrap2[X]
    }

We simply use the whole signature of method m, including its return type, as part of a type we are interested in. A simplest example would be:

def wrap[R](x :BaseSignature { def m :R }) :X = x.m 
wrap(new Root[Int]) //:Wrap1[X]
wrap(new Sub[Int]) //:Wrap2[X]

What's important to note, is that x.m call there is not reflective, as m method itself is declared in BaseSignature - scala compiler calls simply that and does a no-op cast to R. BaseSignature is necessary because of scala's annoying rule that an implemented method always overrides a declaration, even from the point of view of the caller, so an argument of x :Root[X] { def m :R } would have x.m :Wrap1[X] and there is no way around it AFAIK.

This solution even works for reasonably complex method signatures, including generic methods with their own type parameters with bounds, as well as using type parameters of the enclosing class. Type inference in the latter case has serious issues though. Unfortunately, and I did not realise it until I coded the simpler methods, there is a problem with return types of higher kinds which depend on type arguments, or worse, on member types of value arguments. Consider instead:

trait Root[X] {
   def m[A] = new Wrap1[A]
}
trait Sub[X] {
    def m[A] = new Wrap3[A, X]
}
trait Wrap3[A, B]

The return type which we must infer here is a type constructor, and Scala 2 is very bad at that: it would infer R in m[A] :R[A] no problem in the first case, but in the case of Wrap2 only if A is the last argument, so, while simple cases might be covered, it is not a robust, generic solution. From what I read, Scala 3 could infer correctly R[A] =:= [A]Wrap3[X, A], so it might be good in the future. For now, I would need to define an external type alias which guides the inferer:

trait Sub[X] extends Root[X] {
    type SubResult[A] = Wrap3[X, A]
    override def m[A] :SubResult[A] = new Wrap3[A]
}

Not ideal, but still better then the member type solution described earlier, as in this case any subclass Sub2 of Sub would just define its own type type Sub2Result[A] = ..., posing no conflict.

I might still stick with this as it looks like migration to Scala 3 will be the easiest, at the same time producing the simplest solution. It's still an interesting problem though, so I certainly would like to hear alternatives.

user_15442780
Related