Не определено неявное упорядочение для A в двоичном дереве

Question

Я пытаюсь разработать бинарную древовидную структуру в Scala, но у меня есть ошибка, которая говорит:

 Error:(15, 54) No implicit Ordering defined for A.

 override def add[A](new_value: A): BinaryTree[A] = new Node(NullNode,new_value,NullNode)

Может кто-нибудь объяснить мне, как я могу это исправить? Вот код, проблема в методе add объекта NullNode , этот метод вызывается, когда вы пытаетесь создать левый элемент для Node .

sealed abstract class BinaryTree[+A] {
  def isEmpty: Boolean
  def isValid: Boolean
  def add[B >: A](new_value: B): BinaryTree[A]
  def isLeaf: Boolean
  def length: Int
}

case object NullNode extends BinaryTree[Nothing] {
  override def isEmpty: Boolean = true
  override def isValid: Boolean = true
  override def isLeaf: Boolean = false
  override def add[A](new_value: A): BinaryTree[A] = new Node(NullNode,new_value,NullNode)
  override def length: Int = 0
}

case class Node[A] (
      var left  : BinaryTree[A],
      var value : A,
      var rigth : BinaryTree[A] )
    ( implicit ord: Ordering[A] ) extends BinaryTree[A] {
  override def isEmpty: Boolean = false
  override def isValid: Boolean = {
    import ord._

    def isValidWith (f: A => Boolean, t: BinaryTree[A]): Boolean = t match {
      case NullNode => true
      case Node(_,valueNode,_) => f(valueNode) && t.isValid
    }

    isValidWith(value < _, left) && isValidWith(value > _, rigth)
  }

  override def isLeaf: Boolean = left.isEmpty && rigth.isEmpty
  override def add[B >: A](new_value: B): BinaryTree[A] = {
    import ord._

    def travel (t: BinaryTree[A]): BinaryTree[A] = t match {
      case NullNode => t.add(new_value)
      case Node (left,nodeValor,rigth) => {
        if (new_value > nodeValor) new Node(travel(left),nodeValor,rigth)
        else if (new_value < nodeValor) new Node(left,nodeValor, travel(rigth))
        else throw new Exception("Valor ya introducido")
      }
    }

    travel(this)
  }
  override def length: Int = {
    def travel (t: BinaryTree[A]): Int = t match {
      case NullNode => t.length
      case Node(left,_,rigth) => left.length + rigth.length + 1
    }

    travel(this)
  }

}

object BinaryTree {
  def apply[A] (value: A)(implicit ord: Ordering[A]): BinaryTree[A] = new Node(NullNode,value,NullNode)
}

На данный момент я пробовал разные реализации, добавляя Упорядочивание к универсальному типу абстрактного класса или делая абстрактный класс a черта , но ничего из этого не сработало, как хотелось бы. Я был бы очень признателен, если бы кто-то мог объяснить, почему эта ошибка.

Answer 1

Основная проблема заключается в том, что нет Ordering[Nothing], что означает, что NullNode нельзя заказать, но тип Node.value должен быть.

Я получил его для компиляциидобавление Ordering к каждой ссылке на метод add() и настройка отношения между типом value с типами узлов left / right.

sealed abstract class BinaryTree[+A] {
  def isEmpty: Boolean
  def isValid: Boolean
  def add[B >: A :Ordering](new_value: B): BinaryTree[B]
  . . .

.,.

case object NullNode extends BinaryTree[Nothing] {
  override def isEmpty: Boolean = true
  override def isValid: Boolean = true
  override def isLeaf: Boolean = false
  override def add[A:Ordering](new_value: A): BinaryTree[A] =
    Node(NullNode, new_value, NullNode)
  . . .

.,.

case class Node[A,C<:A](left  : BinaryTree[C]
                       ,value : A
                       ,rigth : BinaryTree[C]
                       )(implicit ord: Ordering[A]) extends BinaryTree[A] { . . .

.,.

override def add[B >: A :Ordering](new_value: B): BinaryTree[B] = {
  import ord._

  def travel(t: BinaryTree[A]): BinaryTree[B] = t match { . . .

Есть другие проблемы и проблемы с кодом, но по крайней мере это компилируется.