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

Question

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

Каждая коллекция в clojure называется "sequable", но на самом деле только списки и минусы:

user> (seq? {:a 1 :b 2})
false
user> (seq? [1 2 3])
false

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

user> (class (rest {:a 1 :b 2}))
clojure.lang.PersistentArrayMap$Seq

Я не могу делать такие вещи, как:

user> (:b (rest {:a 1 :b 2}))
nil
user> (:b (filter #(-> % val (= 1)) {:a 1 :b 1 :c 2}))
nil

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

Итак, почему коллекции clojure не реализуют интерфейс ISeq напрямую, а все функции seq не возвращают объект того же класса, что и входной объект?

20

clojure sequence seq

Источник

user453735 21 апр '14 в 00:15

4 ответа

Решение

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

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

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

9

Источник

user7671 21 апр '14 в 02:42

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: лень. Объединение в цепочку последовательных функций, таких как map а также filter это очень распространенная операция, и без лени это было бы намного менее производительно и намного более требовательно к памяти.

2

Источник

user523342 21 апр '14 в 02:33

Классы коллекции следуют шаблону фабрики, т.е. вместо реализации 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, ...) { } 
    ...
}

0

Источник

user553209 21 апр '14 в 04:49

Другие вопросы по тегам clojure sequence seq

user232707 21 апр '14 в 07:30 2014-04-21 07:30 · Accepted Answer · 2014-04-21 07:30

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

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

обзор

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

какой-то способ перебора их ввода;
применение функции к каждому элементу ввода;
производя вывод.

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

итерация

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

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

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

Производить вывод

Как отмечалось выше, мы не всегда хотим производить вывод того же типа, что и ввод. Однако, когда мы делаем это, часто лучший способ сделать это эквивалентно заливке 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)).

Резюме

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

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

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