如何在 Scala 中将 F 界多态性与关联类型相结合?

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

在斯卡斯蒂：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))
}

链接到斯卡斯蒂：https://scastie.scala-lang.org/RolPc3ggTxeZ2tUqdXKNEQ

---

如果您这样定义subgraph，它也有效：

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

因为它是逆变的，即使Vertex在不同的类别和/或特征中是不同的，它也会起作用。

链接到斯卡斯蒂：https://scastie.scala-lang.org/fz509HEpTBGoJGaJxLziBQ

Answer 2

首先，自Automaton extends Graphlike[Automaton]年以来写val aut: Automaton with Graphlike[Automaton]是没有意义的(所以Automaton with Graphlike[Automaton] =:= Automaton(。

其次，我猜你希望Graphlike的Vertex在Automaton中State。所以你应该override type Vertex = State添加到Automaton.

第三，Vertex是路径依赖类型。aut.Vertex和a.Vertex(其中val a: Automaton = aut.subgraph(Set(aut.initialState))(是不同的类型。如果您希望subgraph接受不同x: Automaton的Set[x.Vertex]，则应使用类型投影修改其签名

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

(整个代码：https://scastie.scala-lang.org/pKfCrEjDToOXi0e7fDEt7w(

修改subgraph签名的另一种方法是(如@user建议的那样(

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

因此，您应该扩展参数类型(从Set[Vertex]又名Set[this.Vertex]扩展到Set[A#Vertex](或缩小返回类型(从A到this.type(。