如何将F-界多态性与Scala中的关联类型结合起来？

Question

我有一个名为Graphlike的特性，用于作为图形工作的事物。值得注意的是，我希望拥有的一个属性是，方法g.subgraph(Set(1, 2, 3))将返回一个与顶点1、2和3相同类型的子图。显然，这意味着我需要F有界多态性，而Graphlike看起来如下所示：

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

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

我也有一个特征，代表一个自动机与相关类型的边和顶点。我想让它表现得像个图。简化后，如下所示：

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

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

这几乎成功了。但是，当我尝试将两者混合起来并对结果做一些有用的事情时，Scala的类型系统就会变得混乱：

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

给出一个错误，例如：

[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))

如何让Scala理解两个关联类型在所有派生对象中是相同的？

Answer 1

最简单的解决办法似乎就是这个。只要确保子图在this.type中返回相同的类型，就可以了。不需要A --它只是增加了额外的复杂性，因为您试图证明A是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))
}

在Scastie：https://scastie.scala-lang.org/zMtde7VISKi18LdPXO6Ytw

让State成为一个类型参数也对我有用。注意，在UsesAutomataAsGraphs中，如果使用A <: Automaton[_] (通配符)，它就不能工作，因为State可以是任何东西。编译器希望您保证返回的Automaton具有相同的State类型(因为它是无界的，扩展Automaton的其他类可以不同地定义它)。

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))
}

链接到Scastie：https://scastie.scala-lang.org/RolPc3ggTxeZ2tUqdXKNEQ

如果您将subgraph定义为这样的话，它也是有效的：

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

因为它是相反的，即使Vertex在不同的类和/或特性上是不同的，它也能工作。

链接到Scastie：https://scastie.scala-lang.org/fz509HEpTBGoJGaJxLziBQ