Ко- и контравариантные типы в очереди с общим приоритетом - PullRequest
Новая
       28

Ко- и контравариантные типы в очереди с общим приоритетом

3 голосов
/ 30 июля 2010

Я пытаюсь реализовать в Scala общий тип данных, параметризованный для типа T, который должен быть Ordered[T].В частности, это постоянная версия приоритетных очередей Sleator & Tarjan skew heap .После добавления множества сложных описаний параметров типа, основанных на объяснении здесь и в Odersky-Spoon-Venners, я дошел до одной ошибки компилятора, прежде чем смогу протестировать / отладить реальную функциональность.* Ниже приведена упрощенная версия моего кода. 

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]?

Ответы [ 3 ]

3 голосов
/ 31 июля 2010 
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.min, потому что хочет преобразовать this.min в Ordered[T] и that.min в Ordered[U].Самый простой ответ - добавить преобразование типа в this.min к Ordered[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], поэтому вам действительно нужно искать какой-то другой способ убедиться, что ваш порядок соответствует.

2 голосов
/ 31 июля 2010

Вместо того, чтобы использовать синтаксический сахар <%, я предлагаю вам вручную добавить неявный параметр. Это намного более контролируемо, и, конечно, легче увидеть, что происходит: 

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

Проблема с использованием оператора <% в вашем случае связана с T, а не U. Таким образом, он искал функцию типа T => Ordered[U]. На самом деле, все ваши методы делают это, и я подозреваю, что это не то поведение, которое вы хотели.

Также небольшое замечание по идиомам: обычно используется оператор ++ для объединения двух коллекций и оператор + для добавления одного значения в существующую коллекцию (см. Vector, ArrayBuffer и почти любая коллекция в стандартной библиотеке).

0 голосов
/ 31 июля 2010

В дополнение к другим предложениям, вы можете рассмотреть возможность перехода от Упорядоченного к неявному параметру 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].

(Извините за самый простой пример, мой компьютер вышел из строя, и у меня нет доступной IDE ...)

...