Building instances of `this.type` in Scala

Question

I am working on a graph trait called Graphlike where I use dependent/associated types for the vertices. After solving my polymorphism issues, my implementation looks like this:

trait Graphlike {
  type Vertex

  def subgraph(selectedVertices: Set[Vertex]): this.type
}

I also have various kinds of abstract atomic-state automata, which of course behave like graphs:

trait Automaton extends Graphlike {
  type State
  type Vertex = State

  def states: Iterable[State]
  def initialState: State
  def getBuilder: AutomatonBuilder[this.type]


  def subgraph(selectedVertices: Set[Vertex]) = {
    val builder = getBuilder
    // Some logic to actually do something to the builder here
    builder.getAutomaton
  }
}

trait AutomatonBuilder[A <: Automaton] {
  def getAutomaton: A
}

However, when I try to actually implement a concrete automaton, I run into trouble:

class ConcreteAutomaton extends Automaton {
  type State = Int

  def states = List(1, 2, 3)
  def initialState = 1
  def getBuilder = new ConcreteAutomatonBuilder

}

class ConcreteAutomatonBuilder extends AutomatonBuilder[ConcreteAutomaton] {
  def getAutomaton = new ConcreteAutomaton
}

class UsesAutomataAsGraphs {
  val aut = new ConcreteAutomaton
  aut.subgraph(Set(aut.initialState)).subgraph(Set(aut.initialState))
}

gives:

[info] Compiling 1 Scala source to /Users/albin/Downloads/example/target/scala-2.12/classes ...
[error] /Users/albin/Downloads/example/src/main/scala/example/Example.scala:33:20: type mismatch;
[error]  found   : ConcreteAutomatonBuilder
[error]  required: AutomatonBuilder[ConcreteAutomaton.this.type]
[error] Note: ConcreteAutomaton >: ConcreteAutomaton.this.type (and ConcreteAutomatonBuilder <: AutomatonBuilder[ConcreteAutomaton]), but trait AutomatonBuilder is invariant in type A.
[error] You may wish to define A as -A instead. (SLS 4.5)
[error]   def getBuilder = new ConcreteAutomatonBuilder
[error]                    ^

Following the suggestion and making A contravariant gives me other issues. It's also not really what I want; I want my builders to produce the exact same type of automaton.

Answer 1

I'm adding another answer here because it's significantly different from the other one and because it would get too big. This one uses typeclasses and implicit classes to do everything, and I feel it's safer, even though it may seem boilerplate-y and a little too much to you.

Instead of putting subgraph in the Graphlike trait, different objects do the subgraph method and construct new automatons. An implicit class provides the subgraph method because I couldn't prove that G was the type of this in the Graphlike trait itself.

Scastie: https://scastie.scala-lang.org/bYTXEzS3T6uNMShDIjQghA

trait Graphlike {
  type Vertex
}
trait Automaton extends Graphlike {
  type State
  type Vertex = State

  def states: Iterable[State]
  def initialState: State
}
class ConcreteAutomaton extends Automaton {
  type State = Int

  def states = List(1, 2, 3)
  def initialState = 1
}

trait AutomatonBuilder[+A <: Automaton] {
  def getAutomaton: A
}
class ConcreteAutomatonBuilder extends AutomatonBuilder[ConcreteAutomaton] {
  def getAutomaton = new ConcreteAutomaton
}


trait Subgraph[G <: Graphlike] {
  def subgraph(graph: G)(selectedVertices: Set[graph.Vertex]): G
}
trait AutomatonSubgraph[A <: Automaton] extends Subgraph[A] {
  protected def newBuilder: AutomatonBuilder[A]
  def subgraph(automaton: A)(selectedVertices: Set[automaton.Vertex]): A = {
    val builder = newBuilder
    //Do stuff to the builder here
    builder.getAutomaton
  }
}
implicit object ConcreteAutomatonSubgraph extends AutomatonSubgraph[ConcreteAutomaton] {
  protected def newBuilder = new ConcreteAutomatonBuilder()
}

implicit class Subgraphable[+G <: Graphlike](graph: G)(implicit sub: Subgraph[G]) {
  def subgraph(selectedVertices: Set[graph.Vertex]): G = sub.subgraph(graph)(selectedVertices)
}

class UsesAutomataAsGraphs {
  val aut = new ConcreteAutomaton
  val x = aut.subgraph(Set(aut.initialState)).subgraph(Set(aut.initialState))
}

Another approach that stays more faithful to your original design but I don't like: https://scastie.scala-lang.org/AfKX5cpbSXqrqesT4rsUvA