Почему коллекции clojure не реализуют интерфейс ISeq напрямую?

Это обсуждалось в группе Google Clojure; см., например, ветку семантики карты от февраля этого года. Я позволю себе повторно использовать некоторые моменты, которые я сделал в своем сообщении в этой ветке ниже, добавляя несколько новых.

Прежде чем я продолжу объяснять, почему я думаю, что дизайн с «раздельной последовательностью» является правильным, я хотел бы отметить, что это естественное решение для ситуаций, когда вы действительно хотите получить вывод, аналогичный вводу, но не являясь явным. об этом существует в виде функции fmap из библиотеки contrib algo.generic. (Однако я не думаю, что это хорошая идея использовать его по умолчанию, по тем же причинам, по которым дизайн базовой библиотеки является хорошим.)

Обзор

Ключевым наблюдением, на мой взгляд, является то, что операции последовательности, такие как map, filter и т. д., концептуально делятся на три отдельные задачи:

1. некоторый способ повторения их ввода;

2. применение функции к каждому элементу ввода;

3. производя вывод.

Очевидно, что 2. не вызывает проблем, если мы можем иметь дело с 1. и 3. Итак, давайте посмотрим на них.

Итерация

Для 1. учтите, что самый простой и наиболее производительный способ перебора коллекции обычно не включает выделение промежуточных результатов того же абстрактного типа, что и коллекция. Сопоставление функции с фрагментированной последовательностью с вектором, вероятно, будет намного более эффективным, чем сопоставление функции с последовательностью, создающей «векторы просмотра» (с использованием subvec) для каждого вызова next; последний, однако, является лучшим, что мы можем сделать с точки зрения производительности для next на векторах в стиле Clojure (даже при наличии деревья RRB, которые хороши, когда нам нужна правильная операция подвектора/векторного среза для реализации интересного алгоритма, но делают обходы ужасающе медленными, если мы использовали их для реализации next).

В Clojure специализированные типы seq поддерживают состояние обхода и дополнительные функции, такие как (1) стек узлов для отсортированных карт и наборов (помимо лучшей производительности, это имеет лучшую сложность большого O, чем обходы с использованием dissoc / disj!), (2) текущий индекс + логика для упаковки листовых массивов в куски для векторов, (3) "продолжение" обхода для хэш-карт. Обход коллекции через такой объект просто быстрее, чем любая попытка прохождения через subvec / dissoc / disj.

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

(->> some-vector (map f) (filter p?))

Здесь есть проблема — нет хорошего способа удалить элементы из вектора. (Опять же, RRB-деревья могли бы помочь в теории, но на практике все нарезки и объединения RRB, связанные с созданием «реального вектора» для операций фильтрации, абсолютно снижают производительность.)

Вот аналогичная проблема. Рассмотрим этот конвейер:

(->> some-sorted-set (filter p?) (map f) (take n))

Здесь мы выиграем от лени (или, скорее, от возможности прекратить фильтрацию и сопоставление раньше времени; здесь есть пункт, связанный с редьюсерами, см. ниже). Очевидно, что take можно заменить на map, но не на filter.

Дело в том, что если filter можно неявно преобразовывать в seq, то это нормально и для map; и аналогичные аргументы могут быть сделаны для других функций последовательности. Как только мы привели аргументы для всех — или почти всех — из них, становится ясно, что для seq также имеет смысл возвращать специализированные seq объекты.

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

Создание вывода

Как отмечалось выше, мы не всегда хотим создавать вывод того же типа, что и ввод. Однако, когда мы это делаем, часто лучший способ сделать это — это сделать что-то вроде заливки последовательностью входных данных в пустую выходную коллекцию.

На самом деле нет абсолютно никакого способа сделать лучше карты и наборы. Основная причина заключается в том, что для наборов мощности больше 1 невозможно предсказать мощность вывода отображения функции на набор, поскольку функция может «склеивать» (давать одинаковые результаты для) произвольные входы.

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

Таким образом, если во многих случаях нет способа, скажем, map значительно лучше, чем выполнять seq и into по отдельности, и учитывая, что и seq, и into сами по себе создают полезные примитивы, Clojure делает выбор в том, чтобы раскрыть полезные примитивы и позволяя пользователям создавать их. Это позволяет нам map и into создавать набор из набора, оставляя нам свободу не переходить к этапу into, когда создание набора (или другого набора) не принесет никакой пользы. типа, в зависимости от обстоятельств).

Не все последовательно; или, рассмотрим редукторы

Некоторые проблемы с использованием самих типов коллекций при сопоставлении, фильтрации и т. д. не возникают при использовании редюсеров.

Ключевое различие между редьюсерами и последовательностями заключается в том, что промежуточные объекты, созданные clojure.core.reducers/map и его друзьями, производят только объекты-дескрипторы, которые содержат информацию о том, какие вычисления необходимо выполнить в случае, если редюсер действительно будет сокращен. Таким образом, отдельные этапы вычислений могут быть объединены.

Это позволяет нам делать такие вещи, как

(require '[clojure.core.reducers :as r])

(->> some-set (r/map f) (r/filter p?) (into #{}))

Конечно, нам по-прежнему нужно явно указать наш (into #{}), но это всего лишь способ сказать: «Конвейер редюсеров здесь заканчивается; пожалуйста, представьте результат в виде набора». Мы также можем запросить другой тип коллекции (возможно, вектор результатов; обратите внимание, что сопоставление f с набором вполне может привести к дублированию результатов, и в некоторых ситуациях мы можем захотеть их сохранить) или скалярное значение ((reduce + 0)).

Резюме

Основные моменты таковы:

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

2. seq использует самый быстрый способ итерации;

3. лучший подход к преобразованию набора путем сопоставления или фильтрации включает использование операции в стиле seq, потому что мы хотим очень быстро выполнять итерацию при накоплении вывода;

4. таким образом seq делает большой примитив;

5. map и filter в своем выборе для работы с последовательностями, в зависимости от сценария, могут избежать штрафов за производительность без положительных сторон, выиграть от лени и т. д., но все же могут использоваться для получения результата сбора с into;

6. таким образом, они тоже являются великими примитивами.

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

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

Функции последовательности (карта, фильтр и т. д.) берут "seqable" объект (что-то, что может создавать последовательность), вызывают для него seq для создания последовательности, а затем работают с этой последовательностью, возвращая новую последовательность. Вам решать, нужно ли вам или как повторно собрать эту последовательность обратно в конкретную коллекцию. В то время как векторы и списки упорядочены, наборы и карты — нет, поэтому последовательности над этими структурами данных должны вычислять и сохранять порядок вне коллекции.

Специализированные функции, такие как mapv, filterv, reduce-kv, позволяют вам оставаться «в коллекции», когда вы знаете, что хотите, чтобы операция возвращала в конце коллекцию, а не последовательность.

Последовательности — это упорядоченные структуры, а карты и наборы — неупорядоченные. Две одинаковые по значению карты могут иметь разный внутренний порядок. Например:

user=> (seq (array-map :a 1 :b 2))
([:a 1] [:b 2])
user=> (seq (array-map :b 2 :a 1))
([:b 2] [:a 1])

Нет смысла запрашивать rest карты, потому что это не последовательная структура. То же самое касается набора.

Так что насчет векторов? Они упорядочены последовательно, так что потенциально мы можем сопоставить вектор, и действительно есть такая функция: mapv.

Вы можете спросить: почему это не подразумевается? Если я передам вектор map, почему он не вернет вектор?

Ну, во-первых, это будет означать создание исключений для упорядоченных структур, таких как векторы, а Clojure не очень любит делать исключения.

Но что более важно, вы потеряете одно из самых полезных свойств последовательностей: лень. Объединение в цепочку функций seq, таких как map и filter, является очень распространенной операцией, и без лени это было бы намного менее производительно и требовало бы гораздо больше памяти.

Классы коллекций следуют шаблону фабрики, т. е. вместо реализации ISeq они реализуют Sequable, т. е. вы можете создать ISeq из коллекции, но сама коллекция не является ISeq.

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

Пример в java:

interface ISeq {
    ....
}

class A implements ISeq {

}

class B implements ISeq {

}

static class Helpers {
    /*
        Filter can only work with ISeq, that's what makes it general purpose.
        There is no way it could return A or B objects.
    */
    public static ISeq filter(ISeq coll, ...) { } 
    ...
}