Абстракция последовательности

Главная мысль урока: функции последовательностей в Clojure не знают про векторы, мапы и строки. Они знают одну абстракцию: последовательность, у которой можно спросить первый элемент и остаток. Любая коллекция умеет превратиться в такую последовательность через seq, поэтому map, filter и first работают со всеми сразу.

Вечером в лагере игре нужно пройтись по трём вещам: отряду, ценам торговца и названию деревни, куда отряд идёт завтра. Отряд это вектор, цены это мапа, название это строка. Три разных типа, и одна функция first справляется со всеми:

У вектора первый элемент это первый герой. У мапы это пара «ключ значение». У строки первая буква. first не проверяет, что ей дали. Она просит у аргумента последовательность и берёт её голову.

seq: превратить что угодно в последовательность

Функция seq берёт коллекцию и возвращает её содержимое последовательностью. Печатается последовательность круглыми скобками, как список:

Две последние строки важны. Пустая коллекция и nil дают одно и то же: nil. У последовательности не бывает «пустой версии», либо в ней есть хотя бы один элемент, либо её нет.

Строка в браузере разбилась на однобуквенные строки, потому что у JavaScript нет отдельного типа для символа. На JVM у строки своя последовательность символов Java:

(prn (seq "Ой"))              ; (\О \й)
(prn (first "Ольховка"))      ; \О
(assert (= \О (first "Ольховка")))
(assert (= "Ольховка" (apply str (seq "Ольховка"))))

Код, который не сравнивает буквы с литералами, работает одинаково в обоих местах. (apply str (reverse "Ой")) склеит буквы обратно в строку и на JVM, и в браузере.

Четыре слова: first, rest, next, cons

Вся абстракция держится на трёх операциях и одном конструкторе:

first берёт голову, rest возвращает всё, кроме головы. rest и next отличаются только на краю: когда после головы ничего нет, rest возвращает пустую последовательность (), а next возвращает nil. Запомнить помогает связь с seq: (next x) это (seq (rest x)).

cons приклеивает элемент к голове и всегда возвращает последовательность, какую бы коллекцию ему ни дали. Это отличает его от conj из урока про коллекции: conj уважает тип коллекции и кладёт туда, где дешевле, а cons про тип забывает.

seq как проверка на пустоту

Раз пустая коллекция превращается в nil, а nil ложен, у seq есть второе назначение. Это идиоматичная проверка «есть ли что-то внутри»:

Пустой вектор в Clojure истинен, ты видел это в уроке про формы. Поэтому (if party ...) не отличит пустой отряд от полного, а (if (seq party) ...) отличит. Есть и empty?, но внутри она устроена как (not (seq coll)). Когда надо проверить и сразу работать с содержимым, пишут (when-let [s (seq coll)] ...).

Мапа как последовательность пар

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

Посмотри на два последних результата. map над мапой вернул не мапу, а последовательность пар. Чтобы получить мапу обратно, пары переливают через into {}. Для частого случая «поменять все значения» есть готовая update-vals, а для ключей update-keys.

Почему map над вектором отдаёт не вектор

Это вопрос, который задаёт каждый, кто пришёл из JavaScript. [1, 2].map(f) в JavaScript возвращает массив. А в Clojure:

map не знает, что ей дали вектор. Она вызвала seq и работает с абстракцией, поэтому и возвращает абстракцию: последовательность. Вектор потерялся по дороге, и conj в результат кладёт в голову, как в список. Это ловушка: код, который ждёт вектор и дописывает в конец, после map начнёт дописывать в начало.

Почему так сделано? Потому что одна map на всё лучше, чем десять: map для векторов, map для мап, map для строк, map для файлов. Кроме того, последовательность, которую вернула map, ленивая: элементы считаются только когда их попросят. Об этом весь урок про лень.

Если нужен вектор, скажи об этом явно: mapv, filterv или (into [] ...).

Что ещё умеет быть последовательностью

Коллекции Clojure это только начало. seq понимает всё, что умеет отдать себя по одному элементу:

range сразу строит последовательность. Отсортированная мапа отдаёт пары в порядке ключей. Массив JavaScript, пришедший из интеропа, тоже обходится first и map, хотя он вообще не коллекция Clojure. На JVM так же ведут себя массивы и коллекции Java, а ещё строки файла, если прочитать их через line-seq. Результат re-seq это последовательность совпадений регулярного выражения.

Каждый такой источник умеет одно: по запросу отдать первый элемент и остаток. Всё остальное, от map до frequencies, построено поверх этого. Поэтому когда ты пишешь функцию над последовательностью, ты пишешь её сразу для всех источников, включая те, что появятся завтра. Лог событий из файла, ответ сервера, строки таблицы: если источник отдаёт seq, твоя функция с ним уже работает.

Обратная сторона: seq от числа или от ключевого слова это ошибка. Последовательность нельзя сделать из того, у чего нет элементов.

Своя функция на четырёх словах

Абстракция окупается, когда пишешь свою функцию. Вот map для одной коллекции через seq, first, rest и cons:

Пять строк, и функция работает с векторами, мапами, строками, множествами и nil, хотя ни про один из этих типов в ней не сказано ни слова. Это та же идея, что итераторы в JavaScript: общий протокол обхода вместо знания о конкретной коллекции. Только в Clojure протокол уже встроен во все коллекции и все функции стандартной библиотеки.

У этой my-map два недостатка, которые настоящая map решает. Она не ленивая: считает всё сразу. И она рекурсивная без recur, поэтому на коллекции из сотни тысяч элементов переполнит стек. Ленивость добавляет lazy-seq, к нему вернёмся в уроке про лень, а про стек поговорим в уроке про рекурсию.

Попробуй руками

В задаче четыре функции, и каждая должна работать с любой коллекцией: своя my-map, проверка на пустоту, подсчёт гласных в строке и прибавка ко всем значениям мапы.

Проверь себя

Задание

Дальше

Последовательность умеет больше, чем first и rest: она может быть бесконечной и считаться по требованию. Как это устроено и где лень кусается, разберём в уроке про лень. А всю библиотеку функций над последовательностями соберём в уроке про map, filter и reduce.