Понимание GenericTraversableTemplate и других внутренних элементов коллекции Scala

Я обменивался электронными письмами со знакомым, который был большим поклонником Kotlin, Clojure и Java8, и спросил его, почему бы не Scala. Он предусмотрел множество причин (Scala слишком академичен, слишком много функций, не в первый раз, когда я это слышу, и я думаю, что это очень субъективно) но его самой большой точкой боли было в качестве примера, что ему не нравится язык, на котором он не может понять реализацию основных структур данных, и он привел LinkedList в качестве примера.

Я взглянул на scala.collection.LinkedList и подсчитал то, что я понимаю или немного понимаю.

Может кто-то, кто это хорошо понимает, объясняет GenericTraversableTemplate SeqFactory и GenericCompanion в контексте LinkedList? Для чего они нужны, какое влияние на конечный пользователь у них есть (например, я уверен, что они там по уважительной причине, в чем причина?)

Есть ли они по практической причине? или это уровень абстракции, который мог бы быть упрощен?

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

Ответы

Ответ 1

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

Так как LinkedList теперь устарел, а потому, что Карты обеспечивают лучший пример, я буду использовать TreeMap в качестве примера.

CanBuildFrom

Мотивация такова: если взять TreeMap[Int, Int] и отобразить ее с помощью

case (x, y) => (2 * x, y * y * 0.3d)

получаем TreeMap[Int, Double]. Только этот тип безопасности уже объяснил бы необходимость простые конструкции genericBuilder[X]. Однако, если мы сопоставим его с

case (x, y) => x

получаем Iterable[Int] (точнее: a List[Int]), это уже не карта, тип контейнера изменился. Здесь CBF вступает в игру:

CanBuildFrom[This, X, That]

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

CanBuildFrom[TreeMap[_,_], (X,Y), TreeMap[X,Y]]

во втором случае это будет что-то вроде

CanBuildFrom[TreeMap[_,_], X, Iterable[X]]

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

foo[X1, ..., Xn](x1: X1, ..., xn: Xn): Y

где результат Y зависит от X1,..., Xn, вы можете ввести неявный параметр как следующим образом:

foo[X1, ...., Xn, Y](x1: X1, ..., xn: Xn)(implicit CanFooFrom[X1, ..., Xn, Y]): Y

а затем определите функцию уровня типа X1,..., Xn → Y кусочно, предоставив несколько неявные CanFooFrom's.

LinkedListLike

В определении класса мы видим примерно следующее:

TreeMap[A, B] extends SortedMap[A, B] with SortedMapLike[A, B, TreeMap[A, B]]

Это способ Scala выразить так называемый F-ограниченный полиморфизм. Мотивация такова: предположим, что у нас есть дюжина (или хотя бы двух...) реализаций признака SortedMap[A, B]. Теперь мы хотим реализовать метод withoutHead, он может выглядеть примерно так:

def withoutHead = this.remove(this.head)

Если мы переместим реализацию в SortedMap[A, B], самое лучшее, что мы можем сделать, это следующее:

def withoutHead: SortedMap[A, B] = this.remove(this.head)

Но это самый конкретный тип результата, который мы можем получить? Нет, это слишком расплывчато. Мы хотели бы вернуть TreeMap[A, B], если исходная карта является TreeMap, и CrazySortedLinkedHashMap (или что-то еще...), если оригинал был CrazySortedLinkedHashMap. Вот почему мы перемещаем реализацию в SortedMapLike и даем следующую подпись методу withoutHead:

trait SortedMapLike[A, B, Repr <: SortedMap[A, B]] {
  ...
  def withoutHead: Repr = this.remove(this.head)
}

теперь, поскольку TreeMap[A, B] extends SortedMapLike[A, B, TreeMap[A, B]], тип результата withoutHead - TreeMap[A,B]. То же самое справедливо и для CrazySortedLinkedHashMap: мы возвращаем точный тип. В Java вам нужно либо возвратить SortedMap[A, B], либо переопределить метод в каждом подклассе (который оказался кошмаром обслуживания для богатых функциональностью черт в Scala)

GenericTraversableTemplate

Тип: GenericTraversableTemplate[+A, +CC[X] <: GenTraversable[X]]

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

Вещи вроде foldLeft, reduce, exists здесь не существуют, потому что эти методы относятся только к типу содержимого, а не к типу контейнера.

Вещи вроде flatMap здесь нет, потому что тип контейнера может измениться (опять же, CBF).

Почему это отдельная черта, есть ли фундаментальная причина, почему она существует? Не думаю, что так... Вероятно, можно было бы по-разному сгруппировать godzillion методов. Но это то, что происходит естественным образом: вы начинаете реализовывать черту, и получается, что у нее очень много методов. Поэтому вместо этого вы группируете слабо связанные методы и помещаете их в 10 различных черт с неудобными именами, такими как "GenTraversableTemplate", и их смешивают все их с чертами/классами, где они вам нужны...

GenericCompanion

Это просто абстрактный класс, который реализует некоторые основные функции, которые являются общими для сопутствующих объектов большинства классов коллекций (по сути, он просто реализует очень простые методы factory apply(varargs) и empty).

Например, существует метод apply, который принимает varargs некоторого типа A и возвращает коллекцию типа CC[A]:

Array(1, 2, 3, 4) // calls Array.apply[A](elems: A*) on the companion object
List(1, 2, 3, 4) // same for List

Реализация очень проста, это примерно так:

def apply[A](varargs: A*): CC[A] = {
  val builder = newBuilder[A]
  for (arg <- varargs) builder += arg
  builder.result()
}

Это, очевидно, то же самое для массивов и списков и TreeMaps и почти всего остального, кроме "ограниченных нерегулярных коллекций", таких как Bitset. Так что это обычная функциональность в общем классе предков большинства сопутствующих объектов. Ничего особенного в этом.

SeqFactory

Аналогичен GenericCompanion, но на этот раз более конкретно для последовательностей. Добавляет некоторые общие методы factory, такие как fill() и iterate() и tabulate() и т.д. Опять же, ничего особенно ракета-научного здесь...

Несколько общих замечаний

В общем: я не думаю, что нужно пытаться понять каждый отдельный признак в этой библиотеке. Скорее, нужно попытаться взглянуть на библиотеку в целом. В целом, он имеет очень интересную архитектуру. И по моему личному мнению, это действительно очень эстетичная часть программного обеспечения, но нужно долго смотреть на нее (и пытаться повторно реализовать целую архитектурную схему несколько раз), чтобы понять ее. С другой стороны: например, CBF - это своего рода "шаблон дизайна", который должен быть четко устранен в преемниках этого языка. Вся история с объемом неявного CBF по-прежнему кажется мне полным кошмаром. Но многие вещи казались совершенно непостижимыми вначале, и почти всегда это заканчивалось прозрением (что очень специфично для Scala: для большинства других языков такая борьба обычно заканчивается мыслью "Автор этого - полный идиот" ).