3

型にパラメータ化されたジェネリックデータ型をScalaに実装しようとしてTいますOrdered[T]。具体的には、Sleator＆Tarjanのスキューヒープ優先度キューの永続バージョンです。こことOdersky-Spoon-Vennersの説明に基づいて複雑な型のパラメーター宣言をたくさん追加した後、実際の機能をテスト/デバッグする前に、コンパイラーエラーが1つ発生しました。

以下は私のコードの簡略版です。

abstract class SkewHeap[+T] {
  // merge two heaps
  def +[U >: T <% Ordered[U]](x : SkewHeap[U]) : SkewHeap[U]
  // remove least element, return new heap
  def delMin[U >: T <% Ordered[U]] : SkewHeap[U]
  def isEmpty : Boolean
  def min : T
  def left  : SkewHeap[T]
  def right : SkewHeap[T]
}

case object Leaf extends SkewHeap[Nothing] {
  def +[U <% Ordered[U]](that : SkewHeap[U]) = that
  def isEmpty = true
}

case class Node[+T](left : SkewHeap[T],
                    min : T,
                    right : SkewHeap[T]) extends SkewHeap[T] {
  def +[U >: T <% Ordered[U]](that : SkewHeap[U]) : SkewHeap[U] =
    that match {
      case Leaf        => this
      case Node(l,y,r) => if (this.min < that.min)
                            Node(this.right + that, this.min, this.left)
                          else
                            Node(this + that.right, that.min, that.left)
    }

  def delMin[U >: T <% Ordered[U]] : SkewHeap[U] = left + right
  def isEmpty = false
}

これにより、次のエラーが発生します。

skew.scala:28: error: no implicit argument matching parameter type (T) => Ordered[T] was found.
   def delMin[U >: T <% Ordered[U]] : SkewHeap[U] = left + right

の宣言のいくつかの変形を試しましdelMinたが、役に立ちませんでした。問題は理解できたと思いますが（メソッド+は注文保証が必要です）、これはどこに置くべきですか？そして、代わりにdelMin戻ることを宣言する方法はありますか？SkewHeap[T]SkewHeap[U]

4

3 に答える 3

3 
abstract class SkewHeap[+T <% Ordered[T]] {
  // merge two heaps
  def +[U >: T <% Ordered[U]](x : SkewHeap[U]) : SkewHeap[U]
  // remove least element, return new heap
  def delMin : SkewHeap[T]
  def isEmpty : Boolean
  def min : T
  def left  : SkewHeap[T]
  def right : SkewHeap[T]
}

case object Leaf extends SkewHeap[Nothing] {
  def +[U <% Ordered[U]](that : SkewHeap[U]) = that
  def isEmpty = true
  def min = throw new RuntimeException
  def left = throw new RuntimeException
  def right = throw new RuntimeException
  def delMin = throw new RuntimeException
}

Scalaは、とに変換したいので、と比較this.minする方法がわかりません。最も簡単な答えは、型変換を追加して強制することです。that.minthis.minOrdered[T]that.minOrdered[U]this.minOrdered[U]

case class Node[+T <% Ordered[T]](left : SkewHeap[T],
                    min : T,
                    right : SkewHeap[T]) extends SkewHeap[T] {
  def +[U >: T <% Ordered[U]](that : SkewHeap[U]) : SkewHeap[U] =
    that match {
      case Leaf        => this
      case Node(l,y,r) => if ((this.min:Ordered[U]) < that.min)
                            Node(this.right + that, this.min, this.left)
                          else
                            Node(this + that.right, that.min, that.left)
    }

  def delMin : SkewHeap[T] = left + right
  def isEmpty = false
}

しかし、これらすべての暗黙的な問題には大きな問題があります。その問題はOrdered、ビューバウンドを使用するすべてのコンテキストで異なる実装を取得できること<% Ordered[Something]です。したがって、順序が一貫していることを確認する他の方法を実際に探す必要があります。

于 2010-07-30T20:43:42.850 に答える
2

シンタックスシュガーを使用するのではなく<%、暗黙のパラメーターを手動で追加することをお勧めします。それははるかに制御されており、何が起こっているのかを確認するのは確かに簡単です：

def delMin[U >: T](implicit ord: U => Ordered[U]): SkewHeap[U] = left + right

<%あなたの場合に演算子を使用する際の問題は、それがではTなくにバインドされることですU。したがって、タイプの関数を探していましたT => Ordered[U]。実際、すべてのメソッドがこれを実行しており、それはあなたが望んでいた動作ではないと思います。

また、イディオムに関する注意事項：++2つのコレクションを連結するための演算子と+、既存のコレクションに単一の値を追加するための演算子を使用するのが通例です（、、、および標準ライブラリのほとんどすべてのコレクションを参照Vector）ArrayBuffer。

于 2010-07-30T20:37:41.753 に答える
0

他の提案に加えて、Orderedから暗黙のパラメーターOrdering [T]に切り替えることを検討してください。これにより、制御がはるかに簡単になり、柔軟性が向上します。

[編集]非常に簡単な例：

class Foo[T](val t:T)(implicit val ord: Ordering[T]) {
   def min(that:Foo[T]) = if (ord.compare(this.t, that.t) < 0) this else that
}

この後、順序付けのあるすべてのタイプにFooを使用できます。もちろん、自分で作成することもできます。

implicit object barOrdering extends Ordering[Bar] {...}

この後、を作成できますFoo[Bar]。

（非常に基本的な例で申し訳ありませんが、私のPCが故障し、IDEを利用できません...）

于 2010-07-31T12:14:44.797 に答える