Четыре коллекции

Главная мысль урока: в Clojure четыре коллекции, и у каждой своё обещание. Список дёшево растёт с головы, вектор с хвоста и быстро отдаёт элемент по номеру, мапа ищет по ключу, множество хранит каждое значение один раз. Функции вроде conj, count и get работают со всеми, но каждая коллекция выполняет их так, как дёшево ей самой.

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

Четыре разные скобки, четыре разные коллекции. count понял их все. Дальше разберём, чем они отличаются и почему ни одну нельзя заменить другой.

Четыре литерала

Литерал	Коллекция	Что умеет быстро
'(1 2 3)	список	взять и добавить в голову
[1 2 3]	вектор	добавить в хвост, взять по номеру
{:a 1 :b 2}	мапа	найти значение по ключу
#{1 2 3}	множество	проверить, есть ли элемент

У списка перед скобкой стоит кавычка. Ты помнишь из прошлого урока почему: без неё список это вызов, и Clojure попробует вызвать 1 как функцию. Поэтому в живом коде списки пишут редко, данные почти всегда лежат в векторах.

Мапа это пары «ключ значение» подряд, запятые между парами можно ставить, а можно нет: для Clojure запятая это пробел. Множество выглядит как мапа с решёткой, но хранит одиночные значения, и повтор в литерале #{1 1} это ошибка чтения.

conj кладёт туда, где дешевле

Добавить элемент в любую коллекцию можно одной функцией, conj. Но куда он попадёт, решает сама коллекция:

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

Для журнала это ровно то, что нужно: новая запись сверху без лишней работы. Для очереди дежурных тоже: новый дежурный встаёт в конец.

Брат conj для чтения называется peek, а для удаления pop. Они тоже работают с тем концом, где дёшево:

Отсюда правило: вектор работает как стек с вершиной в конце, список как стек с вершиной в начале.

Общие функции: get, contains?, count

Достать что-то по ключу умеют вектор, мапа и множество. Для вектора ключ это номер элемента с нуля, для множества сам элемент:

Последние три строки показывают, что вектор, мапа и множество сами работают как функции от ключа. Множество в роли функции часто служит проверкой: (visited :cave) вернёт nil, и это ложь.

С contains? есть ловушка, на которой спотыкаются все. Он спрашивает, есть ли такой ключ, а у вектора ключи это номера:

«Есть ли Тим среди дежурных» так не узнать. Для поиска значения в векторе берут some, а если такой вопрос задаётся часто, это сигнал, что данные просятся в множество.

assoc, dissoc, disj

assoc кладёт значение по ключу. Для мапы это новый или заменённый ключ, для вектора замена элемента по номеру. Номер может быть равен длине вектора, тогда элемент допишется в конец, но не дальше:

Из множества удаляют через disj, из мапы через dissoc. Каждый вызов возвращает новую коллекцию, а исходная остаётся прежней. Как это получается без копирования всего подряд, разберём в уроке про персистентность.

into переливает одно в другое

into берёт целевую коллекцию и по очереди делает conj каждого элемента из второй. Поэтому результат всегда того же вида, что и цель, а порядок подчиняется правилу conj:

Вторая строка даёт идиому «убрать повторы»: перелить в множество. Третья переворачивает вектор, потому что каждый следующий элемент лёг в голову списка.

Равенство по значению

В JavaScript [1, 2] === [1, 2] ложно: это два разных массива. В Clojure коллекции сравниваются по содержимому, в каком бы месте программы их ни создали:

Вектор и список равны, если в них те же элементы в том же порядке: оба последовательные. А вот вектор и множество не равны никогда, даже с теми же элементами. Последняя строка показывает следствие равенства по значению: вектор координат годится в ключ мапы. Клетка [3 4] на карте это лагерь, и найти её можно любым вектором [3 4].

Сколько стоит

Операция	Список	Вектор	Мапа	Множество
conj	в голову, O(1)	в хвост, O(1)	O(log₃₂ n)	O(log₃₂ n)
get по ключу или номеру	нет	O(log₃₂ n)	O(log₃₂ n)	O(log₃₂ n)
nth	O(n)	O(log₃₂ n)	нет	нет
count	O(1)	O(1)	O(1)	O(1)

O(log₃₂ n) на практике почти константа: вектору из миллиона элементов нужно четыре шага по дереву. Подробно о том, что такое O и откуда берётся логарифм, рассказано в уроке про базовые алгоритмы.

Как выбрать

Когда ты описываешь новую часть мира игры, задай четыре вопроса по порядку. Первый ответ «да» и выбирает коллекцию.

1. Значения достают по имени, а не по порядку? Это мапа. Герой, цены, настройки.
2. Важно только, есть элемент или нет, и повторы не нужны? Это множество. Посещённые места, флаги, теги.
3. Нужен порядок, номер элемента или добавление в конец? Это вектор. Очередь дежурных, инвентарь, клетки маршрута.
4. Новое всегда кладут в начало и читают с начала? Это список. Журнал свежих событий, стек отмен.

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

Частая ошибка новичка: держать всё в векторах, потому что так привычно после массивов JavaScript. Вектор посещённых мест работает, пока мест десять. Когда их станет тысяча, каждая проверка (some #{place} visited) пройдёт весь вектор, а множество ответит за несколько шагов по дереву. Выбор коллекции в Clojure это не вопрос стиля, а вопрос того, какая операция будет главной.

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

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

Проверь себя

Задание

Дальше

Мапа из этого урока станет главным героем следующего: в ней будут жить герои, предметы и квесты. А почему map над вектором возвращает не вектор, объясним в уроке про абстракцию последовательности.