Типи колекцій

Незмінність та стійкість

Раніше ми вже згадували про те, що колекції у ClojureScript незмінні (immutable) та стійкі(persistent), але не пояснювали значення цих термінів.

Незмінна структура даних, як свідчить назва, не може бути змінена, а саме: не дозволяється безпосереднє оновлення даних без створення допоміжних структур.

Продемонструємо дію цього принципу у наступному прикладі: спробуємо додати нове значення до вектора за допомогою операції conj (conjoin).

(let [xs [1 2 3]
      ys (conj xs 4)]
  (println "xs:" xs)
  (println "ys:" ys))

;; xs: [1 2 3]
;; ys: [1 2 3 4]
;; => nil

Як бачимо, додавши елемент до вектора xs, ми створили нову версію цього вектора, що містить доданий елемент. При цьому вектор xs залишився в оригінальному стані, бо він незмінний.

Стійка структура даних — це структура, яка при трансформації повертає нову версію самої себе та лишається не зміненою. Завдяки техніці structural sharing (спільне користування структурами) ClojureScript проводить такі трансформації ефективно з точки зору використання пам’яті та швидкості. Спільне користування структурами дозволяє при трансформації не дублювати більшу частину даних, спільних для старої та нової версії. Натомість копіюється лише необхідний для трансформацій значення мінімум даних.

Далі ми розглянемо приклад спільного користування структурами, тому, якщо ви не цікавитеся деталями таких операцій, ви можете перейти одразу до наступного розділу.

Щоб показати роботу спільних структур, порівняємо за допомогою предикати identical? оригінальну та нову версію списку та перевіримо, чи є частини цих двох версій тим самим обʼєктом:

(let [xs (list 1 2 3)
      ys (cons 0 xs)]
  (println "xs:" xs)
  (println "ys:" ys)
  (println "(rest ys):" (rest ys))
  (identical? xs (rest ys)))

;; xs: (1 2 3)
;; ys: (0 1 2 3)
;; (rest ys): (1 2 3)
;; => true

Як видно з прикладу, ми додали у початок списку xs нове значення за допомогою функції cons (construct) і отримали новий список ys, що містить доданий елемент. Далі, ми викликали функцію rest та отримали усі значення списку ys, окрім першого, та переконалися, що ці значення є тим самим об’єктом у пам’яті, яким є список xs. Отож, списки xs та ys мають спільну структурну частину.

Абстракція “послідовність”

Послідовність — одна з найважливіших абстракцій у ClojureScript. Послідовність можна розуміти як список, що може бути створений на основі елементу будь-якого типу колекцій. Це стійка та незмінна структура, як усі типи колекцій. Значна частина функцій стандартної бібліотеки ClojureScript повертає саме послідовності.

Типи колекцій, які можуть створювати послідовності, називаються "seqables" — “спископодібні”. Після виклику функції seq з ними ми отримаємо послідовність. Дві основні операції, які можна виконувати на послідовностях, це first (повернути перше значення) та rest (повернути усі значення, окрім першого). Обидві операції викликають функцію seq з аргументами, які отримують:

(first [1 2 3])
;; => 1

(rest [1 2 3])
;; => (2 3)

Виклик функції seq зі спископодібним об’єктом може привести до різних результатів залежно від того, чи був спископодібний об’єкт порожнім. Відповідно, функція seq поверне або значення nil, або послідовність:

(seq [])
;; => nil

(seq [1 2 3])
;; => (1 2 3)

next — операція, схожа на rest, але next — повертає значення nil, якщо передати їй послідовність, що містить лише один елемент або не містить жодного.

Зауважимо, що у такому випадку порожня послідовність, як результат роботи rest, буде обчислена як логічне true, у той час як nil, що буде результатом роботи next, обчислиться як логічне false. Докладніше про це розповідається у розділі про істинність цієї глави.

(rest [])
;; => ()

(next [])
;; => nil

(rest [1 2 3])
;; => (2 3)

(next [1 2 3])
;; => (2 3)

Використання багатозначності nil

Отож, seq, при виклику з порожньою колекцією повертає значення nil, а nil обчислюється як логічне false. Ми можемо скористатися цим знанням для виявлення порожніх колекцій. Такий прийом називають використанням багатозначності nil (nil-punning).

(defn print-coll
  [coll]
  (when (seq coll)
    (println "Saw " (first coll))
    (recur (rest coll))))

(print-coll [1 2 3])
;; Saw 1
;; Saw 2
;; Saw 3
;; => nil

(print-coll #{1 2 3})
;; Saw 1
;; Saw 3
;; Saw 2
;; => nil

nil не є ані спископодібним елементом, ані послідовністю, але усі функції, які ми розглядали раніше, приймають це значення.

(seq nil)
;; => nil

(first nil)
;; => nil

(rest nil)
;; => ()

Функції для роботи з послідовностями

Функції стандартної бібіліотеки ClojureScript, призначені для трансформування колекцій, створюють послідовності зі своїх аргументів та, в свою чергу, імплементовані за допомогою стандартних операцій на послідовностях, які ми розглянули у попередньому розділі. Завдяки цьому такі функції універсальні, бо ми можемо використати їх із будь-яким типом даних, що може бути перетворений на послідовність. Подивимося на використання функції map із різними спископодібними структурами:

(map inc [1 2 3])
;; => (2 3 4)

(map inc #{1 2 3})
;; => (2 4 3)

(map count {:a 41 :b 40})
;; => (2 2)

(map inc '(1 2 3))
;; => (2 3 4)

ЗАУВАЖЕННЯ: при виклику функції map із колекцією типу “мапа” функція вищого порядку отримує двохелементний вектор, що містить ключ та значення з мапи. Для доступу до ключів та значень у наступному прикладі використовується деструктурування:

(map (fn [[key value]] (* value value))
     {:ten 10 :seven 7 :four 4})
;; => (100 49 16)

Звичайно, така операція може бути проведена у більш ідіоматичний спосіб, якщо натомість передати map спископодібну послідовності, що містить лише значення:

(map (fn [value] (* value value))
     (vals {:ten 10 :seven 7 :four 4}))
;; => (100 49 16)

Можливо, ви вже помітили, що функції, які маніпулюють послідовностями, можуть бути викликані із порожніми колекціями, та навіть із значеннями nil, без помилки. У таких випадках вони лише повертають порожню колекцію.

(map inc [])
;; => ()

(map inc #{})
;; => ()

(map inc nil)
;; => ()

Ми бачили приклади із найбільш часто вживаними функціями, що працюють із колекціями — map, filter та reduce. Та, насправді, простір імен стандартної бібліотеки ClojureScript пропонує велику кількість універсальних операцій на колекціях. Зауважимо, що значна частина операцій, які ми розглядатимемо далі, або працюють зі спископодібними типами, або можуть бути розширені до використання типів, визначених користувачем.

Предиката coll? дозволяє перевірити чи є певний елемент колекцією:

(coll? nil)
;; => false

(coll? [1 2 3])
;; => true

(coll? {:language "ClojureScript" :file-extension "clojure"})
;; => true

(coll? "ClojureScript")
;; => false

Існують схожі за функціональністю предикати для перевірки чи є певне значення послідовністю (seq?) або спископодібним типом (seqable?):

(seq? nil)
;; => false
(seqable? nil)
;; => false

(seq? [])
;; => false
(seqable? [])
;; => true

(seq? #{1 2 3})
;; => false
(seqable? #{1 2 3})
;; => true

(seq? "ClojureScript")
;; => false
(seqable? "ClojureScript")
;; => false

Для колекцій, які можуть бути пораховані протягом фіксованого проміжку часу, доступна операція count. З рядками count теж працює, хоча рядки не належать ані до колекцій, ані до послідовностей, ані до спископодібних.

(count nil)
;; => 0

(count [1 2 3])
;; => 3

(count {:language "ClojureScript" :file-extension "cljs"})
;; => 2

(count "ClojureScript")
;; => 13

Ми можемо отримати порожній варіант певної колекції за допомогою функції empty:

(empty nil)
;; => nil

(empty [1 2 3])
;; => []

(empty #{1 2 3})
;; => #{}

Предиката empty? повертає значення true, якщо її аргумент — порожня колекція:

(empty? nil)
;; => true

(empty? [])
;; => true

(empty? #{1 2 3})
;; => false

Операція conj додає елементи до колекцій. Нові елементи розміщуються на тих позиціях колекції, де це буде найбільш продуктивним для певного типу колекцій. При цьому не кожна колекція має визначений порядок.

Кількість аргументів conj не обмежена. Розглянемо на прикладі:

(conj nil 42)
;; => (42)

(conj [1 2] 3)
;; => [1 2 3]

(conj [1 2] 3 4 5)
;; => [1 2 3 4 5]

(conj '(1 2) 0)
;; => (0 1 2)

(conj #{1 2 3} 4)
;; => #{1 3 2 4}

(conj {:language "ClojureScript"} [:file-extension "cljs"])
;; => {:language "ClojureScript", :file-extension "cljs"}

Схильність до лінивої поведінки

Більшість функцій ClojureScript, що повертають послідовності, не створюють одразу усю послідовність. Натомість вони створюють так звані ліниві послідовності. Ліниві послідовності генерують свій вміст у той момент, коли на нього надходить запит, зазвичай у формі ітерування. Схильність до лінивої поведінки дозволяє не робити більше роботи, ніж необхідно, та надає можливість розглядати потенційно нескінченні послідовності як звичайні.

Розглянемо функцію range, яка повертає цілі числа у межах визначеного інтервалу:

(range 5)
;; => (0 1 2 3 4)
(range 1 10)
;; => (1 2 3 4 5 6 7 8 9)
(range 10 100 15)
;; (10 25 40 55 70 85)

Якщо викликати (range) без аргументів, то результатом буде нескінченна послідовність цілих чисел. Не відтворюйте цю пораду у REPL, якщо не готові чекати на результат дуже довго, бо REPL прагне обчислити вираз цілком.

Ось дещо штучний приклад. Скажімо, ви пишете програму для створення графіків і вам необхідно створити графік рівняння y= 2 x ² + 5. Ви хочете відібрати лише ті значення x, для яких значення y не перевищує 100. Ви можете згенерувати усі числа в діапазоні від 0 до 100, що буде більш ніж достатньо, викликати функцію take-while і передати їй необхідну умову:

(take-while (fn [x] (< (+ (* 2 x x) 5) 100))
            (range 0 100))
;; => (0 1 2 3 4 5 6)

Поглиблене вивчення колекцій

Ми познайомилися із абстракцією послідовності у ClojureScript та з деякими універсальними функціями для роботи з колекціями. Час перейти до вивчення окремих типів колекцій та операцій, які вони підтримують.

Списки

Списки у ClojureScript використовуються переважно для групування символів у програму. На відміну від інших діалектів Лісп, у ClojureScript значна частина синтаксичних конструкцій вимагає використання не списків, а векторів та мап. Код стає менш однорідним, але простішим для читання, тому таке рішення цілком виправдане.

Списки ClojureScript можна розглядати як однобічно пов’язані структури, де кожен вузол містить значення та вказівник на решту списку. Тому найбільш природним (та швидким) способом додавання нових елементів буде вставка на початку списку, адже для додавання нового елемента у кінці списку доведеться пройти весь список. Додавання елементу на початку здійснюється за допомогою функції cons.

(cons 0 (cons 1 (cons 2 ())))
;; => (0 1 2)

Ми вже використовували літерал () у значенні порожнього списку. Через те, що він не містить жодного символу, він не сприймається компілятором як виклик функції. Але не варто забувати: літерали, що містять елементи, слід цитувати, аби ClojureScript не обчислював їх як виклик функції:

(cons 0 '(1 2))
;; => (0 1 2)

Додавання елементів до "голови" списку відбувається за постійний час, тому операція conj додає нові елементи саме на початку.

(conj '(1 2) 0)
;; => (0 1 2)

Списки та інші структури даних у ClojureScript при виклику функцій peek, pop, та conj функціонують як стек. Зверніть увагу: функція conj додає нові елементи до верхівки стеку і таким чином виступає як еквівалент операції push. При виклику зі списком conj додає елементи на початку списку, peek повертає перший елемент списку, pop — усі елементи, окрім першого.

Зауважимо, що операції, які повертають стек — conj та pop — не змінюють тип колекції, з якої був створений стек.

(def list-stack '(0 1 2))

(peek list-stack)
;; => 0

(pop list-stack)
;; => (1 2)

(type (pop list-stack))
;; => cljs.core/List

(conj list-stack -1)
;; => (-1 0 1 2)

(type (conj list-stack -1))
;; => cljs.core/List

Слабке місце списків — ускладнений довільний доступ до елементу за індексом. Списки зберігаються у памʼяті як структури, подібні до однобічно зв'язаного списку, тому доступ до елементу за заданим індексом вимагає лінійного обходу, в ході якого буде знайдене необхідне значення, або виникне помилка виходу індексу за допустимі межі. Ці обмеження характерні також для неіндексованих впорядкованих колекцій — лінивих послідовностей та інших.

Вектори

Вектори належать до найбільш розповсюджених структур даних у ClojureScript. Вони використовуються як синтаксичні конструкти у багатьох випадках, де більш традиційні діалекти Лісп вимагають списків. Прикладом може бути декларація аргументів функцій або оголошення локальних змінних за допомогою let.

Синтаксичний літерал вектора у ClojureScript передбачає прямокутні дужки []. Вектори також можуть бути створені за допомогою операції vector або при виклику функції vec із колекцією:

(vector? [0 1 2])
;; => true

(vector 0 1 2)
;; => [0 1 2]

(vec '(0 1 2))
;; => [0 1 2]

Подібно до списків, вектори являють собою впорядковані колекції різнорідних значень, але списки та вектори ростуть з різних країв: операція conj додає елементи на кінець вектора. Вставка нового елемента у кінці вектора займає фіксований час:

(conj [0 1] 2)
;; => [0 1 2]

Інша відмінність векторів від списків полягає у тому, що вектори — це індексовані колекції, що підтримують довільний доступ до елементів за індексом та безпечне оновлення значень. Для отримання значення за обраним індексом використовується функція nth.

(nth [0 1 2] 0)
;; => 0

Вектори зʼєднують послідовні числові ключі (індекси) та значення, тому ми можемо працювати з ними як із асоційованими структурами даних. ClojureScript має функцію assoc, яка отримує асоційовану структуру даних та множину пар типу "ключ-значення" та створює нову структуру даних, що містить значення, які відповідають зміненим ключам. Нумерація індексів починаються з нуля, що вказує на перший елемент вектора.

(assoc ["cero" "uno" "two"] 2 "dos")
;; => ["cero" "uno" "dos"]

Зверніть увагу, використати функцію assoc можна із ключем, що вже міститься у векторі, або якщо задана позиція буде останньою у векторі:

(assoc ["cero" "uno" "dos"] 3 "tres")
;; => ["cero" "uno" "dos" "tres"]

(assoc ["cero" "uno" "dos"] 4 "cuatro")
;; Error: Index 4 out of bounds [0,3]

Може здатися дивним, але асоційовані структури даних також можуть бути викликані як функції. Вектору можна передати ключ та отримати повʼязане з цим ключем значення. Якщо заданий ключ відсутній, з'явиться помилка:

(["cero" "uno" "dos"] 0)
;; => "cero"

(["cero" "uno" "dos"] 2)
;; => "dos"

(["cero" "uno" "dos"] 3)
;; Error: Not item 3 in vector of length 3

Подібно по списків, вектори також можуть функціонувати як стеки при виклику функцій peek, pop та conj. Але слід зауважити, що на відміну від списків, зростання векторів відбувається з кінця колекції:

(def vector-stack [0 1 2])

(peek vector-stack)
;; => 2

(pop vector-stack)
;; => [0 1]

(type (pop vector-stack))
;; => cljs.core/PersistentVector

(conj vector-stack 3)
;; => [0 1 2 3]

(type (conj vector-stack 3))
;; => cljs.core/PersistentVector

Операції map та filter повертають ліниві послідовності, але дуже часто при роботі з векторами ми очікуємо отримати вже реалізовану послідовність, тому існують еквіваленти таких операцій, що повертають вектори — mapv та filterv. Такі операції працюють швидше, ніж побудова вектора на основі лінивої колекції; також використання mapv та filterv робить ваші наміри більш чіткими.

(map inc [0 1 2])
;; => (1 2 3)

(type (map inc [0 1 2]))
;; => cljs.core/LazySeq

(mapv inc [0 1 2])
;; => [1 2 3]

(type (mapv inc [0 1 2]))
;; => cljs.core/PersistentVector

Мапи

Мапи у ClojureScript використовуються дуже широко. Подібно до векторів, вони виступають як синтаксичний конструкт, у першу чергу для додавання мета-даних до змінних. Будь-яка структура даних у ClojureScript може бути використана як ключі у мапі, але найчастіше представлені ключові слова, бо вони також можуть бути викликані як функції.

Літерал мапи у ClojureScript — це фігурні дужки, що містять пари типу "ключ — значення". Також для створення мап доступна функція hash-map.

(map? {:name "Cirilla"})
;; => true

(hash-map :name "Cirilla")
;; => {:name "Cirilla"}

(hash-map :name "Cirilla" :surname "Fiona")
;; => {:name "Cirilla" :surname "Fiona"}

Звичайні мапи не мають визначеного порядку, тому операція conj додає нову пару типу "ключ-значення" у невизначеній позиції. Операція conj при використанні з мапою має отримати останнім аргументом одну чи більше послідовностей пар "ключ-значення":

(def ciri {:name "Cirilla"})

(conj ciri [:surname "Fiona"])
;; => {:name "Cirilla", :surname "Fiona"}

(conj ciri [:surname "Fiona"] [:occupation "Wizard"])
;; => {:name "Cirilla", :surname "Fiona", :occupation "Wizard"}

У попередньому прикладі порядок був збережений випадково, але за наявності великої кількості ключів ви побачите, що за нормальних умов порядок не зберігається.

Мапи поєднують ключі та значення і, таким чином є асоційованими структурами. Вони дозволяють додавати нові асоціації за допомогою функції assoc та, на відміну від векторів, дозволяють видаляти існуючі асоціації за допомогою функції dissoc. assoc також може актуалізувати значення існуючого ключа. Давайте подивимося на роботу цих функцій:

(assoc {:name "Cirilla"} :surname "Fiona")
;; => {:name "Cirilla", :surname "Fiona"}
(assoc {:name "Cirilla"} :name "Alfonso")
;; => {:name "Alfonso"}
(dissoc {:name "Cirilla"} :name)
;; => {}

Мапи — це функції від своїх ключів, що повертають значення за обраним ключем. На відміну від векторів, мапи повертають значення nil, якщо обраний ключ у даній мапі не знайдений.

({:name "Cirilla"} :name)
;; => "Cirilla"

({:name "Cirilla"} :surname)
;; => nil

ClojureScript також має сортовані хеш-мапи, які за поведінкою схожі на несортовані мапи, але при ітеруванні зберігають порядок. Сортовану мапу із звичайним впорядкуванням можна створити за допомогою функції sorted-map:

(def sm (sorted-map :c 2 :b 1 :a 0))
;; => {:a 0, :b 1, :c 2}

(keys sm)
;; => (:a :b :c)

Для створення мапи із довільним впорядкуванням ми можемо передати функцію sorted-map-by, яка використовується при порівнянні елементів. Функції для порівняння приймають два елементи та повертають значення -1 (якщо перший елемент менший за другий), 0 (якщо елементи рівні) або 1 (якщо перший елемент більший за другий).

(defn reverse-compare [a b] (compare b a))

(def sm (sorted-map-by reverse-compare :a 0 :b 1 :c 2))
;; => {:c 2, :b 1, :a 0}

(keys sm)
;; => (:c :b :a)

Множини

Літеральний синтаксис множин у ClojureScript складається зі значень, огорнутих у фігурні дужки: #{}. Також множини можна створювати за допомогою конструктору set. Множини являють собою невпорядковані колекції значень без повторення.

(set? #{\a \e \i \o \u})
;; => true

(set [1 1 2 3])
;; => #{1 2 3}

Літерали множин не можуть містити дублікатів. Якщо випадково написати літерал множини із дублікатами, виникне помилка:

#{1 1 2 3}
;; clojure.lang.ExceptionInfo: Duplicate key: 1

Існує багато операцій, що доступні на множинах, але ці операції знаходяться у просторі імен clojure.set і мають бути імпортовані. Пізніше ми розглянемо простори імен більш докладно, а поки що вам слід знати, що ми завантажуємо простір імен clojure.set та приєднуємо його до символу s.

(require '[clojure.set :as s])

(def danish-vowels #{\a \e \i \o \u \æ \ø \å})
;; => #{"a" "e" "å" "æ" "i" "o" "u" "ø"}

(def spanish-vowels #{\a \e \i \o \u})
;; => #{"a" "e" "i" "o" "u"}

(s/difference danish-vowels spanish-vowels)
;; => #{"å" "æ" "ø"}

(s/union danish-vowels spanish-vowels)
;; => #{"a" "e" "å" "æ" "i" "o" "u" "ø"}

(s/intersection danish-vowels spanish-vowels)
;; => #{"a" "e" "i" "o" "u"}

Перевага незмінних множин у тому, що вони можуть бути вкладені. У мовах, де множини — змінна структура, при вкладенні можливе дублювання значень. У ClojureScript такого не станеться. Насправді завдяки незмінності усі структури даних ClojureScript можуть бути довільно вкладені.

Як усі колекції, множини також підтримують універсальную операцію conj.

(def spanish-vowels #{\a \e \i \o \u})
;; => #{"a" "e" "i" "o" "u"}

(def danish-vowels (conj spanish-vowels \æ \ø \å))
;; => #{"a" "e" "i" "o" "u" "æ" "ø" "å"}

(conj #{1 2 3} 1)
;; => #{1 3 2}

Множини виступають як доступні лише для читання асоціативні дані, що приєднують значення, яке в них містяться, до себе самих. У ClojureScript, окрім nil та false усі значення обчислюються як логічне true, ми можемо використовувати множини як функції-предикати:

(def vowels #{\a \e \i \o \u})
;; => #{"a" "e" "i" "o" "u"}

(get vowels \b)
;; => nil

(contains? vowels \b)
;; => false

(vowels \a)
;; => "a"

(vowels \z)
;; => nil

(filter vowels "Hound dog")
;; => ("o" "u" "o")

Подібно до мап, множини мають сортований різновид. Сортовану множину можна створити за допомогою функції sorted-set та sorted-set-by, що є аналогами функцій sorted-map та sorted-map-by.

(def unordered-set #{[0] [1] [2]})
;; => #{[0] [2] [1]}

(seq unordered-set)
;; => ([0] [2] [1])

(def ordered-set (sorted-`set [0] [1] [2]))
;; =># {[0] [1] [2]}

(seq ordered-set)
;; => ([0] [1] [2])

Черги

ClojureScript підтримує стійкі та незмінні черги. Черги — найменш розповсюджений тип колекцій. Створити чергу можна за допомогою літерального синтаксису #queue [], але зручних функцій-конструкторів для створення черги не існує.

(def pq #queue [1 2 3])
;; => #queue [1 2 3]

Функція conj додає значення у кінець черги:

(def pq #queue [1 2 3])
;; => #queue [1 2 3]

(conj pq 4 5)
;; => #queue [1 2 3 4 5]

При роботі з чергами варто памʼятати, що стекові операції на чергах не дотримуються звичної семантики, а саме додавання та видалення елементів з одного кінця стеку. Функція pop видаляє значення з початку черги, але conj додає нові елементи на кінець черги.

(def pq #queue [1 2 3])
;; => #queue [1 2 3]

(peek pq)
;; => 1

(pop pq)
;; => #queue [2 3]

(conj pq 4)
;; => #queue [1 2 3 4]

Черги використовуються менш часто, ніж списки та вектори, але знання про їхнє існування у ClojureScript може стати у нагоді в певних випадках.