тип параметризация или структурный подтип или

Question

Добрый день! Я довольно новичок в scala, поэтому во время разработки был задан следующий вопрос:

Я хочу описать Дерево классов [T] , где T - параметр типа. Но T должен быть ограничен - у него должно быть 2 метода: def key (): A , где A - некоторый тип, полученный из реализации метода (!) и def union (x: T): T , где T совпадает с параметром типа. Я предполагаю, что это ограничение может быть выражено несколькими способами:

1. определение двух характеристик: одна с помощью метода ключ , а другая с помощью метода union (две характеристики обусловлены независимой природой этих методов)
2. с использованием структурного подтипа
3. что-то еще ...

Так как я могу сделать это каждым способом? и существуют ли другие способы?

Также будет хорошо, если будет легко добавить эти методы для простых типов (таких как String, Int и т. Д.).

Answer 1

Вы можете определить структурный тип для key, но не для union.Структурный тип может не ссылаться на абстрактные типы, определенные вне себя.Так что это не сработает:

trait Tree[T <: { def union(x: T): T }]

Вы можете определить черту, которую должны сделать доступными элементы Tree, однако:

trait TreeVal[T] {
    type A
    def key: A
    def union(x: T): T
}

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

trait Tree[T <: TreeVal[T]]

Это также может быть предложено как неявное преобразование, например так:

class IntVal(v: Int) extends TreeVal[Int] {
    type A = Int
    def key: A = v
    def union(x: Int): Int = x + v
}
implicit def IntIsVal(v: Int): IntVal = new IntVal(v)

class Tree[T <% TreeVal[T]] // must be class, so it can receive parameters

При этом используется то, что называется привязка вида .Ищите это для получения дополнительной информации, но достаточно сказать, что вы сможете обрабатывать все, для чего определено неявное преобразование и в области видимости, как если бы это было TreeVal.Например:

class Tree[T <% TreeVal[T]](node: T, left: Option[Tree[T]], right: Option[Tree[T]]) {
    override def toString = "(%s < %s > %s)" format (left.getOrElse("o"), node.key, right.getOrElse("o"))
}

В качестве альтернативы вы можете использовать его с шаблоном класса типов с некоторыми изменениями:

trait TreeVal[T] {
    type A
    def key(v: T): A
    def union(x: T, y: T): T
}
class Tree[T : TreeVal]  // must be class, so it can receive parameters

Шаблон класса типов использует границы контекста.Ищите это для получения дополнительной информации.Этот стиль обычно предпочтительнее прежнего стиля в настоящее время, потому что он более гибок во многих отношениях.Тем не менее, оба будут работать.

В этом случае можно использовать его так:

implicit object IntVal extends TreeVal[Int] {
    type A = Int
    def key(v: Int) = v
    def union(x: Int, y: Int) = x + y
}

class Tree[T: TreeVal](node: T, left: Option[Tree[T]], right: Option[Tree[T]]) {
    val treeVal = implicitly[TreeVal[T]]
    import treeVal._

    override def toString = "(%s < %s > %s)" format (left.getOrElse("o"), key(node), right.getOrElse("o"))
}

Answer 2

Если вы хотите иметь возможность «добавлять» эти методы к простым типам, возможно, вам лучше использовать классы типов. Узнайте больше о классах типов в этом вопросе и посмотрите на ответ Кевина Райта, который показывает, как «добавить» zero и append метод к Int и String.

Answer 3

Структурные типы реализованы с помощью отражения Java, поэтому они снижают производительность. Это нормально для скриптовых коротких программ или для инициализации, но любое интенсивное использование может поставить вашу программу на колени ...

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

trait Tree[T,A] {
    def key(): A
    def union( x: T ): T
}