如何在Scala中将F界多态与关联类型结合在一起? [英] How to combine F-bounded polymorphism with associated types in Scala?

问题描述

我具有一个称为Graphlike的特征，可以用作图形.值得注意的是，我要拥有的属性之一是方法g.subgraph(Set(1, 2, 3))将返回仅包含顶点1、2和3的相同类型的子图.显然，这意味着我想要F边界多态性和看起来像这样:

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
}

这几乎可行.但是，当我尝试将两者混合使用并对结果做一些有用的事情时，Scala的类型系统会感到困惑:

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

出现如下错误:

[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理解在所有派生对象中两个关联的类型都相同?

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

推荐答案

最简单的解决方案似乎是这样.只要确保子图返回与this.type相同的类型，就可以了.不需要A-当您尝试证明A是this的类型时，它只会增加额外的复杂性.

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

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

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

具有State作为类型参数也对我有用.请注意，在UsesAutomataAsGraphs中，如果您使用A <: Automaton[_](通配符)，则它不起作用，因为State可能是任何东西.编译器希望您确保返回的Automaton具有相同的State类型(因为它是无界的，并且其他扩展Automaton的类可能会定义不同的类型).

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

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

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

如果您这样定义subgraph，它也将起作用:

It also works if you define subgraph as such:

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

由于它是互变的，即使Vertex在不同的类别和/或特征上有所不同，它也会起作用.

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

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

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

这篇关于如何在Scala中将F界多态与关联类型结合在一起?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！