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

Ответ 1

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

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

Обзор

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

• некоторый способ итерации по их вводу;

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

• выводящий результат.

Ясно, что 2. не проблема, если мы можем иметь дело с 1. и 3. Поэтому давайте посмотрим на них.

Итерация

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

В Clojure специализированные типы seq поддерживают состояние обхода и дополнительные функциональные возможности, такие как (1) стек node для сортированных карт и наборов (кроме лучшей производительности, это имеет большую сложность по сравнению с обходами с использованием 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.

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

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

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

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

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

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

Не все это seq; или, рассмотрим редукторы

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

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

Это позволяет нам делать что-то вроде

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

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

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

Резюме

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

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

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

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

• таким образом seq делает отличный примитив;

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

• Таким образом, они тоже создают отличные примитивы.

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

Ответ 2

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

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

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

Ответ 3

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

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 невелик при создании исключений.

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

Ответ 4

Классы сбора следуют шаблону factory, то есть вместо реализации ISeq они реализуют Sequable, т.е. вы можете создавать a 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 what makes it general purpose.
        There is no way it could return A or B objects.
    */
    public static ISeq filter(ISeq coll, ...) { } 
    ...
}