scala - 驯服 Scala 类型系统

Question

我似乎不了解 Scala 类型系统。我正在尝试实现
两个基本特征和一个用于一系列算法的特征。
我在下面做错了什么？

移动和状态的基本特征；这些被简化为仅包括
暴露问题的方法。

trait Move
trait State[M <: Move] {
    def moves: List[M]
    def successor(m: M): State[M]
}

这是使用上述算法系列的特征。
我不确定这是对的!
可能涉及一些 +M/-S 的东西......

trait Algorithm {
    def bestMove[M <: Move, S <: State[M]](s: S): M
}

具体移动和状态:

case class MyMove(x: Int) extends Move
class MyState(val s: Map[MyMove,Int]) extends State[MyMove] {
    def moves = MyMove(1) :: MyMove(2) :: Nil
    def successor(p: MyMove) = new MyState(s.updated(p, 1))
}

我对下面的内容非常不稳定，但编译器似乎接受了它......
试图对算法特征进行具体实现。

object MyAlgorithm extends Algorithm {
    def bestMove(s: State[Move]) = s.moves.head
}

到目前为止没有编译错误；但是，当我尝试将所有部分放在一起时，它们就会出现:

object Main extends App {
    val s = new MyState(Map())
    val m = MyAlgorithm.bestMove(s)
    println(m)
}

以上抛出此错误:

error: overloaded method value bestMove with alternatives:
  (s: State[Move])Move <and>
  [M <: Move, S <: State[M]](s: S)M
 cannot be applied to (MyState)
    val m = MyAlgorithm.bestMove(s)
                        ^

更新:我将算法特征更改为使用抽象类型成员，如
建议。这解决了我提出的问题，但我有
把它简化得太多了。 MyAlgorithm.bestMove()方法必须是
允许使用 s.successor(m) 的输出调用自身，如下所示:

trait Algorithm {
    type M <: Move
    type S <: State[M]
    def bestMove(s: S): M
}

trait MyAlgorithm extends Algorithm {
    def score(s: S): Int = s.moves.size
    def bestMove(s: S): M = {
        val groups = s.moves.groupBy(m => score(s.successor(m)))
        val max = groups.keys.max
        groups(max).head
    }
}

以上给出了现在2个错误:

Foo.scala:38: error: type mismatch;
 found   : State[MyAlgorithm.this.M]
 required: MyAlgorithm.this.S
            val groups = s.moves.groupBy(m => score(s.successor(m)))
                                                               ^
Foo.scala:39: error: diverging implicit expansion for type Ordering[B]
starting with method Tuple9 in object Ordering
            val max = groups.keys.max
                                  ^

我是否必须转向使用特征的特征的方法，也就是蛋糕模式，才能使这项工作？ (我只是在这里猜测；我仍然很困惑。)

Answer 1

您声明 MyAlgorithm#bestMove明确地作为 State[Move]参数，但在 Main 内您正试图将其传递给 MyState ，这是一个 State[MyMove]不是 State[Move] .

您有几个选项可以解决此问题。一种是不限制 MyAlgorithm 中的类型:

object MyAlgorithm extends Algorithm {
    def bestMove[M <: Move, S <: State[M]](s: S) : M = s.moves.head
}

不幸的是，scala 类型推断不够智能，无法为您找出这些类型，因此在调用站点，您必须声明它们，调用 MyAlgorithm#bestMove看起来像这样:

val m = MyAlgorithm.bestMove[MyMove, MyState](s)

另一个选项使用 Algorithm 的抽象类型成员特征:

trait Algorithm {
  type M <: Move
  type S <: State[M]
    def bestMove(s: S): M
}

并在具体实现中解析抽象类型:

object MyAlgorithm extends Algorithm {
  type M = MyMove
  type S = MyState
  def bestMove(s: S) : M = s.moves.head
}

然后调用站点将返回到您的原始版本，而不提及类型:

val m = MyAlgorithm.bestMove(s)

您可能希望让 MyAlgorithm 不知道实际类型，并将这些类型的确定留给该对象的“客户端”，在这种情况下，将对象更改为特征:

trait MyAlgorithm extends Algorithm {
  def bestMove(s: S) : M = s.moves.head
}

然后在你的 Main 类中，实例化一个 MyAlgorithm与具体类型:

val a = new MyAlgorithm {
  type M = MyMove
  type S = MyState
}
val m = a.bestMove(s)

您的评论“可能涉及一些 +M/-S 内容”是一个很好的猜测，但在这里对您不起作用。您可能希望协变类型修饰符“+”在这里有所帮助。如果您在 State 上声明了类型参数作为

State[+M]

这表明 State[M] <:< State[N]如果 M <:< N . (读 <:< 作为"is"的一个子类型)。那么你就可以毫无问题地传入一个 State[MyMove] ，其中一个 State[Move] 是预期的。但是，这里不能在 M 上使用协变修饰符，因为它作为后继函数的参数出现在逆变位置。

为什么这是个问题？您的继任者声明说它将需要一个 M 并返回一个状态。协变注解说一个 State[M] 也是一个 State[Any]。所以我们应该允许这个分配:

val x : State[Any] = y : State[MyMove]

现在如果我们有一个 State[Any] ，那么x.successor 是什么类型呢？ Any => MyMove .这不可能是正确的，因为您的实现需要 MyMove ，不是 Any