Clojure является диалектом Lisp, поэтому совершенно не удивительно, что работе со списками отводится ключевое место в языке. Правда, в отличии от традиционных диалектов (CL или Scheme), вместо классических двухслотовых списков в Clojure используется абстракция Sequence — «логический список». Фактически, это интерфейс, предоставляющий методы для работы с неизменяемыми, ленивыми и, возможно, бесконечными последовательностями. Данная статья описывает внутреннее устройство этих сущностей.
Суть последовательностей
Начнем с java-интерфейсов. Все структуры в Clojure реализуют clojure.lang.Seqable:
public interface Seqable {
ISeq seq();
}
В свою же очередь clojure.lang.ISeq определен как:
public interface ISeq extends IPersistentCollection {
Object first();
ISeq next();
ISeq more();
ISeq cons(Object o);
}
Тут можно провести аналогию с Iterable, соответственно ISeq — некий аналог Iterator. Главное их отличие в том, что объекты ISeq иммутабельны: его методы возвращают новый экземпляр (может быть, даже другого типа) вместо изменения внутреннего состояния объекта. Все последовательности в Clojure одновременно являются и коллекциями — реализуют унаследованный интерфейс clojure.lang.IPersistentCollection, а через него и Seqable:
public interface IPersistentCollection extends Seqable {
int count();
IPersistentCollection cons(Object o);
IPersistentCollection empty();
boolean equiv(Object o);
}
Тут мы видим count — подсчет количества элементов. Для последовательностей его сложность очевидно равна O(n). Метод empty возвращает пустую коллекцию такого же типа. Для последовательностей возвращается (). Ну и метод cons добавляет новый элемент.
Для получения объектов ISeq в языке предусмотрена функция seq. Если коллекция пустая, то возвращается nil, если у нас объект Seqable, то у него вызывается метод seq(), в противном случае создается специальная обертка (адаптер). Обертки поддерживаются для массивов, итераторов, java-коллекций (включая Map) и объектов CharSequence (строк). Добавить свой тип в этот список не получится — он «вшит» в java код (не помогут даже протоколы). Разумеется, не стоит изменять массивы (или java-коллекции), если для них создана последовательность. Так, исключение ConcurrentModificationException просто пробрасывается вверх.
В Clojure для работы с последовательностями имеется всего три базовых функции:
- first — взять первый элемент последовательности или nil если она пуста;
- rest — получить «хвост», т.е. последовательность без первого элемента;
- cons — создать новую неизменяемую cons-ячейку.
Для добавления новых элементов вместо cons обычно используется функция conj. Различие между ними в том, что первая всегда создает новую ячейку односвязного списка, а вот результат второй специфичен для каждого конкретного типа коллекций — элемент добавляется в наиболее подходящее место. Для cons-ячеек это начало списка, для векторов — конец, для множеств порядок вообще не определен. Важно отметить, что если мы применили к коллекции seq, то мы теряем информацию о ее типе:
(conj [1 2 3] 4) ;=> [1 2 3 4]
(conj (seq [1 2 3]) 4) ;=> '(4 1 2 3)
К сожалению, имена методов в java-интерфейсах и названия функций не всегда совпадают: функция conj соответствует методу cons, а rest — методу more. С другой стороны, знать имена методов нужно лишь при написании своих коллекций, а это занятие врядли можно отнести к обыденным.
Все стандартные функции автоматически вызывают seq. К примеру, если мы напишем (cons 1 [2 3]), то созданная cons-ячейка на самом деле будет ссылается не на сам вектор [1 2], а на результат (seq [1 2]). Тот же трюк проводится и при работе остальных функций (map, filter и т.п.) — все они работают с последовательностями, хотя и принимают в качестве параметров коллекции.
Собственно, только списки и cons-ячейки напрямую реализуют ISeq:
(seq? '(1 2)) ;=> true
(seq? ()) ;=> true
(seq? (cons 1 nil)) ;=> true
(seq? (cons 1 [2 3])) ;=> true
(seq? [1 2]) ;=> false
(seq? {:a :b}) ;=> false
(seq? #{1 2}) ;=> false
(seq? nil) ;=> false
Поэтому, при итерациях по списку не создается никаких временных объектов. А вот когда пробегаемся по вектору, то для каждого элемента создается по одному временному экземпляру ISeq. В действительности с версии 1.1 дела обстоят немного иначе, но об этом ниже.
Есть еще «никому не известный» интерфейс clojure.lang.IndexedSeq, его реализуют последовательности для массивов и строк. Он определяет метод index() для получения номера текущего элемента (т.е. на каком месте в исходной коллекции находится голова).
(.index (rest (to-array [1 2 3 4]))) ;=> 1
(.index (rest (rest (to-array [1 2 3 4]))) ;=> 2
На практике этот интерфейс нигде не используется (недокументированная возможность). Впрочем, придумать ему применение действительно сложно. Кстати, объекты clojure.lang.APersistenVector$Seq тоже его реализуют. Но беда тут в том, что сейчас seq для векторов возвращает экземпляры clojure.lang.PersistentVector$ChunkedSeq, которые уже не обладают такой сомнительной возможностью.
Ленивые последовательности (lazy sequences)
Важной особенностью последовательностей в Clojure является их потенциальная ленивость. Это означает, что в текущий момент времени не вся последовательность построена, и ее «хвост» еще не создан. В Clojure это часто используют для поточной обработки ввода-вывода.
Реализуется ленивость весьма просто. Существует класс clojure.lang.LazySeq (который, конечно же, реализует ISeq). Объекты этого класса имеют ссылку на функцию (экземпляр IFn), которая при своем вызове должна вернуть собственно новую последовательность (скорее всего тоже ленивую, хотя и не обязательно). При любом обращении к методам LazySeq производится синхронизированный вызов порождающей функции, ее результат сохраняется, а ссылка на саму функцию обнуляется (дабы позволить сборщику мусора ее обработать). Очевидно, что нету никакого способа получить элемент ленивой последовательности, не вычисляя всех предыдущих. Если нужно именно такое поведение — можно воспользоваться макросом delay.
(nth (map #(print % "") (iterate inc 0)) 5) ;=> 1 2 3 4 5
@(nth (map #(delay (print % "")) (iterate inc 0)) 5) ;=> 5
Порождать ленивые последовательности в своем коде до смешного просто. Достаточно поместить код, вызывающий cons, внутрь макроса lazy-seq. Но, на самом деле, даже и этого делать чаще всего не приходится — большинство стандартных фукнций (за очень редким исключением) возвращают именно ленивые коллекции, делая всю «грязную» работу за нас. Есть тут правда и мелкие нюансы.
Так, при своем вычислении, ленивая последовательность фактически превращается в обычный односвязный список, и если хранить ссылку на первый элемент, то могут быть проблемы памятью. Классический пример:
(def all-odds (filter odd? (range)))
(println (nth all-odds 20000000))
Тут мы пытаемся найти 20000000-ое нечетное число. И оно его находит, да вот только все промежуточные экземпляры ISeq остаются в памяти. Правильное решение:
(defn make-all-odds [] (filter odd? (range)))
(println (nth (make-all-odds) 2000000))
Функция rest никогда не возвращает nil, вместо этого она может вернуть пустую последовательность. Если же мы хотим получать nil, то стоит использовать next.
(first '(1 2 3)) ;=> 1
(rest '(1 2 3)) ;=> '(2 3)
(rest '(1)) ;=> ()
(rest ()) ;=> ()
(next '(1)) ;=> nil
(next ()) ;=> nil
Сделано это для большей ленивости. В самом деле, если последовательность ленивая, то в общем случае мы не знаем, есть ли в ней еще элементы или нет. Для проверки этого факта при помощи next нам нужно вычислить как минимум 2 первых элемента: первый мы отбросим, а по наличию второго поймем, нужно ли возвращать nil. Ну а вычисление 2х элементов — это уже явно не то, что нам обычно нужно.
Если ленивое поведение не требуется, то можно полностью вычислить всю последовательность при помощи функций dorun и doall. Первая возвращает исходную последовательность, вторая — nil.
(dorun
(map #(println % "") (range 5)));=> 1 2 3 4 5
Блочные последовательности (chunked sequences)
Ленивые коллекции являются очень мощным инструментом, но на практике мы чаще обрабатываем всю коллекции целиком, а lazy-seq привносит ощутимые накладные расходы. Поэтому в версии 1.1 была проделана важная оптимизация — chunked seqences. Суть проста — при обработке ленивых последовательностей мы имеем дело не с отдельными элементами, а с их группами. При этом жадно вычисляется некоторое количество элементов «на вырост».
Угадайте, что выводит данный код?
(first (map #(print % "") (range 100)))Итак, в Clojure определен специальный интерфейс clojure.lang.IChunkedSeq. Описывать java-часть данного механизма нету большого смысла, поэтому я ее опущу. Интерфейс реализуют только последовательности для векторов. Ну и, как мы увидели, результат фукнции range.
Алгоритм обработки подобных последовательностей:
- проверяем, является ли источник IChunkedSeq (функция chunked-seq?);
- если нет, то выполняем обычную версию алгоритма (поэелементную обработку);
- если да, то берем из последовательности первый блок (функция chunk-first);
- смотрим его размер (функция chunk-size);
- создаем новый блок, туда будем помещать порождаемые элементы (функция chunk-buffer);
- собственно выполняем полезную работу, элементы добавляем в блок (функция chunk-append);
- оборачиваем наш новый блок в ChunkedCons (функция chunk-cons).
Для примера напишем свою реализацию #(filter odd? %). Простой вариант:
(defn filter-odd-1 [a]
(lazy-seq
(when-let [s (seq a)]
(let [f (first s)
r (rest s)]
(if (odd? f)
(cons f (filter-odd-1 r))
(filter-odd-1 r))))))
Расширенный вариант (с поддержкой блоков):
(defn filter-odd-2 [a]
(lazy-seq
(when-let [s (seq a)]
(if (chunked-seq? s)
(let [f (chunk-first s)
c (count f)
b (chunk-buffer c)]
(dotimes [i c]
(let [x (nth f i)]
(when (odd? x)
(chunk-append b x))))
(chunk-cons (chunk b) (filter-odd-2 (chunk-rest s))))
(let [f (first s)
r (rest s)]
(if (odd? f)
(cons f (filter-odd-2 r))
(filter-odd-2 r)))))))
Конечно же, кода стало «немножко» больше, да и на лицо явное дублирование: нам пришлось создавать две отдельных реализации. Но такова цена скорости. К счастью, большинство стандартных функций уже поддерживают chunks в полной мере. Отмечу, что последовательность может состоять как из блоков различной длины (блоки не склеиваются, но иногда урезаются, как в примере выше), так и вовсе быть смешением обычных элементов и блоков.
Что делать, если мы хотим обычную последовательность превратить в блочную? Надо ее просто преобразовать в вектор при помощи функции vec. Обратное уже немного сложнее:
(defn seq1 [s]
(lazy-seq
(when-let [x (seq s)]
(cons (first x) (seq1 (rest x))))))
(first (map println (seq1 (range 1000)))) ;=> 1
(defn seq1 [^clojure.lang.ISeq s]
(reify clojure.lang.ISeq
(first [_] (.first s))
(more [_] (seq1 (.more s)))
(next [_] (let [sn (.next s)] (and sn (seq1 sn))))
(seq [_] (let [ss (.seq s)] (and ss (seq1 ss))))
(count [_] (.count s))
(cons [_ o] (.cons s o))
(empty [_] (.empty s))
(equiv [_ o] (.equiv s o))))
Вполне ожидаемо, что и функция reduce использует преимущества блочных последовательностей. Так, у каждого блока есть специальный метод, выполняющий свертку в java-цикле без создания временных объектов. Вообще, reduce имеет еще и другие оптимизации, все интересующиеся могут посмотреть clojure.core.protocols.
Вместо заключения
Последовательности в Clojure мощны и удобны. Их несомненный плюс еще в том, что зачастую можно даже не задумываться о таких «мелочах», как ленивость или блочная обработка — Clojure старается это сделать за нас.
Автор: anjensan
