Clojure — последовательности (sequences)

Clojure является диалектом Lisp, поэтому совершенно не удивительно, что работе со списками отводится ключевое место в языке. Правда, в отличии от традиционных диалектов (CL или Scheme), вместо классических двухслотовых списков в Clojure используется абстракция Sequence — «логический список». Фактически, это интерфейс, предоставляющий методы для работы с неизменяемыми, ленивыми и, возможно, бесконечными последовательностями. Данная статья описывает внутреннее устройство этих сущностей.

Суть последовательностей

Начнем с java-интерфейсов. Все структуры в Clojure реализуют clojure.lang.Seqable ^[1]:

public interface Seqable {
    ISeq seq();
}

В свою же очередь clojure.lang.ISeq ^[2] определен как:

public interface ISeq extends IPersistentCollection {
    Object first();
    ISeq next();
    ISeq more();
    ISeq cons(Object o);
}

Тут можно провести аналогию с Iterable, соответственно ISeq — некий аналог Iterator. Главное их отличие в том, что объекты ISeq иммутабельны: его методы возвращают новый экземпляр (может быть, даже другого типа) вместо изменения внутреннего состояния объекта. Все последовательности в Clojure одновременно являются и коллекциями — реализуют унаследованный интерфейс clojure.lang.IPersistentCollection ^[3], а через него и 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-ячейку ^[4].

Для добавления новых элементов вместо 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 ^[5], его реализуют последовательности для массивов и строк. Он определяет метод 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 ^[6] (который, конечно же, реализует ISeq). Объекты этого класса имеют ссылку на функцию (экземпляр IFn), которая при своем вызове должна вернуть собственно новую последовательность (скорее всего тоже ленивую, хотя и не обязательно). При любом обращении к методам LazySeq производится синхронизированный вызов порождающей функции, ее результат сохраняется, а ссылка на саму функцию обнуляется (дабы позволить сборщику мусора ее обработать). Очевидно, что нету никакого способа получить элемент ленивой последовательности, не вычисляя всех предыдущих. Если нужно именно такое поведение — можно воспользоваться макросом delay ^[7].

(nth (map #(print % "") (iterate inc 0)) 5)		;=> 1 2 3 4 5
@(nth (map #(delay (print % "")) (iterate inc 0)) 5)	;=> 5

Порождать ленивые последовательности в своем коде до смешного просто. Достаточно поместить код, вызывающий cons, внутрь макроса lazy-seq ^[8]. Но, на самом деле, даже и этого делать чаще всего не приходится — большинство стандартных фукнций (за очень редким исключением) возвращают именно ленивые коллекции, делая всю «грязную» работу за нас. Есть тут правда и мелкие нюансы.

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

(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 ^[9]. Описывать 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 ^[10].

Вместо заключения

Последовательности в Clojure мощны и удобны. Их несомненный плюс еще в том, что зачастую можно даже не задумываться о таких «мелочах», как ленивость или блочная обработка — Clojure старается это сделать за нас.

Автор: anjensan

Источник ^[11]