How to combine F-bounded polymorphism with associated types in Scala?

Question

I have a trait called Graphlike for things that work as a graph. Notably, one of the properties I want to have is that the method g.subgraph(Set(1, 2, 3)) would return a subgraph of the same type with just the vertices 1, 2 and 3. Apparently, this means that I want F-bounded polymorphism and that Graphlike looks something like this:

trait Graphlike[A <: Graphlike[A]] {
  type Vertex

  def subgraph(selectedVertices: Set[Vertex]): A
}

I also have a trait representing an automaton with associated types for edges and vertices. I want it to behave like a graph. Simplified, it looks like this:

trait Automaton extends Graphlike[Automaton] {
  type State
  type Vertex = State

  def states: Iterable[State]
  def initialState: State
}

This almost works. However, Scala's type system gets confused when I try to mix the two and do something useful with the result:

class UsesAutomataAsGraphs(val aut: Automaton with Graphlike[Automaton]) {
  aut.subgraph(Set(aut.initialState)).subgraph(Set(aut.initialState))
}

gives an error like:

[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:21:56: type mismatch;
[error]  found   : UsesAutomataAsGraphs.this.aut.State
[error]  required: _1.State where val _1: Automaton
[error]   aut.subgraph(Set(aut.initialState)).subgraph(Set(aut.initialState))

How do I get Scala to understand that the two associated types are the same in all derived objects?

Answer 1

The easiest solution seems to be this. Just make sure that subgraph returns the same type with this.type and you're good to go. There's no need for A - it just adds additional complexity as you try to prove that A is the type of this.

trait Graphlike {
  type Vertex

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

trait Automaton extends Graphlike {
  type State
  type Vertex = State

  def states: Iterable[State]
  def initialState: State
}

class UsesAutomataAsGraphs(val aut: Automaton) {
  aut.subgraph(Set(aut.initialState)).subgraph(Set(aut.initialState))
}

In Scastie: https://scastie.scala-lang.org/zMtde7VISKi18LdPXO6Ytw

---

Having State be a type parameter also worked for me. Note that in UsesAutomataAsGraphs, if you use A <: Automaton[_] (a wildcard), it doesn't work, because State could be anything. The compiler wants your assurance that the returned Automaton will have the same State type (because it's unbounded, and other classes extending Automaton could define it differently).

trait Graphlike[A <: Graphlike[A]] {
  type Vertex

  def subgraph(selectedVertices: Set[Vertex]): A
}

trait Automaton[State] extends Graphlike[Automaton[State]] {
  type Vertex = State

  def states: Iterable[State]
  def initialState: State
}

class UsesAutomataAsGraphs[S](val aut: Automaton[S]) {
  aut.subgraph(Set(aut.initialState)).subgraph(Set(aut.initialState))
}

Link to Scastie: https://scastie.scala-lang.org/RolPc3ggTxeZ2tUqdXKNEQ

---

It also works if you define subgraph as such:

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

Because it's contravariant, even if Vertex is different in different classes and/or traits, it'll work.

Link to Scastie: https://scastie.scala-lang.org/fz509HEpTBGoJGaJxLziBQ

Answer 2

Firstly, there's no sense in writing val aut: Automaton with Graphlike[Automaton] since Automaton extends Graphlike[Automaton] (so Automaton with Graphlike[Automaton] =:= Automaton).

Secondly, I guess you want Graphlike's Vertex to be State in Automaton. So you should add override type Vertex = State to Automaton.

Thirdly, Vertex is a path-dependent type. aut.Vertex and a.Vertex (where val a: Automaton = aut.subgraph(Set(aut.initialState))) are different types. If you want subgraph to accept Set[x.Vertex] for different x: Automaton then you should modify its signature using type projection

def subgraph(selectedVertices: Set[A#Vertex]): A

(The whole code: https://scastie.scala-lang.org/pKfCrEjDToOXi0e7fDEt7w)

Another way to modify the signature of subgraph is (as @user proposed)

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

So you should either expand parameter type (from Set[Vertex] aka Set[this.Vertex] to Set[A#Vertex]) or narrow return type (from A to this.type).