驯服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使用具体类型实例化a :

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.(读<:<作"是"的子类型").然后你可以在状态[MyMove]中传递状态[Move]进行预测时没有问题.但是,您不能在此处使用M上的协变修改器,因为它在逆变位置中显示为后继函数的参数.

为什么这是个问题？你的继任者声明说它需要一个M并返回一个国家.协变注释说国家[M]也是国家[任何].所以我们应该允许这个任务:

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

现在,如果我们有一个State[Any],那么x.successor是什么类型的？ Any => MyMove.这是不正确的,因为您的实现期望a MyMove,而不是Any

Answer 2

对于更新的代码.

编译器对投诉非常公平.算法使用State的一个子类表示,状态后继可以返回State [M]的任何其他子类

您可以声明IntegerOne类

trait Abstract[T]
class IntegerOne extends Abstract[Int]

但编译器不知道AbstractOne [Int]的所有实例都是IntegerOne.它假设可能还有另一个类也实现了Abstract [Int]

class IntegerTwo extends Abstract[Int]

您可以尝试使用隐式转换从Abstract [Int]转换为IntegerOne,但是traits没有隐式视图边界,因为它们根本没有值参数.

解决方案0

因此,您可以将算法特征重写为抽象类并使用隐式转换:

abstract class MyAlgorithm[MT <: Move, ST <: State[MT]] (implicit val toSM : State[MT] => ST) extends Algorithm {
  override type M = MT // finalize types, no further subtyping allowed
  override type S = ST // finalize types, no further subtyping allowed
  def score(s : S) : Int = s.moves.size
  override def bestMove(s : S) : M = {
    val groups = s.moves.groupBy( m => score(toSM ( s.successor(m)) ) )
    val max = groups.keys.max
    groups(max).head
  }
}

implicit def toMyState(state : State[MyMove]) : MyState = state.asInstanceOf[MyState]

object ConcreteAlgorithm extends MyAlgorithm[MyMove,MyState]

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

这个解决方案有两个缺点

• 使用asInstanceOf进行隐式转换
• 搭售类型

您可以先将其作为进一步打字的费用熄灭.

解决方案1

让我们使用Algorithm作为唯一的类型参数化源并相应地重写类型结构

trait State[A <: Algorithm] { _:A#S =>
  def moves : List[A#M]
  def successor(m : A#M): A#S
}

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

在这种情况下,您的MyAlgorithm可以在不重写的情况下使用

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

使用它:

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

object ConcreteAlgorithm extends MyAlgorithm {
  override type M = MyMove
  override type S = MyState
}

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

查看此tecnique的更多抽象和复杂的用法示例:Scala:抽象类型与泛型

解决方案2

您的问题也有一个简单的解决方案,但我怀疑它可以解决您的问题.在更复杂的用例中,您最终会再次遇到类型不一致的问题.

只需让MyState.successor返回this.type而不是State[M]

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

final 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))).asInstanceOf[this.type]
}

其他事情没有变化

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
  override def bestMove(s : S) : M = {
    val groups = s.moves.groupBy(m => score(s.successor(m)))
    val max = groups.keys.max
    groups(max).head
  }
}

object ConcreteAlgorithm extends MyAlgorithm {
  override type M = MyMove
  override type S = MyState
}

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

注意final修饰符到MyState类.它确保转换asInstanceOf [this.type]是正确的.Scala编译器可以自己计算最终类始终保持this.type但仍然存在一些缺陷.

解决方案3

无需将算法与自定义状态绑定.只要算法不使用特定的状态函数,它就可以在没有类型边界练习的情况下编写得更简单.

trait Algorithm{
  type M <: Move
  def bestMove(s : State[M]) : M
}
trait MyAlgorithm extends Algorithm {
  def score(s : State[M]) : Int = s.moves.size
  override def bestMove(s : State[M]) : M = {
    val groups = s.moves.groupBy(m => score(s.successor(m)))
    val max = groups.keys.max
    groups(max).head
  }
}

这个简单的例子很快就没有出现在我脑海中,因为我认为绑定到不同的状态是强制性的.但有时只有部分系统真正应该明确参数化,你可以避免额外的复杂性

结论

讨论的问题反映了我经常在我的实践中出现的一系列问题.

有两个相互竞争的目的不应该相互排斥,而是在scala中这样做.

• 可扩展性
• 概论

首先意味着您可以构建复杂的系统,实现一些基本的实现,并能够逐个替换它的部分,以实现更复杂的实现.

第二个允许您定义非常抽象的系统,可用于不同的情况.

Scala开发人员在为一种既可以实现功能又面向对象的语言创建类型系统方面具有非常具有挑战性的任务,同时仅限于具有类型擦除等巨大缺陷的jvm实现核心.给予用户的Co/Contra-variance类型注释不足以在复杂系统中表达类型关系

每当我遇到可扩展性 - 一般性困境时,我就会遇到困难,决定接受哪种权衡.

我不想使用设计模式,而是用目标语言声明它.我希望有一天scala会给我这个能力.