Учебник по дизайну коллекций Scala 2.8

Question

Исходя из моей одышки, какие полезные ресурсы объясняют, как структурирована новая библиотека коллекций Scala 2.8. Мне интересно найти некоторую информацию о том, как следующие вещи сочетаются друг с другом:

• Коллекция классов / черты себя (например, List, Iterable)
• Почему существуют классы Like (например, TraversableLike)
• Для чего нужны сопутствующие методы (например, List.companion)
• Откуда я знаю что implicit объекты находятся в области в данной точке

Answer 1

предисловие

Мартин Одерски рассказывает о коллекции 2.8, которая, вероятно, должна быть вашей первой рекомендацией. Он также был дополнен архитектурными заметками, которые будут особенно интересны тем, кто хочет создавать свои собственные коллекции.

Остальная часть этого ответа была написана задолго до того, как такая вещь существовала (фактически, до самой версии 2.8.0).

Вы можете найти документ об этом как Scala SID # 3. Другие статьи в этой области также должны быть интересны людям, интересующимся различиями между Scala 2.7 и 2.8.

Я приведу цитату из статьи, выборочно, и дополню некоторыми своими мыслями. Есть также некоторые изображения, сгенерированные Matthias на decodified.com, и оригинальные файлы SVG можно найти здесь.

Коллекция классов / черт себя

На самом деле существует три иерархии признаков для коллекций: одна для изменяемых коллекций, другая для неизменяемых коллекций и другая, которая не делает никаких предположений о коллекциях.

Существует также различие между параллельными, последовательными и, возможно, параллельными коллекциями, которые были представлены в Scala 2.9. Я расскажу о них в следующем разделе. Иерархия, описанная в этом разделе, относится исключительно к непараллельным коллекциям.

На следующем рисунке показана неспецифическая иерархия, представленная в Scala 2.8:

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

График для неизменной иерархии:

График для изменчивой иерархии:

Условные обозначения:

Вот сокращенное описание ASCII иерархии коллекции для тех, кто не может видеть изображения.

                    Traversable
                         |
                         |
                      Iterable
                         |
      +------------------+--------------------+
     Map                Set                  Seq
      |                  |                    |
      |             +----+----+         +-----+------+
    Sorted Map  SortedSet   BitSet   Buffer Vector LinearSeq

Параллельные Коллекции

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

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

Были созданы две новые иерархии для поддержки параллельных коллекций.

Иерархия параллельных коллекций имеет те же имена для признаков, но предшествует Par: ParIterable, ParSeq, ParMap а также ParSet, Обратите внимание, что нет ParTraversable, поскольку любая коллекция, поддерживающая параллельный доступ, способна поддерживать более ParIterable черта характера. Он также не имеет некоторых более специализированных черт, присутствующих в последовательной иерархии. Вся эта иерархия находится в каталоге scala.collection.parallel,

Классы, реализующие параллельные коллекции, также различаются ParHashMap а также ParHashSet как для изменяемых, так и для неизменных параллельных коллекций, плюс ParRange а также ParVector реализации immutable.ParSeq а также ParArray реализации mutable.ParSeq,

Существует также другая иерархия, которая отражает черты последовательных и параллельных коллекций, но с префиксом Gen: GenTraversable, GenIterable, GenSeq, GenMap а также GenSet, Эти черты являются родителями как для параллельных, так и для серийных коллекций. Это означает, что метод, принимающий Seq не может получить параллельную коллекцию, но метод, принимающий GenSeq как ожидается, будет работать как с последовательными, так и с параллельными коллекциями.

Учитывая то, как эти иерархии были структурированы, код, написанный для Scala 2.8, был полностью совместим с Scala 2.9 и требовал последовательного поведения. Без переписывания он не может использовать преимущества параллельных коллекций, но требуемые изменения очень малы.

Использование параллельных коллекций

Любую коллекцию можно преобразовать в параллельную, вызвав метод par в теме. Аналогично, любую коллекцию можно преобразовать в последовательную, вызвав метод seq в теме.

Если коллекция уже имеет запрошенный тип (параллельный или последовательный), преобразование не будет. Если один звонит seq на параллельной коллекции или par однако в последовательной коллекции будет создана новая коллекция с запрошенной характеристикой.

Не путай seq, который превращает коллекцию в непараллельную коллекцию, с toSeq, который возвращает Seq создан из элементов коллекции. призвание toSeq на параллельной коллекции вернет ParSeq, а не серийный сборник.

Основные черты

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

В следующих подразделах я кратко опишу основные черты и идею, лежащую в их основе.

Traitable TranceableOnce

Эта черта очень похожа на черту Traversable описано ниже, но с ограничением, что вы можете использовать его только один раз. То есть любые методы, вызываемые на TraversableOnce может сделать его непригодным для использования.

Это ограничение позволяет использовать одни и те же методы для коллекций и Iterator, Это делает возможным метод, который работает с Iterator но не используя Iterator -специфичные методы, позволяющие фактически работать с любой коллекцией, плюс итераторы, если они переписаны для принятия TraversableOnce,

Так как TraversableOnce объединяет коллекции и итераторы, он не появляется на предыдущих графиках, которые касаются только коллекций.

Черта Traversable

На вершине иерархии коллекции есть черта Traversable, Его единственная абстрактная операция

def foreach[U](f: Elem => U)

Операция предназначена для прохождения всех элементов коллекции и применения данной операции f к каждому элементу. Приложение сделано только для его побочного эффекта; фактически любой результат функции f отбрасывается foreach.

Проходимые объекты могут быть конечными или бесконечными. Примером бесконечного проходимого объекта является поток натуральных чисел Stream.from(0), Метод hasDefiniteSize указывает, является ли коллекция, возможно, бесконечной. Если hasDefiniteSize возвращает true, коллекция конечно конечна. Если он возвращает false, коллекция еще не полностью проработана, поэтому она может быть бесконечной или конечной.

Этот класс определяет методы, которые могут быть эффективно реализованы с точки зрения foreach (более 40 из них).

Черта итерируемая

Эта черта объявляет абстрактный метод iterator который возвращает итератор, который возвращает все элементы коллекции один за другим. foreach метод в Iterable реализуется с точки зрения iterator, Подклассы Iterable часто переопределяют foreach прямой реализацией для повышения эффективности.

Учебный класс Iterable также добавляет некоторые редко используемые методы Traversable, который может быть эффективно реализован, только если iterator доступен. Они обобщены ниже.

xs.iterator          An iterator that yields every element in xs, in the same order as foreach traverses elements.
xs takeRight n       A collection consisting of the last n elements of xs (or, some arbitrary n elements, if no order is defined).
xs dropRight n       The rest of the collection except xs takeRight n.
xs sameElements ys   A test whether xs and ys contain the same elements in the same order

Другие черты

После Iterable появляются три базовые черты, которые наследуются от него: Seq, Set, а также Map, Все трое имеют apply метод и все три реализуют PartialFunction черта, но смысл apply отличается в каждом случае.

Я верю смыслу Seq, Set а также Map интуитивно понятен После них классы разбиваются на конкретные реализации, которые предлагают особые гарантии в отношении производительности и методов, которые она делает доступными в результате этого. Также доступны некоторые черты с дальнейшими уточнениями, такими как LinearSeq, IndexedSeq а также SortedSet,

Список ниже может быть улучшен. Оставьте комментарий с предложениями и я это исправлю.

Базовые классы и черты

• Traversable - Базовый класс коллекции. Может быть реализовано только с foreach,
  • TraversableProxy - прокси для Traversable, Просто укажите self в настоящую коллекцию.
  • TraversableView - Traversable с некоторыми не строгими методами.
  • TraversableForwarder - Направляет большинство методов underlying, Кроме toString, hashCode, equals, stringPrefix, newBuilder, view и все вызовы создают новый итерируемый объект того же вида.
  • mutable.Traversable а также immutable.Traversable - то же самое, что Traversable, но ограничивающий тип коллекции.
  • Другие особые случаи Iterable классы, такие как MetaData, существует.
  • Iterable - Коллекция, для которой Iterator может быть создан (через iterator).
    • IterableProxy, IterableView, mutable а также immutable.Iterable,
• Iterator - черта, которая не является потомком Traversable, определять next а также hasNext,
  • CountedIterator - Ан Iterator определяющий count, который возвращает элементы, которые вы видели до сих пор.
  • BufferedIterator - определяет head, который возвращает следующий элемент, не потребляя его.
  • Другие особые случаи Iterator классы, такие как Source, существует.

Карты

• Map - Ан Iterable из Tuple2, который также предоставляет методы для извлечения значения (второй элемент кортежа) по заданному ключу (первый элемент кортежа). Расширяет PartialFunction также.
  • MapProxy - А Proxy для Map,
  • DefaultMap - Черта, реализующая некоторые из Map абстрактные методы.
  • SortedMap - А Map чьи ключи отсортированы.
    • immutable.SortMap
      • immutable.TreeMap - класс, реализующий immutable.SortedMap,
  • immutable.Map
    • immutable.MapProxy
    • immutable.HashMap - класс, реализующий immutable.Map через хеширование ключей.
    • immutable.IntMap - класс, реализующий immutable.Map специализируется на Int ключи. Использует дерево на основе двоичных цифр ключей.
    • immutable.ListMap - класс, реализующий immutable.Map через списки.
    • immutable.LongMap - класс, реализующий immutable.Map специализируется на Long ключи. Увидеть IntMap,
    • Существуют дополнительные классы, оптимизированные для определенного количества элементов.
  • mutable.Map
    • mutable.HashMap - класс, реализующий mutable.Map через хеширование ключей.
    • mutable.ImmutableMapAdaptor - класс, реализующий mutable.Map из существующего immutable.Map,
    • mutable.LinkedHashMap -?
    • mutable.ListMap - класс, реализующий mutable.Map через списки.
    • mutable.MultiMap - класс, принимающий более одного отдельного значения для каждого ключа.
    • mutable.ObservableMap - миксин, который при смешивании с Map публикует события для наблюдателей через Publisher интерфейс.
    • mutable.OpenHashMap - Класс, основанный на алгоритме открытого хеширования.
    • mutable.SynchronizedMap - Mixin, который должен быть смешан с Map предоставить версию с синхронизированными методами.
    • mutable.MapProxy,

Последовательности

• Seq - последовательность элементов. Один предполагает четко определенный размер и повторение элементов. Расширяет PartialFunction также.
  • IndexedSeq - Последовательности, которые поддерживают доступ к элементу O(1) и вычисление длины O(1).
    • IndexedSeqView
    • immutable.PagedSeq - реализация IndexedSeq где элементы создаются по требованию функцией, переданной через конструктор.
    • immutable.IndexedSeq
      • immutable.Range - Разграниченная последовательность целых чисел, закрытая на нижнем конце, открытая на верхнем конце и с шагом.
        • immutable.Range.Inclusive - А Range закрыт на высоком конце, а также.
        • immutable.Range.ByOne - А Range чей шаг 1.
      • immutable.NumericRange - Более общая версия Range который работает с любым Integral,
        • immutable.NumericRange.Inclusive, immutable.NumericRange.Exclusive,
        • immutable.WrappedString, immutable.RichString - Обертки, которые позволяют видеть String как Seq[Char], сохраняя при этом String методы. Я не уверен, в чем разница между ними.
    • mutable.IndexedSeq
      • mutable.GenericArray - Ан Seq на основе массива структуры. Обратите внимание, что "класс" Array это Java Array, который является больше методом хранения в памяти, чем класс.
      • mutable.ResizableArray - Внутренний класс, используемый классами на основе массивов изменяемого размера.
      • mutable.PriorityQueue, mutable.SynchronizedPriorityQueue - Классы, реализующие приоритетные очереди - очереди, в которых элементы удалены из очереди в соответствии с Ordering во-первых, и порядок очередей в последнюю очередь.
      • mutable.PriorityQueueProxy - реферат Proxy для PriorityQueue,
  • LinearSeq - черта для линейных последовательностей, с эффективным временем для isEmpty, head а также tail,
    • immutable.LinearSeq
      • immutable.List - Неизменяемая, односвязная реализация списка.
      • immutable.Stream - Ленивый список. Его элементы вычисляются только по запросу, но запоминаются (сохраняются в памяти) впоследствии. Это может быть теоретически бесконечно.
    • mutable.LinearSeq
      • mutable.DoublyLinkedList - список с изменяемым prev, head (elem) а также tail (next).
      • mutable.LinkedList - список с изменяемым head (elem) а также tail (next).
      • mutable.MutableList - Класс, используемый внутри для реализации классов на основе изменяемых списков.
        • mutable.Queue, mutable.QueueProxy - Структура данных, оптимизированная для операций FIFO (First-In, First-Out).
        • mutable.QueueProxy - А Proxy для mutable.Queue,
  • SeqProxy, SeqView, SeqForwarder
  • immutable.Seq
    • immutable.Queue - класс, реализующий структуру данных, оптимизированную для FIFO (First-In, First-Out). Там нет общего суперкласса обоих mutable а также immutable Очереди.
    • immutable.Stack - класс, реализующий LIFO-оптимизированную (Last-In, First-Out) структуру данных. Там нет общего суперкласса обоих mutableimmutable стеки.
    • immutable.Vector -?
    • scala.xml.NodeSeq - Специализированный класс XML, который расширяет immutable.Seq,
    • immutable.IndexedSeq - Как видно выше.
    • immutable.LinearSeq - Как видно выше.
  • mutable.ArrayStack - класс, реализующий оптимизированную LIFO структуру данных с использованием массивов. Предположительно значительно быстрее, чем обычный стек.
  • mutable.Stack, mutable.SynchronizedStack - Классы, реализующие оптимизированную LIFO структуру данных.
  • mutable.StackProxy - А Proxy для mutable.Stack..
  • mutable.Seq
    • mutable.Buffer - Последовательность элементов, которые могут быть изменены путем добавления, добавления или добавления новых членов.
      • mutable.ArrayBuffer - реализация mutable.Buffer класс с постоянным амортизированным временем для операций добавления, обновления и произвольного доступа. У него есть несколько специализированных подклассов, таких как NodeBuffer,
      • mutable.BufferProxy, mutable.SynchronizedBuffer,
      • mutable.ListBuffer - Буфер, поддерживаемый списком. Он обеспечивает постоянное добавление и добавление времени, при этом большинство других операций являются линейными.
      • mutable.ObservableBuffer - Mixin черта, которая при смешении с Buffer предоставляет уведомления о событиях через Publisher интерфейсы.
      • mutable.IndexedSeq - Как видно выше.
      • mutable.LinearSeq - Как видно выше.

Наборы

• Set - Набор - это коллекция, включающая не более одного объекта.
  • BitSet - Набор целых чисел, хранящихся в виде набора битов.
    • immutable.BitSet
    • mutable.BitSet
  • SortedSet - Набор, элементы которого упорядочены.
    • immutable.SortedSet
      • immutable.TreeSet - реализация SortedSet на основе дерева.
  • SetProxy - А Proxy для Set,
  • immutable.Set
    • immutable.HashSet - реализация Set основанный на элементном хешировании.
    • immutable.ListSet - реализация Set на основе списков.
    • Существуют дополнительные классы множеств для обеспечения оптимизированных реализаций для множеств от 0 до 4 элементов.
    • immutable.SetProxy - А Proxy для неизменного Set,
  • mutable.Set
    • mutable.HashSet - реализация Set основанный на элементном хешировании.
    • mutable.ImmutableSetAdaptor - класс, реализующий изменяемый Set из неизменного Set,
    • LinkedHashSet - реализация Set на основе списков.
    • ObservableSet - Mixin черта, которая, когда смешивается с Set предоставляет уведомления о событиях через Publisher интерфейс.
    • SetProxy - А Proxy для Set,
    • SynchronizedSet - Mixin черта, которая, когда смешивается с Set предоставляет уведомления о событиях через Publisher интерфейс.

---

• Почему существуют классы Like (например, TraversableLike)

Это было сделано для достижения максимального повторного использования кода. Конкретная универсальная реализация для классов с определенной структурой (traversable, map и т. Д.) Выполняется в классах Like. Классы, предназначенные для общего потребления, переопределяют выбранные методы, которые можно оптимизировать.

• Для чего нужны сопутствующие методы (например, List.companion)

Конструктор для классов, т. Е. Объект, который знает, как создавать экземпляры этого класса таким образом, который может использоваться такими методами, как map, создается методом в объекте-компаньоне. Итак, чтобы построить объект типа X, мне нужно получить этот конструктор из сопутствующего объекта X. К сожалению, в Scala нет способа добраться из класса X в объект X. Из-за этого существует метод, определенный в каждом экземпляре X, companion, который возвращает сопутствующий объект класса X.

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

• Как я знаю, какие неявные объекты находятся в области действия в данный момент

Вы не должны заботиться об этом. Они неявные, так что вам не нужно выяснять, как заставить это работать.

Эти последствия существуют, чтобы позволить методам в коллекциях быть определенными в родительских классах, но при этом возвращать коллекцию того же типа. Например, map метод определен на TraversableLike, но если вы использовали на List вы получите List назад.