16

Scala 型システムを理解していないようです。私は、2 つの基本的な特性と、アルゴリズムのファミリーがそれらと連携するための特性を実装しようとしています。以下で何が間違っていますか？

動きと状態の基本特性。これらは、問題を明らかにするメソッドを含めるように単純化されています。

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

私は以下に関して非常に不安定な立場にありますが、コンパイラはそれを受け入れているようです... Algorithm トレイトの具体的な実装を試みています。

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

更新:提案されているように、抽象型メンバーを使用するように Algorithm 特性を変更しました。これは、私が言い表したように質問を解決しましたが、少し単純化しすぎました。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
                                  ^

これを機能させるには、トレイトのトレイト (ケーキ パターンとも呼ばれる) を使用するアプローチに移行する必要がありますか? （私はここで推測しているだけです。私はまだ完全に混乱しています。）

4

2 に答える 2

14

MyAlgorithm#bestMoveパラメータを取ると明示的に宣言しState[Move]ますが、内部では、ではなくMainを渡そうとしています。 MyStateState[MyMove]State[Move]

これを解決するには、いくつかのオプションがあります。1 つは、 の型を制約しないことです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
}

次に、メイン クラスで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. <:<( 「のサブタイプである」と読みます)。そうすれば、State[Move] が予期される場所に State[MyMove] を渡しても問題ありません。ただし、後続関数への引数として反変の位置に現れるため、ここで M に共変修飾子を使用することはできません。

なぜこれが問題なのですか？後継者の宣言は、M を取り、State を返すと述べています。共変注釈は、State[M] も State[Any] であると述べています。したがって、この割り当てを許可する必要があります。

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

がある場合State[Any]、 x.successor はどのタイプですか? Any => MyMove. あなたの実装はMyMoveではなく を期待しているので、これは正しくありませんAny

于 2012-11-14T03:16:13.323 に答える
7

更新されたコード用。

コンパイラは、苦情に対して非常に公平です。アルゴリズムは、示されているように State の 1 つのサブクラスを使用し、状態の後継者は State[M] の他のサブクラスを返す場合があります。

IntegerOne クラスを宣言できます

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

しかし、コンパイラには、AbstractOne[Int] のすべてのインスタンスが IntegerOne になるという手がかりがありません。Abstract[Int] も実装する別のクラスが存在する可能性があると想定しています。

class IntegerTwo extends Abstract[Int]

暗黙的な変換を使用して Abstract[Int] から IntegerOne にキャストしようとすることもできますが、特性には値パラメーターがまったくないため、暗黙的なビュー境界がありません。

ソリューション 0

したがって、 Algorithm トレイトを抽象クラスとして書き直して、暗黙的な変換を使用できます。

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

このソリューションには 2 つの欠点があります

  • asInstanceOf で暗黙的な変換を使用する
  • 結び方

追加のタイプタイイングのコストとして、最初に消火してもよい。

解決策 1

アルゴリズムを唯一の型パラメーター化ソースとして使用し、それに応じて型構造を書き換えましょう

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

この手法のより抽象的で複雑な使用例を参照してください: Scala: 抽象型とジェネリック

解決策 2

あなたの質問には簡単な解決策もありますが、それがあなたの問題を解決できるとは思えません。より複雑なユースケースでは、最終的に型の不一致に再び行き詰まります。

this.type代わりにMyState.successor を返すだけです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)
}

finalMyState クラスの修飾子に注意してください。asInstanceOf[this.type] の変換が正しいことを保証します。Scala コンパイラは、最終クラスが常に保持することを自分自身で計算する場合がありますthis.typeが、それでもいくつかの欠陥があります。

解決策 3

Algorithm をカスタム State と結び付ける必要はありません。Algorithm が特定の State 関数を使用しない限り、型境界の演習を行わなくても、より単純に記述できます。

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 では排除すべき 2 つの競合する目的があります。

  • 拡張性
  • 一般性

1つ目は、複雑なシステムを構築し、いくつかの基本的な実現を実装し、その部品を1つずつ置き換えてより複雑な実現を実装できることを意味します。

2 つ目は、さまざまなケースに使用できる非常に抽象的なシステムを定義することを可能にします。

Scala 開発者は、関数型とオブジェクト指向の両方が可能な言語の型システムを作成するという非常に困難なタスクを抱えていましたが、型消去などの大きな欠陥を伴う jvm 実装コアに制限されていました。ユーザーに与えられた共/反分散型アノテーションは、複雑なシステムで型関係を表現するには不十分です

拡張性と一般性のジレンマに遭遇するたびに、どのトレードオフを受け入れるかを決めるのに苦労します。

デザインパターンを使わず、ターゲット言語で宣言したい。いつかscalaがこの能力を私に与えてくれることを願っています。

于 2012-11-14T12:19:36.763 に答える