Self-recursive types

Let's recall different implementations inheriting from a single trait from the previous example:

sealed trait Lock
class PadLock extends Lock
class CombinationLock extends Lock

We will now extend Lock with an open method, which should return the same type of Lock and let our implementations serve as type parameters:

sealed trait Secret[E]
sealed trait Lock[E] { def open(key: Secret[E]): E = ??? }
case class PadLock() extends Lock[PadLock]
case class CombinationLock() extends Lock[CombinationLock]

The realization is not very interesting for now—the important part is that it returns the same type as the instance it was called on. 

Now, with this implementation, there is an issue that we can use it with something that is not a Lock at all:

case class IntLock() extends Lock[Int]
lazy val unlocked: Int = IntLock().open(new Secret[Int] {})

Naturally, we don't want to allow this! We want to constrain our type parameter so that it is a subtype of Lock:

sealed trait Lock[E <: Lock]

But unfortunately, this won't compile because the Lock takes a type parameter that is absent in the preceding definition. We need to provide that type parameter. What should it be? Logically, the same type as we used to parameterize the Lock—E:

sealed trait Lock[E <: Lock[E]] {
  def open(key: Secret[E]): E = ???
}

The type parameter looks a bit weird because it refers to itself recursively. This way of defining a type is called a self-recursive type parameter (or sometimes an F-bounded type polymorphism).

Now, we can only parameterize Lock by the type, which is itself a Lock:

scala> case class IntLock() extends Lock[Int]
                                      ^
       error: illegal inheritance;
        self-type IntLock does not conform to Lock[Int]'s selftype Int
scala> case class PadLock() extends Lock[PadLock]
defined class PadLock

But unfortunately, we can still mess things up by defining the wrong subtype as a type parameter:

scala> case class CombinationLock() extends Lock[PadLock]
defined class CombinationLock

Therefore, we need to define another constraint that will say that the type parameter should refer to the type itself, not just any Lock. We already know that there is a self-type that can be used for that:

sealed trait Lock[E <: Lock[E]] { self: E  =>
  def open(key: Secret[E]): E = self
}

scala> case class CombinationLock() extends Lock[PadLock]
                                              ^
       error: illegal inheritance;
        self-type CombinationLock does not conform to Lock[PadLock]'s selftype PadLock
scala> case class CombinationLock() extends Lock[CombinationLock]
defined class CombinationLock
scala> PadLock().open(new Secret[PadLock]{})
res2: PadLock = PadLock()
scala> CombinationLock().open(new Secret[CombinationLock]{})
res3: CombinationLock = CombinationLock()

Nice! We've just defined a Lock trait that can only be parameterized with classes that extend this trait and only by the class itself. We've done this by using a combination of the self-recursive type parameter and the self-type.