Programovací jazyk Clojure – triky při práci s kolekcemi

Pavel Tišnovský 6. 8. 2015

Ve dvacátém prvním dílu seriálu o programovacím jazyku Clojure i o knihovnách, které jsou pro tento jazyk dostupné, se budeme zabývat popisem některých tipů a triků použitelných při práci se sekvencemi a kolekcemi. Navážeme tak na předchozí část věnovanou především práci s řetězci.

Obsah

1. Programovací jazyk Clojure – triky při práci s kolekcemi

2. Kolekce v programovacím jazyku Clojure

3. Sekvence a rozhraní Seq

4. Funkce pracující se sekvencemi

5. Seznamy

6. Vektory

7. Rozdíly v chování seznamů a vektorů

8. Měnitelné seznamy a vektory (transient collection)

9. Tajemná funkce contains?

10. Jak tedy zjistit existenci prvku v seznamu či vektoru?

11. Odkazy na předchozí části tohoto seriálu

12. Odkazy na Internetu

1. Programovací jazyk Clojure – triky při práci s kolekcemi

V předchozí části tohoto seriálu jsme se seznámili s některými tipy a triky, které je v programovacím jazyce Clojure možné použít při práci s řetězci. Mnohem důležitější pro praktické použití jazyka Clojure je však seznámení se s nabízenými kolekcemi, protože právě kolekce tvoří ve většině aplikací naprostý základ při tvorbě strukturovaných uživatelských datových typů. Jak je ve funkcionálních jazycích zvykem, omezuje se zde využívání tříd a objektů, namísto toho se intenzivně pracuje s neměnitelnými (immutable) a persistentními kolekcemi. Z hlediska dobrého návrhu aplikací i z hlediska případných optimalizací je výhodné se alespoň přibližně seznámit s vnitřní strukturou kolekcí a se složitostí operací prováděných s kolekcemi. V případě potřeby je však možné přímo v Clojure využít i původní měnitelné (mutable) kolekce nabízené knihovnami programovacího jazyka Java, použít tzv. dočasné kolekce (transient collections), popř. existuje i poměrně pěkně zpracované rozhraní umožňující práci s klasickými javovskými poli (arrays).

Programovací jazyk Clojure podporuje jak práci s takzvanými základními typy (což mohou být například pravdivostní hodnoty, celá čísla, numerické hodnoty s plovoucí řádovou čárkou, zlomky, znaky, symboly a keywords), tak i s kolekcemi, s jejichž využitím je možné vytvářet složitější datové struktury. Mezi čtyři základní typy kolekcí, které nalezneme v prakticky každé rozsáhlejší aplikaci, patří seznam (list), vektor (vector), mapa (map) a množina (set). Seznamy přitom mají poněkud výjimečné postavení, neboť se s jejich využitím zapisuje i samotný zdrojový kód, což je mimochodem dnes již velmi tradiční zápis používaný před více než padesáti lety v LISPu a posléze převzatý jak jazykem Scheme, tak i Clojure.

2. Kolekce v programovacím jazyku Clojure

Pro zápis vektorů se používají hranaté závorky, mapy využívají závorky složené a množiny taktéž závorky složené, ovšem před otevírací závorkou se musí napsat křížek (hash, #). V následující tabulce jsou vypsány všechny čtyři typy kolekcí. Kromě seznamů lze ostatní tři složené formy (vektory, mapy, množiny) vytvořit i s využitím vhodného konstruktoru (třetí sloupec), ovšem přesný význam této formy zápisu si uvedeme až v následujících kapitolách:

# Typ kolekce Zápis (syntaktický cukr) Konstruktor
1 Seznam (prvky) '(prvky)
(list prvky)
2 Vektor [prvky] (vector prvky)
(vec kolekce)
3 Mapa {dvojice klíč-hodnota} (hash-map dvojice klíč-hodnota)
(sorted-map dvojice klíč-hodnota)
4 Množina #{unikátní prvky} (hash-set unikátní prvky)
(sorted-set unikátní prvky)

Podívejme se ještě na to, v jakých třídách jsou jednotlivé kolekce deklarovány a jaká rozhraní tyto třídy implementují:

# Kolekce Implementované rozhraní Implementováno v… Predikát
1 Seznam IPersistentList PersistentList.java list?
2 Vektor IPersistentVector PersistentVector.java vector?
3 Mapa IPersistentMap PersistentArrayMap.java
PersistentHashMap.java
PersistentTreeMap.java
map?
4 Množina IPersistentSet PersistentHashSet.java
PersistentTreeSet.java
set?

Vidíme, že některé typy kolekcí mají větší počet implementací, což je ale pochopitelné, protože mapy a množiny mohou být buď seřazené (a interně tedy založené na datové struktuře stromu) či neseřazené (a založené na hashovací mapě).

Při volbě vhodné kolekce, která má tvořit základ uživatelem definované datové struktury ve vyvíjené aplikaci, se vývojář může orientovat i podle toho, jaké rozhraní (ve smyslu programovacího jazyka Java) jednotlivé kolekce implementují. Tím jsou určeny základní vlastnosti každé kolekce:

Rozhraní seznam vektor mapa množina
java.util.Collection ano ano ne ano
java.util.List ano ano ne ne
java.util.Map ne ne ano ne
java.util.Set ne ne ne ano
java.util.RandomAccess ne ano ne ne
java.lang.Iterable ano ano ano ano
java.lang.Comparable ne ano ne ne

Další vlastnosti jsou společné všem kolekcím:

  • Kolekce jsou neměnitelné (immutable), kolekci je tak možné sdílet mezi více vlákny i bez použití zámků či dalších synchronizačních mechanizmů.
  • Kolekce jsou perzistentní.
  • Mezi libovolným počtem kolekcí jazyk zajišťuje sdílení struktury (viz další text), pokud je to možné.
  • U všech kolekcí lze zjistit počet prvků funkcí count.
  • Každá kolekce je mapovatelná na sekvenci a je tedy možné procházet všemi prvky kolekce.
  • Ke každé kolekci je možné „přidat“ nový prvek funkcí conj, výsledkem je nová kolekce.

Funkce společné všem kolekcím:

# Funkce Význam funkce
1 count vrátí počet prvků v kolekci
2 empty? (s otazníkem na konci) vrátí true v případě, že je kolekce prázdná
3 empty (bez otazníku) vrátí prázdnou kolekci stejného typu
4 not-empty pokud není parametrem prázdná kolekce, vrátí se tato kolekce, jinak se vrátí nil
5 distinct? vrací true, pokud se všechny prvky kolekce od sebe liší
6 sequential? vrací true pro vektory, seznamy a sekvence
7 associative? vrací true pro asociativní typy: vektory (klíčem jsou celá čísla), mapy a struktury
8 cons vrátí novou kolekci s přidaným prvkem (odkaz jazyka LISP)
9 pop vrátí kolekci bez prvního prvku (seznamy) nebo bez prvku posledního (vektory)
10 peek vrátí první prvek (seznam), popř. poslední prvek (vektor)
11 nth získání n-tého prvku kolekce
12 first první prvek kolekce
13 rest kolekce bez prvního prvku

3. Sekvence a rozhraní Seq

S kolekcemi velmi úzce souvisí i takzvané sekvence. Tímto termínem se v programovacím jazyce Clojure označuje programové rozhraní, které svými základními možnostmi zhruba odpovídá iterátorům známým z programovacího jazyka Java (iterátory jsou však „kurzory“ v měnitelných kolekcích, kdežto v Clojure jsou kolekce, jak již víme, neměnitelné). V základní knihovně programovacího jazyka Clojure existuje velké množství funkcí, které dokážou pracovat se sekvencemi, ať již se jedná o běžné sekvence (jejichž prvky jsou přímo uloženy v paměti), nebo takzvané líné sekvence (lazy sekvence), které nové prvky vytváří či zjišťují až při konkrétním přístupu na tyto prvky. Mezi tyto funkce patří například sort, sort-by, reverse či flatten. Díky tomu, že všechny kolekce (viz předchozí kapitolu) jsou současně i sekvencemi, lze tyto funkce aplikovat i na kolekce, ovšem ve skutečnosti jsou sekvencemi i další typy objektů – I/O proudy (je možná škoda, že se tímto směrem nevyvinulo API Javy, které je zrovna v případě I/O operací dosti složité), řetězce (což jsou sekvence znaků, viz též předchozí část tohoto seriálu) atd.

Naprostý základ pro práci se sekvencemi tvoří trojice funkcí nazvaných first, rest a next. Funkce first vrací první prvek v sekvenci, popř.  speciální hodnotu nil v případě, že je sekvence prázdná. Funkce restnext vrací zbylé prvky v sekvenci, ovšem liší se tím, jaká hodnota se vrátí ve chvíli, kdy již v sekvenci nezbyly žádné prvky (kromě prvního). V tomto případě vrátí rest prázdnou sekvenci (například prázdný seznam), zatímco funkce next vrátí hodnotu nil. U běžných sekvencí, například seznamů, jsou tyto funkce implementovány přímočaře, ovšem v případě lazy sekvencí se prvky vrácené pomocí funkce first vyhodnocují až za běhu aplikace, například pomocí nějaké generátorové funkce. Tímto způsobem je možné pracovat i s nekonečnými sekvencemi, u nichž už z principu nelze dopředu znát celkový počet prvků atd.

# Funkce z rozhraní Seq Stručný popis
1 (first coll) vrací první prvek sekvence
2 (rest coll) vrací zbytek sekvence (bez prvního prvku), může vrátit i prázdnou sekvenci
3 (next coll) vrací novou sekvenci odvozenou od původní sekvence bez prvního prvku, může vrátit hodnotu nil
3 (cons coll) vrací novou sekvenci, na jejíž první místo byl přidán nový prvek

4. Funkce pracující se sekvencemi

V základní knihovně programovacího jazyka Clojure existuje několik desítek funkcí, které nějakým způsobem pracují se sekvencemi. Poměrně velké množství dostupných funkcí sice může být zpočátku matoucí, ovšem na tomto místě je vhodné si uvědomit, že se autor jazyka Clojure držel poučky, že je lepší mít k dispozici sto odladěných, dokumentovaných a optimalizovaných funkcí pracujících nad jediným datovým typem, než deset různých tříd, kde každá třída implementuje deset různých metod. V této kapitole se s některými funkcemi pracujícími s kolekcemi seznámíme, a to formou jednoduchých příkladů.

Nejprve se podívejme na způsob vytvoření sekvence, a to buď zcela nové sekvence (popř. lazy sekvence) nebo sekvence vzniklé z kolekce:

Sekvence od 0 do devíti (asi nejjednodušší příklad reálného použití funkce range):

user=> (range 10)
(0 1 2 3 4 5 6 7 8 9)

Nulová hodnota je tolerována:

user=> (range 0)
()

Záporná hodnota je taktéž tolerována:

user=> (range -10)
()

Vrací lazy sekvenci od 10 do 19:

user=> (range 10 20)
(10 11 12 13 14 15 16 17 18 19)

Podobný příklad, ale s krokem 2:

user=> (range 10 20 2)
(10 12 14 16 18)

Lze použít i záporný krok:

user=> (range 20 10 -1)
(20 19 18 17 16 15 14 13 12 11)

…různý od 1:

user=> (range 20 10 -2)
(20 18 16 14 12)

(Lazy) sekvenci je možné vytvořit i s využitím funkce repeat:

user=> (repeat 10 1)
(1 1 1 1 1 1 1 1 1 1)
user=> (repeat 10 "a")
("a" "a" "a" "a" "a" "a" "a" "a" "a" "a")

Pro pohled na libovolnou kolekci jako na sekvenci slouží funkce seq:

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

Konečně se dostáváme k zajímavému tématu – k funkci map. V nejjednodušším případě funkce map aplikuje nějakou jinou funkci na všechny prvky nějaké sekvence a výsledkem této operace je nová (lazy) sekvence. Sice to může znít složitě, ale použití funkce map je ve skutečnosti dosti jednoduché, protože již víme, že funkce jsou v Clojure plnohodnotným datovým typem a tudíž je lze předat jako parametr jiné funkci.

Aplikace funkce inc na každý prvek sekvence (zde vektoru):

user=> (map inc [1 2 3 4 5 6 7 8])
(2 3 4 5 6 7 8 9)

U seznamů si musíme dát pozor na jejich quotování:

user=> (map inc '(1 2 3 4 5 6 7 8))
(2 3 4 5 6 7 8 9)

Sekvenci lze samozřejmě vytvořit i pomocí funkcí range a repeat (což jsme si již ukázali výše):

user=> (map inc (range 1 9))
(2 3 4 5 6 7 8 9)

Ještě zajímavější je aplikace nějaké funkce s větší aritou než 1 na dvojici, trojici atd. sekvencí:

user=> (map * [1 2 3 4] [5 6 7 8])
(5 12 21 32)

Dtto se seznamy:

user=> (map * '(1 2 3 4) '(5 6 7 8))
(5 12 21 32)
user=> (map * (range 1 5) (range 5 9))
(5 12 21 32)

Hmm, tato číselná řada se tuším nějak jmenovala…

user=> (map / (range 10) (range 1 10))
(0 1/2 2/3 3/4 4/5 5/6 6/7 7/8 8/9)

Samozřejmě lze použít například i funkci „větší než“:

user=> (map > (range 1 10) (range 10 1 -1))
(false false false false false true true true true)

Popř. compare vracející –1, 0, či 1:

user=> (map compare (range 1 10) (range 10 1 -1))
(-1 -1 -1 -1 -1 1 1 1 1)

5. Seznamy

Programovací jazyk LISP, který je ideovým předchůdcem jazyka Clojure, byl původně založen prakticky pouze na použití seznamů, které byly považovány za zcela univerzální datovou strukturu. V tradičních LISPech jsou seznamy implementované pomocí takzvaných tečka-dvojic (dot-pair), což jsou dvojice prvků, přičemž každý prvek buď může obsahovat nějakou hodnotu nebo obsahuje odkaz na další tečka-dvojici. Běžný seznam pak byl vytvořen jako jednosměrně vázaný lineární seznam složený z tečka-dvojic, kde první prvek ve dvojici obsahoval nějakou hodnotu a druhý prvek pak odkaz na prvek následující. U některých variant programovacího jazyka LISP se navíc obsah každého prvku v tečka dvojici rozděloval na takzvaný tag (řekněme zjednodušeně popis datového typu) a vlastní hodnotu, což bylo z hlediska obsazení operační paměti poměrně efektivní řešení. Pro přístup k prvkům seznamů se používaly dvě funkce pojmenované z historických důvodů car a cdr. Funkce car vracela první prvek seznamu a funkce cdr zbytek seznamu, tj. všechny prvky následující. V Clojure jsou tyto funkce nahrazeny funkcemi pro práci se sekvencemi: first, next a rest, s nimiž jsme se již seznámili.

Podívejme se na použití seznamů v příkladech:

Vytvoření seznamu:

user=> (list 1 2 3)
(1 2 3)
 
user=> '(1 2 3)
(1 2 3)

Mezi funkcí list a quotováním je rozdíl:

user=> (list (* 6 7) 10 10)
(42 10 10)
 
user=> '((*6 7) 10 10)
((*6 7) 10 10)

Další možnosti vytvoření seznamu:

user=> (apply list [1 2 3])
(1 2 3)
 
user=> (into '() [1 2 3])
(3 2 1)

Ukázka sdílení struktury seznamu:

user=> (def seznam '(1 2 3))
#'user/seznam
 
user=> seznam
(1 2 3)
 
user=> (def seznam1 (conj seznam 4))
#'user/seznam1
 
user=> (def seznam2 (conj seznam "hello"))
#'user/seznam2
 
user=> seznam
(1 2 3)
 
user=> seznam1
(4 1 2 3)
 
user=> seznam2
("hello" 1 2 3)

Operace rest a pop se někdy chovají odlišně (konkrétně při aplikaci na prázdný seznam):

user=> (rest seznam)
(2 3)
 
user=> (pop seznam)
(2 3)
 
user=> (type (rest seznam))
clojure.lang.PersistentList
 
user=> (type (pop seznam))
clojure.lang.PersistentList
 
user=> (rest '())
()
 
user=> (pop '())
IllegalStateException Can't pop empty list  clojure.lang.PersistentList$EmptyList.pop (PersistentList.java:178)

Výsledky predikátů a funkce pro zjištění typu:

user=> (list? seznam)
true
 
user=> (seq? seznam)
true
 
user=> (type seznam)
clojure.lang.PersistentList
 
user=> (def x (range 1 10))
#'user/x
 
user=> (list? x)
false
 
user=> (seq? x)
true
 
user=> (type x)
clojure.lang.LazySeq

6. Vektory

V programovacím jazyku Clojure se na mnoha místech seznamy nahrazují za vektory, protože práce s vektory může být více efektivní. Vektor můžeme považovat za jednorozměrné pole hodnot libovolných typů, takže by se mohlo zdát, že složitost přístupu k jeho prvkům bude konstantní O(N). Ve skutečnosti jsou však vektory interně implementovány poněkud složitějším (a velmi zajímavým) způsobem a to především z toho důvodu, aby bylo snadné k vektorům připojovat další prvky – tak vznikne nový vektor, ovšem původní vektor musí samozřejmě zůstat zachovaný. Proto se v Clojure (a v některých dalších moderních programovacích jazycích) používají pro implementaci vektorů takzvané RRB-Stromy (RRB-Trees, Relaxed Radix Balanced Trees). V Clojure jsou použity (vyvážené) RRB-stromy, které mají v každém listu uloženo jednorozměrné pole o délce 32 prvků. Pokud se pracuje s kratším vektorem, je pro jeho uložení použit strom pouze s jedním listem a tudíž je vektor skutečně reprezentován jednorozměrným polem (ve skutečnosti se vedle vlastního stromu používá ještě pomocné pole tail, pro jednoduchost však jeho roli v tomto textu poněkud zanedbáme).

U delších vektorů se v 32prvkovém poli uloženém v kořenu stromu nenachází přímo prvky vektoru, ale reference na další listy, z nichž každý opět obsahuje 32prvkové pole. To znamená, že vektor s až 1024 prvky může být uložen ve stromu o výšce 1, ve stromu o výšce 2 je celkový (možný) počet prvků vektoru roven 32768 (1024 listů á 32 prvků) atd. Operace vrácení n-tého prvku má tedy složitost O(log32N), což sice není konstantní složitost O(1), ale pro vektory běžných délek můžeme tuto složitost taktéž považovat za konstantní. Předností vektorů je tedy rychlejší přístup k jeho prvkům, ale nesmíme zapomenout ani na paměťové nároky – vektory interně potřebují mnohem méně referencí, než je tomu u seznamů, tudíž i paměťové nároky budou nižší, a to zejména na 64bitových systémech; samozřejmě pokud zde uživatelé nepovolí použití komprimovaných ukazatelů (compressed oops).

Opět se podívejme na základní příklady:

Několik způsobů vytvoření vektoru:

user=> [1 2 3]
[1 2 3]
 
user=> (vector 1 2 3)
[1 2 3]
 
user=> (vec '(1 2 3))
[1 2 3]
 
user=> (vec (range 1 10))
[1 2 3 4 5 6 7 8 9]
 
user=> (into [] (range 1 10))
[1 2 3 4 5 6 7 8 9]

Funkce conj, pop a rest:

user=> (def vektor [1 2 3])
#'user/vektor
 
user=> (conj vektor 4)
[1 2 3 4]
 
user=> (pop vektor)
[1 2]
 
user=> (rest vektor)
(2 3)
 
user=> (type (rest vektor))
clojure.lang.PersistentVector$ChunkedSeq
 
user=> (type (pop vektor))
clojure.lang.PersistentVector

Výsledky predikátů a funkce pro zjištění typu:

user=> (vector? vektor)
true
 
user=> (list? vektor)
false
 
user=> (seq? vektor)
false
 
user=> (sequential? vektor)
true
 
user=> (type vektor)
clojure.lang.PersistentVector

7. Rozdíly v chování seznamů a vektorů

Programovací jazyk LISP, z něhož je jazyk Clojure do značné míry odvozen (či možná lépe řečeno inspirován), byl původně založen prakticky pouze na použití seznamů, které se využívaly jak pro ukládání dat, tak i pro reprezentaci vlastního programu, protože program (jeho funkce) lze reprezentovat jako seznam seznamů (tato vlastnost se označuje termínem homoikonicita/homoiconicity). Stejným způsobem se seznamy používají i v jazyku Scheme a nejinak je tomu i v programovacím jazyku Clojure, jenž však, jak již víme z předchozích kapitol, kromě seznamů poměrně intenzivně používá i vektory (například parametry funkce se zapisují do vektorů, speciální forma let používá vektory, stejně jako makro for atd.), což musí mít svoje opodstatnění. Seznamy a vektory sice na první pohled vypadají jako vzájemně zaměnitelné datové typy, ve skutečnosti se však od sebe dosti podstatným způsobem odlišují, a to především svojí vnitřní strukturou, z níž přímo vyplývají i operace, které lze s těmito kolekcemi provádět a v neposlední řadě i složitost jednotlivých operací, která nás dnes taktéž zajímá.

Jeden z rozdílů mezi seznamy a kolekcemi spočívá v tom, že prvky vektorů je možné číst jako přímou sekvenci i jako sekvenci otočenou (od posledního prvku k prvku prvnímu). Nad vektorem lze tedy zavolat funkci seqrseq, zatímco u seznamů pouze funkci seq – prvky lze číst pouze od začátku seznamu do konce. Další rozdíl mezi seznamy a vektory spočívá v odlišném chování funkce conj, kterou lze použít k vytvoření kopie původní kolekce doplněné o nové prvky. U seznamů se prvky přidávají na jeho začátek, zatímco u vektorů je tomu přesně naopak – vrácen je nový vektor s prvky přidanými na jeho konci. Podobně se liší chování funkcí pop a peek. Shrňme si nyní jednotlivé funkční rozdíly mezi seznamy a vektory přehledně do tabulky:

# Funkce Seznam Vektor
1 seq podporováno podporováno
2 rseq není podporováno podporováno
3 conj nové prvky + původní seznam vektor + nové prvky
4 pop seznam bez prvního prvku vektor bez posledního prvku
5 peek první prvek seznamu poslední prvek vektoru
5 first první prvek seznamu první prvek vektoru
6 last poslední prvek seznamu poslední prvek vektoru
7 nth n-tý prvek seznamu n-tý prvek vektoru
8 count počet prvků seznamu počet prvků vektoru

Důležité je při optimalizaci aplikací i porovnání výpočetní složitosti některých funkcí z předchozí tabulky, protože právě odlišná složitost může výrazným způsobem ovlivnit výkonnost celé aplikace, zejména tehdy, pokud se budou používat kolekce s velkým množstvím prvků. Zajímavé je, že funkce count má v obou případech konstantní složitost: O(1). To znamená, že v Clojure nemá smysl počítat počet prvků seznamu s využitím rekurzivní funkce, což je jeden z oblíbených školních příkladů používaných při výuce LISPu :-) Naproti tomu funkce nth se sice u obou typů kolekcí chová stejně, má však výrazně odlišnou složitost: O(n) v případě seznamů (lineární složitost) a O(log32N) v případě vektorů (logaritmická složitost). U krátkých vektorů (do 32 prvků) je složitost konstantní a i u delších vektorů je počet kroků nutných pro získání n-tého prvku velmi malý (například dva kroky pro vektory o délce přibližně 1000 prvků atd.). Složitost funkce peek je v případě vektoru taktéž rovna O(log32N), na rozdíl od funkce last se složitostí O(N) – v případě vektorů tedy vždy používejte peek!

# Funkce Seznam Vektor
1 count O(1) O(1)
2 nth O(N) O(log32N)
3 pop O(1) O(log32N)
4 peek O(1) O(log32N)
5 first O(1) O(1)
6 last O(N) O(N)

Povšimněte si, že vektory ve skutečnosti neodpovídají složitostí některých funkcí běžně chápaným vektorům-jednorozměrným polím. Je tomu tak z toho důvodu, že v Clojure jsou vektory implementovány odlišným způsobem a to zejména proto, aby bylo možné jednoduše implementovat funkci conj, tj. aby se již vytvořená datová struktura mohla sdílet mezi větším množstvím vektorů (to je možné i díky jejich neměnnosti).

8. Měnitelné seznamy a vektory (transient collection)

Jak jsme se již několikrát zmínili v předchozích kapitolách, jsou všechny základní kolekce nabízené programovacím jazykem Clojure neměnné a perzistentní. V některých algoritmech z praxe je však nutné kolekci vytvářet postupně (prvek po prvku) popř. modifikovat hodnoty jednotlivých prvků. V tomto případě je možné použít takzvané krátkodobé kolekce (transient collection). Slovo „transient“ naznačuje, že s takovou kolekcí by se mělo v ideálním případě pracovat pouze v rámci jediné funkce, přičemž výsledkem této funkce by měla být již očekávaná neměnná a perzistentní kolekce. Myšlenka je to vlastně logická – to, co se děje v rámci jedné funkce, je lokální změna stavu, která se neprojeví ani v dalších funkcích ani v dalších vláknech, takže zde je povolena změna kolekce. Jak se ovšem jednou z funkce vrátí nově vytvořená kolekce, již se nesmí jednat o měnitelnou datovou strukturu. Předností jsou pak značně rychlejší operace při práci s krátkodobými kolekcemi.

Při práci s tranzientními :-) kolekcemi se používají tyto nové funkce:

  • transient pro vrácení perzistentní kolekce z kolekce tranzientní (původní kolekce se nemění)
  • persistent! pro převod tranzientní kolekce na kolekci perzistentní (neprovádí se kopie)
  • assoc! pro změnu prvku tranzientní kolekce
  • conj! pro přidání prvku do tranzientní kolekce

Podívejme se na poněkud umělý příklad funkce pro vytvoření vektoru zadané délky:

(defn x1
    [length]
    (let [vektor (atom [])]
        (doseq [x (range 0 length)]
            (reset! vektor (conj @vektor x)))
            @vektor))

Tuto funkci je možné vylepšit použitím swap!, nicméně se stále bude aplikovat conj na již existující vektor:

(defn x2
    [length]
    (let [vektor (atom [])]
        (doseq [x (range 0 length)]
            (swap! vektor conj x))
            @vektor))

Řešením je třetí verze nepoužívající atomy ale tranzientní kolekci:

(defn x3
    [length]
    (let [vektor (transient [])]
        (doseq [x (range 0 length)]
            (conj! vektor x))
            (persistent! vektor)))

Povšimněte si, že výslednou hodnotou je běžná perzistentní kolekce!

Příklad z praxe – získání setříděné množiny obsahující jména produktů přečtených z knížek:

(defn get-products
    "Returns sorted set of all products"
    []
    (let [products (transient #{})]
        (doseq [book books/books]
            (let [book-val (val book)
                  book-product-name (nth book-val 3)
                  book-product-ver  (nth book-val 4)
                  book-product (str book-product-name " " book-product-ver)]
                (conj! products book-product)))
        (into (sorted-set) (persistent! products))))

9. Tajemná funkce contains?

„Indeed, contains? has to be the most misleadingly named function in Clojure :)“

Při práci s kolekcemi je mnohdy nutné zjistit, zda daná kolekce obsahuje nějaký prvek. První funkcí, kterou většina vývojářů (včetně autora tohoto článku :-) intuitivně ale chybně použije, je funkce-predikát nazvaná contains?. Podle názvu této funkce by se mohlo zdát, že v případě, že kolekce obsahuje zadaný prvek, vrátí se pravdivostní hodnota true, v opačném případě pak hodnota false či nil. Ve skutečnosti tomu však tak není, protože predikát contains? slouží ke zjištění, zda daná kolekce obsahuje zadaný klíč, nikoli prvek! Co to znamená v praxi? Tuto funkci vůbec nejde použít pro seznamy, protože se vyhodí výjimka typu IllegalArgumentException. Dále, pokud je tato funkce použita pro vektory, bude sice fungovat (nevyhodí se výjimka), ale vracet se bude true pouze tehdy, když funkci contains? předáme správný klíč, přičemž ve vektorech jsou klíče celočíselné hodnoty (jedná se o indexy prvků).

user=> (doc contains?)
-------------------------
clojure.core/contains?
([coll key])
  Returns true if key is present in the given collection, otherwise
  returns false.  Note that for numerically indexed collections like
  vectors and Java arrays, this tests if the numeric key is within the
  range of indexes. 'contains?' operates constant or logarithmic time;
  it will not perform a linear search for a value.  See also 'some'.

Podívejme se pro jistotu na několik příkladů, na nichž bude chování popisované funkce patrné:

user=> (def seznam '("a" "b" "c"))
#'user/seznam
 
user=> (def vektor ["a" "b" "c"])
#'user/vektor
 
 
user=> (contains? seznam "b")
IllegalArgumentException contains? not supported on type: clojure.lang.PersistentList  clojure.lang.RT.contains (RT.java:724)
 
 
user=> (contains? vektor "b")
false
 
user=> (contains? vektor 1)
true
 
user=> (contains? vektor 10)
false

Chování funkce contains? začne být intuitivní ve chvíli, kdy je použita pro vyhledání prvků (podle klíčů) v mapě či v množině:

user=> (def mapa {"a" "acko"  "b" "becko"   "c" "cecko"})
#'user/mapa
 
user=> (def mnozina #{"a" "b" "c"})
#'user/mnozina
 
 
user=> (contains? mapa "a")
true
 
user=> (contains? mapa "acko")
false
 
user=> (contains? mnozina "a")
true
 
user=> (contains? mnozina "z")
false

Výsledkem je tedy zjištění, že funkce contains? má praktický význam jen při práci s mapami a množinami, nikoli při práci se seznamy a vektory.

widgety

10. Jak tedy zjistit existenci prvku v seznamu či vektoru?

Jakou funkci tedy mají vývojáři použít namísto contains? ve chvíli, kdy potřebují zjistit, zda seznam či vektor obsahuje nějaký prvek? Samozřejmě je možné si napsat nějakou funkci vlastní, ovšem již ve standardní knihovně se nachází použitelná funkce nazvaná some. Této funkci stačí předat množinu hledaných prvků (klidně se může jednat o jednoprvkovou množinu) a seznam/vektor. Pokud se žádný prvek z předané množiny v kolekci nenachází, vrátí se hodnota nil (zpracovávaná většinou stejně jako false), pokud se prvek či prvku najdou, je jeden z prvků vrácen (u seznamů a vektorů jde o první prvek). Připomeňme si, že v Clojure je jakákoli hodnota odlišná od nil či false chápána jako pravda, takže náš problém s vyhledáním prvku nebo prvků je vyřešen.

user=> (doc some)
-------------------------
clojure.core/some
([pred coll])
  Returns the first logical true value of (pred x) for any x in coll,
  else nil.  One common idiom is to use a set as pred, for example
  this will return :fred if :fred is in the sequence, otherwise nil:
  (some #{:fred} coll)

Opět se podívejme na několik příkladů, v nichž se funkce some používá:

user=> (def seznam '("a" "b" "c"))
#'user/seznam
 
user=> (def vektor ["a" "b" "c"])
#'user/vektor
 
 
user=> (some #{"a"} seznam)
"a"
 
user=> (some #{"x"} seznam)
nil
 
user=> (some #{"a"} vektor)
"a"
 
user=> (some #{"x"} vektor)
nil
 
 
user=> (some #{"a" "c"} seznam)
"a"
 
user=> (some #{"a" "c"} vektor)
"a"
 
user=> (some #{"c" "a"} seznam)
"a"
 
user=> (some #{"c" "a"} vektor)
"a"
 
 
user=> (some #{42 "a"} seznam)
"a"
 
user=> (some #{42 "a"} vektor)
"a"

11. Odkazy na předchozí části tohoto seriálu

  1. Leiningen: nástroj pro správu projektů napsaných v Clojure
    http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure/
  2. Leiningen: nástroj pro správu projektů napsaných v Clojure (2)
    http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure-2/
  3. Leiningen: nástroj pro správu projektů napsaných v Clojure (3)
    http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure-3/
  4. Leiningen: nástroj pro správu projektů napsaných v Clojure (4)
    http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure-4/
  5. Leiningen: nástroj pro správu projektů napsaných v Clojure (5)
    http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure-5/
  6. Leiningen: nástroj pro správu projektů napsaných v Clojure (6)
    http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure-6/
  7. Programovací jazyk Clojure a databáze (1.část)
    http://www.root.cz/clanky/programovaci-jazyk-clojure-a-databaze-1-cast/
  8. Pluginy pro Leiningen
    http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure-pluginy-pro-leiningen/
  9. Programovací jazyk Clojure a knihovny pro práci s vektory a maticemi
    http://www.root.cz/clanky/programovaci-jazyk-clojure-a-knihovny-pro-praci-s-vektory-a-maticemi/
  10. Programovací jazyk Clojure a knihovny pro práci s vektory a maticemi (2)
    http://www.root.cz/clanky/programovaci-jazyk-clojure-a-knihovny-pro-praci-s-vektory-a-maticemi-2/
  11. Programovací jazyk Clojure: syntéza procedurálních textur s využitím knihovny Clisk
    http://www.root.cz/clanky/programovaci-jazyk-clojure-synteza-proceduralnich-textur-s-vyuzitim-knihovny-clisk/
  12. Programovací jazyk Clojure: syntéza procedurálních textur s využitím knihovny Clisk (2)
    http://www.root.cz/clanky/programovaci-jazyk-clojure-synteza-proceduralnich-textur-s-vyuzitim-knihovny-clisk-2/
  13. Programovací jazyk Clojure: syntéza procedurálních textur s využitím knihovny Clisk (dokončení)
    http://www.root.cz/clanky/programovaci-jazyk-clojure-synteza-proceduralnich-textur-s-vyuzitim-knihovny-clisk-dokonceni/
  14. Seesaw: knihovna pro snadnou tvorbu GUI v jazyce Clojure
    http://www.root.cz/clanky/seesaw-knihovna-pro-snadnou-tvorbu-gui-v-jazyce-clojure/
  15. Seesaw: knihovna pro snadnou tvorbu GUI v jazyce Clojure (2)
    http://www.root.cz/clanky/seesaw-knihovna-pro-snadnou-tvorbu-gui-v-jazyce-clojure-2/
  16. Seesaw: knihovna pro snadnou tvorbu GUI v jazyce Clojure (3)
    http://www.root.cz/clanky/seesaw-knihovna-pro-snadnou-tvorbu-gui-v-jazyce-clojure-3/
  17. Programovací jazyk Clojure a práce s Gitem
    http://www.root.cz/clanky/programovaci-jazyk-clojure-a-prace-s-gitem/
  18. Programovací jazyk Clojure a práce s Gitem (2)
    http://www.root.cz/clanky/programovaci-jazyk-clojure-a-prace-s-gitem-2/
  19. Programovací jazyk Clojure – triky při práci s řetězci
    http://www.root.cz/clanky/programovaci-jazyk-clojure-triky-pri-praci-s-retezci/

12. Odkazy na Internetu

  1. Clojure home page
    http://clojure.org/
  2. Clojure (downloads)
    http://clojure.org/downloads
  3. Clojure Sequences
    http://clojure.org/sequences
  4. Clojure Data Structures
    http://clojure.org/data_structures
  5. The Structure and Interpretation of Computer Programs: 2.2.1 Representing Sequences
    http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec2.2.1
  6. The Structure and Interpretation of Computer Programs: 3.3.1 Mutable List Structure
    http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec3.3.1
  7. Clojure – Functional Programming for the JVM
    http://java.ociweb.com/mar­k/clojure/article.html
  8. Clojure quick reference
    http://faustus.webatu.com/clj-quick-ref.html
  9. 4Clojure
    http://www.4clojure.com/
  10. ClojureDoc (rozcestník s dokumentací jazyka Clojure)
    http://clojuredocs.org/
  11. Clojure (na Wikipedia EN)
    http://en.wikipedia.org/wiki/Clojure
  12. Clojure (na Wikipedia CS)
    http://cs.wikipedia.org/wiki/Clojure
  13. SICP (The Structure and Interpretation of Computer Programs)
    http://mitpress.mit.edu/sicp/
  14. Pure function
    http://en.wikipedia.org/wi­ki/Pure_function
  15. Funkcionální programování
    http://cs.wikipedia.org/wi­ki/Funkcionální_programová­ní
  16. Čistě funkcionální (datové struktury, jazyky, programování)
    http://cs.wikipedia.org/wi­ki/Čistě_funkcionální
  17. Clojure Macro Tutorial (Part I, Getting the Compiler to Write Your Code For You)
    http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-i-getting.html
  18. Clojure Macro Tutorial (Part II: The Compiler Strikes Back)
    http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-ii-compiler.html
  19. Clojure Macro Tutorial (Part III: Syntax Quote)
    http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-ii-syntax.html
  20. Tech behind Tech: Clojure Macros Simplified
    http://techbehindtech.com/2010/09/28/clo­jure-macros-simplified/
  21. Fatvat – Exploring functional programming: Clojure Macros
    http://www.fatvat.co.uk/2009/02/clo­jure-macros.html
  22. Eulerovo číslo
    http://cs.wikipedia.org/wi­ki/Eulerovo_číslo
  23. List comprehension
    http://en.wikipedia.org/wi­ki/List_comprehension
  24. List Comprehensions in Clojure
    http://asymmetrical-view.com/2008/11/18/list-comprehensions-in-clojure.html
  25. Clojure Programming Concepts: List Comprehension
    http://en.wikibooks.org/wi­ki/Clojure_Programming/Con­cepts#List_Comprehension
  26. Clojure core API: for macro
    http://clojure.github.com/clo­jure/clojure.core-api.html#clojure.core/for
  27. cirrus machina – The Clojure for macro
    http://www.cirrusmachina.com/blog/com­ment/the-clojure-for-macro/
  28. Riastradh's Lisp Style Rules
    http://mumble.net/~campbe­ll/scheme/style.txt
  29. Dynamic Languages Strike Back
    http://steve-yegge.blogspot.cz/2008/05/dynamic-languages-strike-back.html
  30. Scripting: Higher Level Programming for the 21st Century
    http://www.tcl.tk/doc/scripting.html
  31. Java Virtual Machine Support for Non-Java Languages
    http://docs.oracle.com/ja­vase/7/docs/technotes/gui­des/vm/multiple-language-support.html
  32. Třída java.lang.String
    http://docs.oracle.com/ja­vase/7/docs/api/java/lang/Strin­g.html
  33. Třída java.lang.StringBuffer
    http://docs.oracle.com/ja­vase/7/docs/api/java/lang/Strin­gBuffer.html
  34. Třída java.lang.StringBuilder
    http://docs.oracle.com/ja­vase/7/docs/api/java/lang/Strin­gBuilder.html
  35. StringBuffer versus String
    http://www.javaworld.com/ar­ticle/2076072/build-ci-sdlc/stringbuffer-versus-string.html
  36. Threading macro (dokumentace k jazyku Clojure)
    https://clojure.github.io/clo­jure/clojure.core-api.html#clojure.core/->
  37. Understanding the Clojure → macro
    http://blog.fogus.me/2009/09/04/un­derstanding-the-clojure-macro/
  38. clojure.inspector
    http://clojure.github.io/clo­jure/clojure.inspector-api.html
  39. The Clojure Toolbox
    http://www.clojure-toolbox.com/
  40. Unit Testing in Clojure
    http://nakkaya.com/2009/11/18/unit-testing-in-clojure/
  41. Testing in Clojure (Part-1: Unit testing)
    http://blog.knoldus.com/2014/03/22/tes­ting-in-clojure-part-1-unit-testing/
  42. API for clojure.test – Clojure v1.6 (stable)
    https://clojure.github.io/clo­jure/clojure.test-api.html
  43. Leiningen: úvodní stránka
    http://leiningen.org/
  44. Leiningen: Git repository
    https://github.com/techno­mancy/leiningen
  45. leiningen-win-installer
    http://leiningen-win-installer.djpowell.net/
  46. Clojure 1: Úvod
    http://www.root.cz/clanky/clojure-aneb-jazyk-umoznujici-tvorbu-bezpecnych-vicevlaknovych-aplikaci-pro-jvm/
  47. Clojure 2: Symboly, kolekce atd.
    http://www.root.cz/clanky/clojure-aneb-jazyk-umoznujici-tvorbu-bezpecnych-vicevlaknovych-aplikaci-pro-jvm-2-cast/
  48. Clojure 3: Funkcionální programování
    http://www.root.cz/clanky/clojure-aneb-jazyk-umoznujici-tvorbu-bezpecnych-vicevlaknovych-aplikaci-pro-jvm-3-cast-funkcionalni-programovani/
  49. Clojure 4: Kolekce, sekvence a lazy sekvence
    http://www.root.cz/clanky/clojure-aneb-jazyk-umoznujici-tvorbu-bezpecnych-vicevlaknovych-aplikaci-pro-jvm-4-cast-kolekce-sekvence-a-lazy-sekvence/
  50. Clojure 5: Sekvence, lazy sekvence a paralelní programy
    http://www.root.cz/clanky/clojure-a-bezpecne-aplikace-pro-jvm-sekvence-lazy-sekvence-a-paralelni-programy/
  51. Clojure 6: Podpora pro paralelní programování
    http://www.root.cz/clanky/programovaci-jazyk-clojure-6-futures-nejsou-jen-financni-derivaty/
  52. Clojure 7: Další funkce pro paralelní programování
    http://www.root.cz/clanky/programovaci-jazyk-clojure-7-dalsi-podpurne-prostredky-pro-paralelni-programovani/
  53. Clojure 8: Identity, stavy, neměnné hodnoty a reference
    http://www.root.cz/clanky/programovaci-jazyk-clojure-8-identity-stavy-nemenne-hodnoty-a-referencni-typy/
  54. Clojure 9: Validátory, pozorovatelé a kooperace s Javou
    http://www.root.cz/clanky/programovaci-jazyk-clojure-9-validatory-pozorovatele-a-kooperace-mezi-clojure-a-javou/
  55. Clojure 10: Kooperace mezi Clojure a Javou
    http://www.root.cz/clanky/programovaci-jazyk-clojure-10-kooperace-mezi-clojure-a-javou-pokracovani/
  56. Clojure 11: Generátorová notace seznamu/list comprehension
    http://www.root.cz/clanky/programovaci-jazyk-clojure-11-generatorova-notace-seznamu-list-comprehension/
  57. Clojure 12: Překlad programů z Clojure do bajtkódu JVM I:
    http://www.root.cz/clanky/programovaci-jazyk-clojure-12-preklad-programu-z-clojure-do-bajtkodu-jvm/
  58. Clojure 13: Překlad programů z Clojure do bajtkódu JVM II:
    http://www.root.cz/clanky/programovaci-jazyk-clojure-13-preklad-programu-z-clojure-do-bajtkodu-jvm-pokracovani/
  59. Clojure 14: Základy práce se systémem maker
    http://www.root.cz/clanky/programovaci-jazyk-clojure-14-zaklady-prace-se-systemem-maker/
  60. Clojure 15: Tvorba uživatelských maker
    http://www.root.cz/clanky/programovaci-jazyk-clojure-15-tvorba-uzivatelskych-maker/
  61. Clojure 16: Složitější uživatelská makra
    http://www.root.cz/clanky/programovaci-jazyk-clojure-16-slozitejsi-uzivatelska-makra/
  62. Clojure 17: Využití standardních maker v praxi
    http://www.root.cz/clanky/programovaci-jazyk-clojure-17-vyuziti-standardnich-maker-v-praxi/
  63. Clojure 18: Základní techniky optimalizace aplikací
    http://www.root.cz/clanky/programovaci-jazyk-clojure-18-zakladni-techniky-optimalizace-aplikaci/
  64. Clojure 19: Vývojová prostředí pro Clojure
    http://www.root.cz/clanky/programovaci-jazyk-clojure-19-vyvojova-prostredi-pro-clojure/
  65. Clojure 20: Vývojová prostředí pro Clojure (Vimu s REPL)
    http://www.root.cz/clanky/programovaci-jazyk-clojure-20-vyvojova-prostredi-pro-clojure-integrace-vimu-s-repl/
  66. Clojure 21: ClojureScript aneb překlad Clojure do JS
    http://www.root.cz/clanky/programovaci-jazyk-clojure-21-clojurescript-aneb-preklad-clojure-do-javascriptu/
  67. Clojure.org: Vars and the Global Environment
    http://clojure.org/Vars
  68. Clojure.org: Refs and Transactions
    http://clojure.org/Refs
  69. Clojure.org: Atoms
    http://clojure.org/Atoms
  70. Clojure.org: Agents as Asynchronous Actions
    http://clojure.org/agents
  71. Transient Data Structureshttp://clojure.or­g/transients
Našli jste v článku chybu?
DigiZone.cz: Sony MP-CL1A: miniaturní projektor

Sony MP-CL1A: miniaturní projektor

120na80.cz: Co je padesátkrát sladší než cukr?

Co je padesátkrát sladší než cukr?

Vitalia.cz: Muž, který miluje příliš. Ženám neimponuje

Muž, který miluje příliš. Ženám neimponuje

Lupa.cz: Jak levné procesory změnily svět?

Jak levné procesory změnily svět?

Vitalia.cz: Test dětských svačinek: Tyhle ne!

Test dětských svačinek: Tyhle ne!

DigiZone.cz: Na jaká videa se vlastně díváme

Na jaká videa se vlastně díváme

Lupa.cz: Hackeři mají data z půlmiliardy účtů Yahoo

Hackeři mají data z půlmiliardy účtů Yahoo

Podnikatel.cz: Znáte už 5 novinek k #EET

Znáte už 5 novinek k #EET

Lupa.cz: Cimrman má hry na YouTube i vlastní doodle

Cimrman má hry na YouTube i vlastní doodle

DigiZone.cz: DVB-T2 ověřeno: seznam TV zveřejněn

DVB-T2 ověřeno: seznam TV zveřejněn

Vitalia.cz: Voda z Vltavy před a po úpravě na pitnou

Voda z Vltavy před a po úpravě na pitnou

Lupa.cz: Blíží se konec Wi-Fi sítí bez hesla?

Blíží se konec Wi-Fi sítí bez hesla?

Měšec.cz: TEST: Vyzkoušeli jsme pražské taxikáře

TEST: Vyzkoušeli jsme pražské taxikáře

Lupa.cz: Další Češi si nechali vložit do těla čip

Další Češi si nechali vložit do těla čip

Vitalia.cz: Jak Ondra o astma přišel

Jak Ondra o astma přišel

DigiZone.cz: Parlamentní listy: kde končí PR...

Parlamentní listy: kde končí PR...

DigiZone.cz: Technisat připravuje trojici DAB

Technisat připravuje trojici DAB

Podnikatel.cz: Takhle se prodávají mražené potraviny

Takhle se prodávají mražené potraviny

Podnikatel.cz: Babišovi se nedá věřit, stěžovali si hospodští

Babišovi se nedá věřit, stěžovali si hospodští

DigiZone.cz: Rapl: seriál, který vás smíří s ČT

Rapl: seriál, který vás smíří s ČT