Obsah
1. Programovací jazyk Clojure – triky při práci s kolekcemi
2. Kolekce v programovacím jazyku Clojure
4. Funkce pracující se sekvencemi
7. Rozdíly v chování seznamů a vektorů
8. Měnitelné seznamy a vektory (transient collection)
10. Jak tedy zjistit existenci prvku v seznamu či vektoru?
11. Odkazy na předchozí části tohoto seriálu
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 rest i next 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 seq i rseq, 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.
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
- Leiningen: nástroj pro správu projektů napsaných v Clojure
http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure/ - 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/ - 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/ - 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/ - 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/ - 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/ - Programovací jazyk Clojure a databáze (1.část)
http://www.root.cz/clanky/programovaci-jazyk-clojure-a-databaze-1-cast/ - Pluginy pro Leiningen
http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure-pluginy-pro-leiningen/ - 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/ - 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/ - 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/ - 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/ - 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/ - Seesaw: knihovna pro snadnou tvorbu GUI v jazyce Clojure
http://www.root.cz/clanky/seesaw-knihovna-pro-snadnou-tvorbu-gui-v-jazyce-clojure/ - 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/ - 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/ - Programovací jazyk Clojure a práce s Gitem
http://www.root.cz/clanky/programovaci-jazyk-clojure-a-prace-s-gitem/ - Programovací jazyk Clojure a práce s Gitem (2)
http://www.root.cz/clanky/programovaci-jazyk-clojure-a-prace-s-gitem-2/ - 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
- Clojure home page
http://clojure.org/ - Clojure (downloads)
http://clojure.org/downloads - Clojure Sequences
http://clojure.org/sequences - Clojure Data Structures
http://clojure.org/data_structures - 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 - 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 - Clojure – Functional Programming for the JVM
http://java.ociweb.com/mark/clojure/article.html - Clojure quick reference
http://faustus.webatu.com/clj-quick-ref.html - 4Clojure
http://www.4clojure.com/ - ClojureDoc (rozcestník s dokumentací jazyka Clojure)
http://clojuredocs.org/ - Clojure (na Wikipedia EN)
http://en.wikipedia.org/wiki/Clojure - Clojure (na Wikipedia CS)
http://cs.wikipedia.org/wiki/Clojure - SICP (The Structure and Interpretation of Computer Programs)
http://mitpress.mit.edu/sicp/ - Pure function
http://en.wikipedia.org/wiki/Pure_function - Funkcionální programování
http://cs.wikipedia.org/wiki/Funkcionální_programování - Čistě funkcionální (datové struktury, jazyky, programování)
http://cs.wikipedia.org/wiki/Čistě_funkcionální - 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 - Clojure Macro Tutorial (Part II: The Compiler Strikes Back)
http://www.learningclojure.com/2010/09/clojure-macro-tutorial-part-ii-compiler.html - Clojure Macro Tutorial (Part III: Syntax Quote)
http://www.learningclojure.com/2010/09/clojure-macro-tutorial-part-ii-syntax.html - Tech behind Tech: Clojure Macros Simplified
http://techbehindtech.com/2010/09/28/clojure-macros-simplified/ - Fatvat – Exploring functional programming: Clojure Macros
http://www.fatvat.co.uk/2009/02/clojure-macros.html - Eulerovo číslo
http://cs.wikipedia.org/wiki/Eulerovo_číslo - List comprehension
http://en.wikipedia.org/wiki/List_comprehension - List Comprehensions in Clojure
http://asymmetrical-view.com/2008/11/18/list-comprehensions-in-clojure.html - Clojure Programming Concepts: List Comprehension
http://en.wikibooks.org/wiki/Clojure_Programming/Concepts#List_Comprehension - Clojure core API: for macro
http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/for - cirrus machina – The Clojure for macro
http://www.cirrusmachina.com/blog/comment/the-clojure-for-macro/ - Riastradh's Lisp Style Rules
http://mumble.net/~campbell/scheme/style.txt - Dynamic Languages Strike Back
http://steve-yegge.blogspot.cz/2008/05/dynamic-languages-strike-back.html - Scripting: Higher Level Programming for the 21st Century
http://www.tcl.tk/doc/scripting.html - Java Virtual Machine Support for Non-Java Languages
http://docs.oracle.com/javase/7/docs/technotes/guides/vm/multiple-language-support.html - Třída java.lang.String
http://docs.oracle.com/javase/7/docs/api/java/lang/String.html - Třída java.lang.StringBuffer
http://docs.oracle.com/javase/7/docs/api/java/lang/StringBuffer.html - Třída java.lang.StringBuilder
http://docs.oracle.com/javase/7/docs/api/java/lang/StringBuilder.html - StringBuffer versus String
http://www.javaworld.com/article/2076072/build-ci-sdlc/stringbuffer-versus-string.html - Threading macro (dokumentace k jazyku Clojure)
https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/-> - Understanding the Clojure → macro
http://blog.fogus.me/2009/09/04/understanding-the-clojure-macro/ - clojure.inspector
http://clojure.github.io/clojure/clojure.inspector-api.html - The Clojure Toolbox
http://www.clojure-toolbox.com/ - Unit Testing in Clojure
http://nakkaya.com/2009/11/18/unit-testing-in-clojure/ - Testing in Clojure (Part-1: Unit testing)
http://blog.knoldus.com/2014/03/22/testing-in-clojure-part-1-unit-testing/ - API for clojure.test – Clojure v1.6 (stable)
https://clojure.github.io/clojure/clojure.test-api.html - Leiningen: úvodní stránka
http://leiningen.org/ - Leiningen: Git repository
https://github.com/technomancy/leiningen - leiningen-win-installer
http://leiningen-win-installer.djpowell.net/ - Clojure 1: Úvod
http://www.root.cz/clanky/clojure-aneb-jazyk-umoznujici-tvorbu-bezpecnych-vicevlaknovych-aplikaci-pro-jvm/ - Clojure 2: Symboly, kolekce atd.
http://www.root.cz/clanky/clojure-aneb-jazyk-umoznujici-tvorbu-bezpecnych-vicevlaknovych-aplikaci-pro-jvm-2-cast/ - 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/ - 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/ - 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/ - Clojure 6: Podpora pro paralelní programování
http://www.root.cz/clanky/programovaci-jazyk-clojure-6-futures-nejsou-jen-financni-derivaty/ - Clojure 7: Další funkce pro paralelní programování
http://www.root.cz/clanky/programovaci-jazyk-clojure-7-dalsi-podpurne-prostredky-pro-paralelni-programovani/ - 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/ - 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/ - Clojure 10: Kooperace mezi Clojure a Javou
http://www.root.cz/clanky/programovaci-jazyk-clojure-10-kooperace-mezi-clojure-a-javou-pokracovani/ - Clojure 11: Generátorová notace seznamu/list comprehension
http://www.root.cz/clanky/programovaci-jazyk-clojure-11-generatorova-notace-seznamu-list-comprehension/ - 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/ - 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/ - Clojure 14: Základy práce se systémem maker
http://www.root.cz/clanky/programovaci-jazyk-clojure-14-zaklady-prace-se-systemem-maker/ - Clojure 15: Tvorba uživatelských maker
http://www.root.cz/clanky/programovaci-jazyk-clojure-15-tvorba-uzivatelskych-maker/ - Clojure 16: Složitější uživatelská makra
http://www.root.cz/clanky/programovaci-jazyk-clojure-16-slozitejsi-uzivatelska-makra/ - Clojure 17: Využití standardních maker v praxi
http://www.root.cz/clanky/programovaci-jazyk-clojure-17-vyuziti-standardnich-maker-v-praxi/ - Clojure 18: Základní techniky optimalizace aplikací
http://www.root.cz/clanky/programovaci-jazyk-clojure-18-zakladni-techniky-optimalizace-aplikaci/ - Clojure 19: Vývojová prostředí pro Clojure
http://www.root.cz/clanky/programovaci-jazyk-clojure-19-vyvojova-prostredi-pro-clojure/ - 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/ - Clojure 21: ClojureScript aneb překlad Clojure do JS
http://www.root.cz/clanky/programovaci-jazyk-clojure-21-clojurescript-aneb-preklad-clojure-do-javascriptu/ - Clojure.org: Vars and the Global Environment
http://clojure.org/Vars - Clojure.org: Refs and Transactions
http://clojure.org/Refs - Clojure.org: Atoms
http://clojure.org/Atoms - Clojure.org: Agents as Asynchronous Actions
http://clojure.org/agents - Transient Data Structureshttp://clojure.org/transients
