Определение неявных границ вида по признакам Scala

Я выполняю упражнение для реализации функционального дерева двоичного поиска в Scala, следуя аналогичной схеме, которую я видел в Haskell. У меня есть структура, которая выглядит примерно так:

trait TreeNode[A] {
    def isLeaf: Boolean
    def traverse: Seq[A]
    ...
}

case class Branch[A](value: A, left: TreeNode[A], right: TreeNode[A]) extends TreeNode[A] { 
   def isLeaf: Boolean = false
   def traverse: Seq[A] = ...
   ... 
}

case class Leaf[A]() extends TreeNode[A] { 
    def isLeaf: Boolean = true
    def traverse: Seq[A] = Seq[A]()
    ... 
}

Я бы хотел поставить ограничение типа на A, чтобы он принимал только объекты, расширяющие Ordered. Похоже, мне нужно определить ограничение представления на A ([A <% Ordered[A]]) на Branch и Leaf, а также на показатель TreeNode. Я не могу это сделать по признаку TreeNode, однако, потому что границы представления не принимаются.

Как я понимаю, <% -style view-bounds являются синтаксическим сахаром для определения implicit, поэтому должен быть способ записи для определения привязки вручную в пределах TreeNode. Я не уверен, как я должен это делать. Я немного огляделся, но не получил намного больше, чем нужно определить какие-то неявные потребности.

Может ли кто-нибудь указать мне в правильном направлении? Я полностью подхожу к этому с неправильного угла?

Ответ 1

Проблема состоит в том, что границы представления, а также границы контекста являются просто синтаксическим сахаром для определенных типов неявных параметров. При применении к параметру типа универсального класса (в отличие от применения к универсальному методу) эти импликации добавляются в конструктор класса. Поскольку признаки не имеют конструктора (или, скорее, имеют только один конструктор без параметров), некуда передавать эти неявные параметры, и, таким образом, границы контекста и границы представления недопустимы для общих признаков. Простейшим решением было бы превратить TreeNode в абстрактный класс.

abstract class TreeNode[A <% Ordered[A]]

Обратите внимание, что по совету Бена Джеймса использование контекста, связанного с Ordering, обычно лучше, чем представление, связанное с Ordered (это более общее). Однако проблема все та же: не будет работать на черту.

Если TreeNode в класс нецелесообразно (скажем, вам нужно смешивать его в разных местах в иерархии типов), вы можете определить абстрактный метод в TreeNode который будет предоставлять неявное значение (типа Ordered[A]) и иметь все классы, которые его расширяют, определяют его. Это, к сожалению, более многословно и явно, но вы не можете сделать намного лучше в этом случае:

trait TreeNode[A] {
  implicit protected def toOrdered: A => Ordered[A]
}

case class Branch[A<%Ordered[A]](value: A, left: TreeNode[A], right: TreeNode[A]) extends TreeNode[A] { 
   protected def toOrdered = implicitly[A => Ordered[A]]
}

case class Leaf[A<%Ordered[A]]() extends TreeNode[A] { 
    protected def toOrdered = implicitly[A => Ordered[A]]
}

Ответ 2

Вы можете указать "доказательства", что A Ordered, требуя абстрактный элемент типа Ordered[A] на trait:

trait TreeNode[A] {
  implicit val evidence: Ordered[A]
}

Затем вы должны были бы предоставить это в любых конкретных подтипах, это доказывает, что A Ordered:

case class Leaf[A](value: A)(implicit ev: Ordered[A]) extends TreeNode[A] {
  val evidence = ev
}

Вместо этого вы можете ограничить A типом, который имеет неявный Ordering[A] - это не отношение наследования; это больше похоже на класс типа haskell. Но реализация в терминах вышеупомянутого метода будет одинаковой.

Ответ 3

Ответ @ben-james отличный, хотелось бы немного его улучшить, чтобы избежать избыточного значения val в классах.

Идея состоит в том, чтобы определить имя параметра неявного конструктора так же, как оно определено в признаке, который содержит неявное значение.

Идея состоит в том, чтобы избежать этой строки:

val evidence = ev

Вот полный пример (суть)

trait PrettyPrinted[A] extends (A => String)

object PrettyPrinted {
  def apply[A](f: A => String): PrettyPrinted[A] = f(_)
}

trait Printable[A] {
  implicit def printer: PrettyPrinted[A]
}

// implicit parameter name is important
case class Person(name: String, age: Int)
                 (implicit val printer: PrettyPrinted[Person])
  extends Printable[Person]

object Person {
  implicit val printer: PrettyPrinted[Person] =
    PrettyPrinted { p =>
      s"Person[name = ${p.name}, age = ${p.age}]"
    }
}

// works also with regular classes
class Car(val name: String)
         (implicit val printer: PrettyPrinted[Car])
  extends Printable[Car]

object Car {
  implicit val printer: PrettyPrinted[Car] =
    PrettyPrinted { c =>
      s"Car[name = ${c.name}]"
    }
}