Hlavní navigace

Čtyři různé podoby datové struktury map v programovacím jazyku Clojure

15. 4. 2021
Doba čtení: 35 minut

Sdílet

 Autor: Clojure
V prakticky jakémkoli programu psaném v Clojure nalezneme mnoho míst, ve kterých se používají mapy. Tato nejužitečnější datová struktura existuje ve třech základních podobách, ovšem existuje i forma prioritní mapy.

Obsah

1. Mapy – nejdůležitější datový typ programovacího jazyka Clojure

2. Typy map v Clojure

3. Implementace třídy clojure.lang.PersistentHashMap

4. Rozhraní INode

5. Třídy ArrayNode a BitmapIndexedNode

6. Nový užitečný typ mapy: priority-map

7. Příprava projektu pro otestování vlastností jednotlivých implementací map

8. Přidání nové závislosti a stažení potřebných knihoven

9. Spuštění interaktivní smyčky REPL a import potřebného modulu

10. Otestování vlastností mapy typu hash-map

11. Otestování vlastností mapy typu sorted-map

12. Otestování vlastností mapy typu array-map

13. Otestování vlastností mapy typu priority-map

14. Základní operace s mapami: assocdissoc

15. Vyhledávání prvků, získání klíčů a hodnot

16. Operace merge a zipmap

17. Specifické operace pro priority-map

18. Repositář s demonstračním příkladem

19. Odkazy na předchozí části seriálu o programovacím jazyku Clojure

20. Odkazy na Internetu

1. Mapy – nejdůležitější datový typ programovacího jazyka Clojure

Při popisu programovacího jazyka Clojure jsme se seznámili se všemi datovými typy, které tento jazyk vývojářům nabízí. Připomeňme si, že kromě jednoduchých datových typů (celá čísla, reálná čísla, znaky, pravdivostní hodnoty, nil) Clojure podporuje i tři složené datové typy, nad nimiž je navíc postaven abstraktní typ sekvence. Především se jedná o seznamy (list), vektory (vector), množiny (set) a mapy (map). Seznamy a vektory jsou velmi důležité, protože se mj. používají i pro reprezentaci samotného programu, a to díky tomu, že Clojure je, podobně jako další dialekty programovacího jazyka LISP, takzvaně homoikonickým jazykem – program je reprezentován stejným způsobem jako data (což mj. umožňuje vytvářet pokročilé systémy maker). V některých aplikacích se používají i množiny, a to například ve chvíli, kdy potřebujeme reprezentovat přítomnost či nepřítomnost určitého prvku, a to nezávisle na jeho umístění v nějaké datové kolekci (nezajímá nás tedy například to, že se jedná o třetí prvek, ale o to, zda takový prvek vůbec existuje).

Seznamy, vektory a mnohdy i množiny tedy nalezneme v prakticky jakémkoli programu psaném v jazyce Clojure, ovšem zdaleka nejužitečnějším datovým typem jsou mapy. A právě velmi časté používání map v programech psaných v Clojure odlišuje tento jazyk jak od většiny ostatních dialektů LISPu, tak i od mainstreamových programovacích jazyků. Mapy jsou skutečně velmi flexibilním a téměř univerzálním datovým typem (či možná lépe řečeno datovou strukturou), který může nahradit například hodnotové objekty (viz například toto známé video), používají se namísto pojmenovaných parametrů funkcí (v Pythonu je nazýváme „keyword parametry“) a samozřejmě jsou (alespoň většinou) výsledkem deserializace souborů typu JSON, YAML apod. Na tomto místě je nutné upozornit na to, že mapy jsou, ostatně stejně jako seznamy, vektory i množiny, v jazyku Clojure neměnitelné (immutable) a perzistentní (persistent), takže velmi dobře zapadají do konceptu funkcionálního jazyka.

Poznámka: velmi pěkně je téma použití map v Clojure shrnuto v přednášce Rails Conf 2012 Keynote: Simplicity Matters by Rich Hickey (tato přednáška existuje v několika variantách).

2. Typy map v Clojure

V základní knihovně programovacího jazyka Clojure existují tři implementace map, které se od sebe odlišují některými svými vlastnostmi, především tím, jak jsou mapy převáděny na sekvence (tedy zda a jak zachovávají pořadí dvojic klíč-hodnota), a jaké jsou časové složitosti základních operací. Ovšem existuje i mnoho dalších implementací map a taktéž multimap. Tento článek vznikl primárně z toho důvodu, aby čtenáře seznámil s takzvanou prioritní mapou, v níž jsou hodnoty uložené do mapy použity pro reprezentaci priority prvků reprezentovaných svým klíčem (což je vlastně inverzní způsob chápání funkce mapy – blíže viz navazující kapitoly). Nicméně pro úplnost si nejdříve připomeneme zmíněné tři základní implementace mapy a poté si vlastnosti těchto implementací porovnáme s prioritními mapami. Mimochodem – prioritní mapy lze využít i pro implementaci prioritní fronty, ovšem s určitými omezeními (prvky musí být unikátní).

# Vlastnost Hash map Sorted map Array map
1 konstruktor (hash-map …) (sorted-map …) (array-map)
2 „literál“ {klíč hodnota klíč hodnota…} × ×
3 složitost přístupu k prvkům O(log32N) O(log N) O(N)
4 složitost (count) O(1) O(1) O(1)
5 zachování pořadí ne ne ano
6 setříděné prvky ne ano ne
7 podpora operace (seq) ano ano ano
8 podpora operace (rseq) ne ano ano
9 klíče nil povoleny ano ano ano
10 hodnoty nil povoleny ano ano ano
Poznámka: povšimněte si rozdílu v časové složitosti přístupu k prvkům mapy v případě hash mapy a sorted mapy. Složitosti O(log32N) a O(log N) sice patří do stejné kategorie, ovšem v praxi je první složitost prakticky konstantní pro rozumně velké mapy (přístup do mapy s tisíci prvky znamená dva kroky, pro mapu s milionem prvků pouhé kroky tři atd).

3. Implementace třídy clojure.lang.PersistentHashMap

Hash mapy se v praxi používají (minimálně v případě programovacího jazyka Clojure) mnohem častěji než mapy, v nichž jsou prvky setříděny na základě hodnoty svého klíče, popř. podle pořadí vložení prvku do mapy. Proto si podrobněji popíšeme interní strukturu hash mapy. Jedná se o neměnitelnou (immutable) a současně i perzistentní (persistent) datovou strukturu, což znamená, že do jednou vytvořené mapy již nelze přidávat další prvky (dvojice klíč-hodnota) ani žádné prvky ubírat. Na druhou stranu však mapy mohou sdílet svoji interní strukturu (structural sharing), takže přidání nového prvku lze efektivně zařídit vytvořením nové mapy s přidaným prvkem (což zajišťuje funkce nazvaná assoc, kterou si popíšeme níže, opakem je funkce dissoc). Hash mapy jsou interně uloženy podobným způsobem, jako vektory, tj. s využitím „tlustého“ stromu, jehož každý uzel může obsahovat až 32 odkazů na další poduzly. Takové stromy jsou typicky velmi nízké a tím pádem je i jejich prohledání rychlé – složitost mnoha operací je buď konstntní nebo rovna O(log32N), tj. „prakticky konstantní“.

4. Rozhraní INode

Interně je hash mapa tvořena stromem obsahujícím jako své uzly objekty objekty s rozhraním INode (tj. jedná se o instance tříd implementujících toto rozhraní). Samotná struktura INode se postupně vyvíjí a mění. V současné verzi jazyka Clojure (1.10) vypadá následovně:

static interface INode extends Serializable {
    INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf);
    INode without(int shift, int hash, Object key);
    IMapEntry find(int shift, int hash, Object key);
    Object find(int shift, int hash, Object key, Object notFound);
    ISeq nodeSeq();
    INode assoc(AtomicReference edit, int shift, int hash, Object key, Object val, Box addedLeaf);
    INode without(AtomicReference edit, int shift, int hash, Object key, Box removedLeaf);
    public Object kvreduce(IFn f, Object init);
    Object fold(IFn combinef, IFn reducef, IFn fjtask, IFn fjfork, IFn fjjoin);
    // returns the result of (f [k v]) for each iterated element
    Iterator iterator(IFn f);
}

V minulosti existovalo pět tříd implementujících rozhraní INode, v moderním Clojure jsou to již jen tři třídy: ArrayNode, BitmapIndexedNode a HashCollisionNode.

5. Třídy ArrayNode a BitmapIndexedNode

Třída ArrayNode interně obsahuje pole s prvky typu INode a hodnotu obsahující počet aktivních prvků v poli (což znamená, že funkce count má konstantní časovou složitost). Důležité je, že zde není uložen přímo klíč a hodnota prvku, jen reference na INode, popř. hodnota null. Operace assoc (přidání prvku se strukturálním sdílením) znamená buď pouhé přidání nového prvku nebo klonování pole s následným přidáním (klonují se ovšem pouze reference, nikoli vlastní hodnoty prvků).

Mnohem zajímavější je třída BitmapIndexedMode. Zde je interně použito pole Object[] o kapacitě 32 prvků, o obsazenosti rozhoduje celočíselný atribut bitmap. Význam jednotlivých položek se může měnit. Sudé prvky obsahují buď hodnotu null nebo klíč, liché prvky buď hodnotu (navázanou na klíč) nebo referenci na další INode (což je rekurzivně opět ArrayNode či BitmapIndexedMode):

  1. Když pole[2*i]==null pak pole[2*i+1] je INode
  2. Když pole[2*i]!=null pak pole[2*i] je klíč a pole[2*i+1] je hodnota

To znamená, že zmíněné 32prvkové pole může maximálně obsahovat šestnáct prvků klíč+hodnota, 32 odkazů na poduzly typu INode nebo mix obou typů záznamů.

Ve skutečnosti se pracuje s klíčem nepřímo přes jeho hash kód zjištěný funkcí hash (jde o 32bitovou hodnotu).

Poznámka: to, jaká struktura bude interně použita, záleží na počtu prvků při konstrukci mapy, popř. na způsobu práce s funkcemi assoc a dissoc. Je možné, že bude docházet i k převodům mezi interní strukturou.

6. Nový užitečný typ mapy: priority-map

Konečně se dostáváme k novému typu mapy, kvůli kterému vlastně dnešní článek vznikl. Jedná se o datový typ nazvaný priority-map, jenž je dostupný v balíčku clojure.data.priority-map (viz též https://github.com/clojure/da­ta.priority-map). Prvky ukládané do této mapy jsou seřazeny, podobně jako v datové struktuře sorted map. Ovšem je zde jeden velký rozdíl – řazení není prováděno na základě klíče, ale na základě hodnoty – jedná se tedy o „inverzní“ přístup k mapě, který umožňuje, aby priorita prvků byla libovolná (což u sorted mapy nelze, protože klíče musí být unikátní). Prioritní mapy lze využít ve funkci prioritní fronty, k čemuž můžeme použít funkce conj, peek a pop, které budou odzkoušeny v rámci navazujících kapitol. Samozřejmě jsou podporovány i běžné funkce typu assoc, dissoc, count, into atd.

7. Příprava projektu pro otestování vlastností jednotlivých implementací map

V dalších kapitolách si ukážeme práci s mapami (všech typů) prakticky. Aby bylo možné otestovat si možnosti prioritních map, vytvoříme nový Clojure projekt založený na projektu Leiningen, s nímž jsme se již v tomto seriálu setkali (odkazy jsou uvedeny v devatenácté kapitole). Kostra nového projektu se vytvoří příkazem:

$ lein new app priority-map-1
 
Generating a project called priority-map-1 based on the 'app' template.

Výsledkem předchozího příkazu by měla být následující adresářová struktura:

.
├── CHANGELOG.md
├── doc
│   └── intro.md
├── LICENSE
├── project.clj
├── README.md
├── resources
├── src
│   └── priority_map_1
│       └── core.clj
└── test
    └── priority_map_1
        └── core_test.clj
 
6 directories, 7 files

Pro nás je v tuto chvíli nejdůležitější soubor nazvaný project.clj, který obsahuje specifikaci celého projektu, a to včetně knihoven, na kterých projekt přímo závisí. Tranzitivní závislosti se řeší automaticky nástrojem Leiningen, který interně pro tento účel používá Maven. Vygenerovaný projektový soubor vypadá takto:

(defproject priority-map-1 "0.1.0-SNAPSHOT"
  :description "FIXME: write description"
  :url "http://example.com/FIXME"
  :license {:name "EPL-2.0 OR GPL-2.0-or-later WITH Classpath-exception-2.0"
            :url "https://www.eclipse.org/legal/epl-2.0/"}
  :dependencies [[org.clojure/clojure "1.10.1"]]
  :main ^:skip-aot priority-map-1.core
  :target-path "target/%s"
  :profiles {:uberjar {:aot :all
                       :jvm-opts ["-Dclojure.compiler.direct-linking=true"]}})

8. Přidání nové závislosti a stažení potřebných knihoven

Do projektového souboru project.clj je nyní nutné přidat informaci o balíčku s implementací prioritní mapy. Soubor upravíme následujícím způsobem:

(defproject priority-map-1 "0.1.0-SNAPSHOT"
  :description "FIXME: write description"
  :url "http://example.com/FIXME"
  :license {:name "EPL-2.0 OR GPL-2.0-or-later WITH Classpath-exception-2.0"
            :url "https://www.eclipse.org/legal/epl-2.0/"}
  :dependencies [[org.clojure/clojure "1.10.1"]
                 [org.clojure/data.priority-map "1.0.0"]]
  :main ^:skip-aot priority-map-1.core
  :target-path "target/%s"
  :profiles {:uberjar {:aot :all
                       :jvm-opts ["-Dclojure.compiler.direct-linking=true"]}})

Pro stažení všech závislých knihoven se použije příkaz:

$ lein deps
 
Retrieving org/clojure/data.priority-map/1.0.0/data.priority-map-1.0.0.pom from central
Retrieving org/clojure/data.priority-map/1.0.0/data.priority-map-1.0.0.jar from central

Nyní by měl být projekt připraven a měly by být k dispozici i všechny potřebné nestandardní knihovny.

9. Spuštění interaktivní smyčky REPL a import potřebného modulu

Pro otestování práce s mapami (všech typů) použijeme interaktivní smyčku REPL jazyka Clojure. Tu je nutné spustit v adresáři s projektovým souborem:

$ lein repl
 
nREPL server started on port 33211 on host 127.0.0.1 - nrepl://127.0.0.1:33211
REPL-y 0.4.4, nREPL 0.7.0
Clojure 1.10.1
OpenJDK 64-Bit Server VM 1.8.0_191-b12
    Docs: (doc function-name-here)
          (find-doc "part-of-name-here")
  Source: (source function-name-here)
 Javadoc: (javadoc java-object-or-class-here)
    Exit: Control+D or (exit) or (quit)
 Results: Stored in vars *1, *2, *3, an exception in *e
 
priority-map-1.core=>

V posledním přípravném kroku načteme modul s implementací prioritní mapy. To lze provést více způsoby, buď s využitím formy use:

priority-map-1.core=> (use 'clojure.data.priority-map)
WARNING: subseq already refers to: #'clojure.core/subseq in namespace: priority-map-1.core, being replaced by: #'clojure.data.priority-map/subseq
WARNING: rsubseq already refers to: #'clojure.core/rsubseq in namespace: priority-map-1.core, being replaced by: #'clojure.data.priority-map/rsubseq

Alternativně – a jedná se o čistší řešení – použijeme příkaz require, u kterého můžeme specifikovat, které symboly se mají načíst do stávajícího jmenného prostoru:

priority-map-1.core=> (require '[clojure.data.priority-map :refer [priority-map]])
Poznámka: další informace o formě use a require nalezneme v nápovědě dostupné přímo z prostředí smyčky REPL:
priority-map-1.core=> (doc use)
-------------------------
clojure.core/use
([& args])
  Like 'require, but also refers to each lib's namespace using
  clojure.core/refer. Use :use in the ns macro in preference to calling
  this directly.
 
  'use accepts additional options in libspecs: :exclude, :only, :rename.
  The arguments and semantics for :exclude, :only, and :rename are the same
  as those documented for clojure.core/refer.
priority-map-1.core=> (doc require)
-------------------------
clojure.core/require
([& args])
  Loads libs, skipping any that are already loaded. Each argument is
  either a libspec that identifies a lib, a prefix list that identifies
  multiple libs whose names share a common prefix, or a flag that modifies
  how all the identified libs are loaded. Use :require in the ns macro
  in preference to calling this directly.

10. Otestování vlastností mapy typu hash-map

Ve druhé polovině článku se budeme věnovat otestování základních vlastností jednotlivých typů map. Začneme s hash mapou, pro níž (kromě jiného) existuje konstruktor (či spíše literál) zapisovaný takto:

{klíč hodnota klíč hodnota klíč hodnota ...}

Pro větší čitelnost je možné použít čárky pro oddělení jednotlivých prvků:

{klíč hodnota, klíč hodnota, klíč hodnota ...}
Poznámka: ve skutečnosti vůbec na umístění čárek nezáleží – jsou zde ignorovány.

Konstruktorem hash mapy je funkce pojmenovaná hash-map:

priority-map-1.core=> (doc hash-map)
-------------------------
clojure.core/hash-map
([] [& keyvals])
  keyval => key val
  Returns a new hash map with supplied mappings.  If any keys are
  equal, they are handled as if by repeated uses of assoc.

Vytvoříme tedy hodnotu typu hash map a navážeme ji na symbol p1 (což by v jiných jazycích byla proměnná, ovšem nikoli v Clojure):

priority-map-1.core=> (def p1 (hash-map :a 2 :b 1 :c 3 :d 5 :e 4 :f 3 :g 0 :h 10 :i 6 :j 7))
#'priority-map-1.core/p1
Poznámka: velmi často se setkáme s tím, že klíče jsou reprezentovány formou :a, :foo atd. (keywords), což je z mnoha pohledů lepší řešení, než využití běžných řetězců. Viz též The five common forms of Clojure keywords.

Zobrazení obsahu hash mapy zdánlivě napovídá, že prvky jsou seřazeny takovým způsobem, jakým byly do mapy zadány (což ovšem není ve skutečnosti pravda):

priority-map-1.core=> p1
{:a 2 :b 1 :c 3 :d 5 :e 4 :f 3 :g 0 :h 10 :i 6 :j 7}

Způsob skutečného seřazení (resp. posloupnost přístupů) nám napoví spíše funkce pro získání všech klíčů:

priority-map-1.core=> (keys p1)
(:e :g :c :j :h :b :d :f :i :a)

Vrácení hodnot v nespecifikovaném pořadí:

priority-map-1.core=> (vals p1)
(4 0 3 7 10 1 5 3 6 2)

Takto se k mapě přistupuje jako k sekvenci hodnot (dvojic). Povšimněte si, že pořadí prvků je „náhodné“ (resp. závislé na haši klíčů):

priority-map-1.core=> (doseq [[key val] p1] (println key val))
:e 4
:g 0
:c 3
:j 7
:h 10
:b 1
:d 5
:f 3
:i 6
:a 2

Ještě jednodušší je převést mapu na sekvenci:

priority-map-1.core=> (seq p1)
([:e 4] [:g 0] [:c 3] [:j 7] [:h 10] [:b 1] [:d 5] [:f 3] [:i 6] [:a 2])

Pokud prvky do hash mapy vložíme v opačném pořadí:

priority-map-1.core=> (def p1r (hash-map :j 2 :i 1 :h 3 :g 5 :f 4 :e 3 :d 0 :c 10 :b 6 :a 7))
#'priority-map-1.core/p1r

Bude její obsah zdánlivě opět seřazen podle klíčů, ovšem jen při výpisu mapy:

priority-map-1.core=> p1r
{:a 7 :b 6 :c 10 :d 0 :e 3 :f 4 :g 5 :h 3 :i 1 :j 2}

Skutečné pořadí při přístupu k mapě jako k sekvenci:

priority-map-1.core=> (keys p1r)
(:e :g :c :j :h :b :d :f :i :a)
 
priority-map-1.core=> (vals p1r)
(3 5 10 2 3 6 0 4 1 7)

Přístup k mapě jako k sekvenci:

priority-map-1.core=> (doseq [[key val] p1r] (println key val))
:e 3
:g 5
:c 10
:j 2
:h 3
:b 6
:d 0
:f 4
:i 1
:a 7

A nakonec si ukažme prázdnou mapu:

priority-map-1.core=> (def p1e (hash-map))
#'priority-map-1.core/p1e
 
priority-map-1.core=> p1e
{}

Mapa podporuje i univerzální „spojovací“ operaci conj. Výsledkem je nová mapa:

priority-map-1.core=> (conj p1 {:foo 99})
{:a 2 :b 1 :c 3 :d 5 :e 4 :f 3 :foo 99 :g 0 :h 10 :i 6 :j 7}

Prvek je možné přepsat:

priority-map-1.core=> (conj p1 {:a 99})
{:a 99 :b 1 :c 3 :d 5 :e 4 :f 3 :g 0 :h 10 :i 6 :j 7}

Naproti tomu hash mapa NEpodporuje operace peek a pop, a to kvůli „náhodnému“ pořadí prvků:

priority-map-1.core=> (peek p1)
Execution error (ClassCastException) at priority-map-1.core/eval5764 (form-init1137606523006859476.clj:1).
clojure.lang.PersistentHashMap cannot be cast to clojure.lang.IPersistentStack
 
priority-map-1.core=> (pop p1)
Execution error (ClassCastException) at priority-map-1.core/eval5766 (form-init1137606523006859476.clj:1).
clojure.lang.PersistentHashMap cannot be cast to clojure.lang.IPersistentStack

11. Otestování vlastností mapy typu sorted-map

Mapa typu sorted map je interně založena na RB stromech, v nichž jsou prvky rozmístěny do jednotlivých uzlů na základě porovnání klíčů s klíči jiných prvků. Při sekvenčním přístupu k mapě jsou prvky seřazeny podle klíčů, přičemž záleží na použitém komparátoru. Například pro čísla se porovnávají jejich hodnoty, řetězce a keywords jsou seřazeny lexikograficky atd. Samozřejmě lze použít i vlastní komparátor.

Konstruktorem tohoto typu mapy je funkce sorted-map:

priority-map-1.core=> (doc sorted-map)
-------------------------
clojure.core/sorted-map
([& keyvals])
  keyval => key val
  Returns a new sorted map with supplied mappings.  If any keys are
  equal, they are handled as if by repeated uses of assoc.
nil

Vytvoříme si tedy tento typ mapy s několika prvky:

priority-map-1.core=> (def p2 (sorted-map :a 2 :b 1 :c 3 :d 5 :e 4 :f 3 :g 0 :h 10 :i 6 :j 7))
#'priority-map-1.core/p2

Nyní jsou prvky skutečně zařazeny podle hodnoty klíče, a to nejenom zdánlivě při tisku obsahu mapy, ale i při přístupu ke klíčům či přímo k hodnotám:

priority-map-1.core=> (keys p2)
(:a :b :c :d :e :f :g :h :i :j)
 
priority-map-1.core=> (vals p2)
(2 1 3 5 4 3 0 10 6 7)
 
priority-map-1.core=> p2
{:a 2 :b 1 :c 3 :d 5 :e 4 :f 3 :g 0 :h 10 :i 6 :j 7}

Zde se ukazuje zásadní rozdíl oproti hash mapám:

priority-map-1.core=> (doseq [[key val] p2] (println key val))
:a 2
:b 1
:c 3
:d 5
:e 4
:f 3
:g 0
:h 10
:i 6
:j 7

Převedení mapy na sekvenci ukazuje seřazení prvků podle hodnoty klíče:

priority-map-1.core=> (seq p2)
([:a 2] [:b 1] [:c 3] [:d 5] [:e 4] [:f 3] [:g 0] [:h 10] [:i 6] [:j 7])

Do mapy lze prvky vložit (při její konstrukci) v libovolném pořadí:

priority-map-1.core=> (def p2r (sorted-map :j 2 :i 1 :h 3 :g 5 :f 4 :e 3 :d 0 :c 10 :b 6 :a 7))
#'priority-map-1.core/p2r

Ovšem interně bude struktura stejná, jako v předchozím případě (prvky seřazeny podle hodnoty klíče):

priority-map-1.core=> p2r
{:a 7 :b 6 :c 10 :d 0 :e 3 :f 4 :g 5 :h 3 :i 1 :j 2}
 
priority-map-1.core=> (keys p2r)
(:a :b :c :d :e :f :g :h :i :j)
 
priority-map-1.core=> (vals p2r)
(7 6 10 0 3 4 5 3 1 2)
 
priority-map-1.core=> (doseq [[key val] p2r] (println key val))
:a 7
:b 6
:c 10
:d 0
:e 3
:f 4
:g 5
:h 3
:i 1
:j 2

Pochopitelně je podporována i práce s prázdnou mapou:

priority-map-1.core=> (def p2e (sorted-map))
#'priority-map-1.core/p2e
 
priority-map-1.core=> p2e
{}

Specifikace vlastního komparátoru (velmi užitečná vlastnost):

priority-map-1.core=> (sorted-map-by (comparator <) 0 :a 1 :b 2 :c)
{0 :a 1 :b 2 :c}
 
priority-map-1.core=> (sorted-map-by (comparator >) 0 :a 1 :b 2 :c)
{2 :c 1 :b 0 :a}

Konverze na jiný typ mapy zajišťuje funkce into:

priority-map-1.core=> (into (hash-map) p2)
{:a 2 :b 1 :c 3 :d 5 :e 4 :f 3 :g 0 :h 10 :i 6 :j 7}

Výsledek vypadá stejně, takže si raději prohlédněme typy:

priority-map-1.core=> (type p2)
#<Class@4fcabd1a clojure.lang.PersistentTreeMap>
 
priority-map-1.core=> (type (into (hash-map) p2))
#<Class@78047b92 clojure.lang.PersistentHashMap>

12. Otestování vlastností mapy typu array-map

Třetím základním typem mapy je array-map. V této mapě si prvky zachovávají pořadí, v jakém byly do mapy vloženy, což však má za následek méně efektivní přístup k jednotlivým prvkům přes jejich klíč. Konstruktorem této mapy je funkce array-map:

priority-map-1.core=> (doc array-map)
-------------------------
clojure.core/array-map
([] [& keyvals])
  Constructs an array-map. If any keys are equal, they are handled as
  if by repeated uses of assoc.

Vytvořme si nyní hodnotu typu array-map, navážeme na symbol a zobrazíme ji:

priority-map-1.core=> (def p3 (array-map :a 2 :b 1 :c 3 :d 5 :e 4 :f 3 :g 0 :h 10 :i 6 :j 7))
#'priority-map-1.core/p3
 
priority-map-1.core=> p3
{:a 2 :b 1 :c 3 :d 5 :e 4 :f 3 :g 0 :h 10 :i 6 :j 7}

Funkce keys a vals naznačují, jak jsou prvky v této mapě seřazeny:

priority-map-1.core=> (keys p3)
(:a :b :c :d :e :f :g :h :i :j)
 
priority-map-1.core=> (vals p3)
(2 1 3 5 4 3 0 10 6 7)

Ovšem přesnější údaje nám dá explicitně zapsaná iterace nad všemi prvky mapy:

priority-map-1.core=> (doseq [[key val] p3] (println key val))
:a 2
:b 1
:c 3
:d 5
:e 4
:f 3
:g 0
:h 10
:i 6
:j 7

Převod na sekvenci:

priority-map-1.core=> (seq p3)
([:a 2] [:b 1] [:c 3] [:d 5] [:e 4] [:f 3] [:g 0] [:h 10] [:i 6] [:j 7])

Mapa, v níž jsou prvky na začátku uspořádány v opačném pořadí, zachová toto nové pořadí:

priority-map-1.core=> (def p3r (array-map :j 2 :i 1 :h 3 :g 5 :f 4 :e 3 :d 0 :c 10 :b 6 :a 7))
#'priority-map-1.core/p3r
 
priority-map-1.core=> p3r
{:a 7 :b 6 :c 10 :d 0 :e 3 :f 4 :g 5 :h 3 :i 1 :j 2}
 
priority-map-1.core=> (keys p3r)
(:j :i :h :g :f :e :d :c :b :a)
 
priority-map-1.core=> (vals p3r)
(2 1 3 5 4 3 0 10 6 7)
 
priority-map-1.core=> (doseq [[key val] p3r] (println key val))
:j 2
:i 1
:h 3
:g 5
:f 4
:e 3
:d 0
:c 10
:b 6
:a 7

Při převodech mezi různými typy map se pořadí prvků podle očekávání ztratí:

priority-map-1.core=> (def p3-hash (into (hash-map) p3))
#'priority-map-1.core/p3-hash
 
priority-map-1.core=> (keys p3-hash)
(:e :g :c :j :h :b :d :f :i :a)
 
priority-map-1.core=> (def p3-back (into (array-map) p3-hash))
#'priority-map-1.core/p3-back
 
priority-map-1.core=> (keys p3-back)
(:e :g :c :j :h :b :d :f :i :a)

13. Otestování vlastností mapy typu priority-map

Posledním typem mapy, jejíž základní vlastnosti testujeme, je priority map. Její konstruktor se jmenuje jednoznačně – priority-map:

priority-map-1.core=> (doc priority-map)
-------------------------
clojure.data.priority-map/priority-map
([& keyvals])
  Usage: (priority-map key val key val ...)
  Returns a new priority map with optional supplied mappings.
  (priority-map) returns an empty priority map.

Zkusme si nyní vytvořit a zobrazit novou prioritní mapu:

priority-map-1.core=> (def p4 (priority-map :a 2 :b 1 :c 3 :d 5 :e 4 :f 3 :g 0 :h 10 :i 6 :j 7))
#'priority-map-1.core/p4
 
priority-map-1.core=> p4
{:g 0 :b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :i 6 :j 7 :h 10}

Nyní se dostáváme k základní a unikátní vlastnosti prioritní mapy – prvky jsou v ní uspořádány podle své hodnoty, nikoli podle svého klíče:

priority-map-1.core=> (keys p4)
(:g :b :a :c :f :e :d :i :j :h)
 
priority-map-1.core=> (vals p4)
(0 1 2 3 3 4 5 6 7 10)

Převod na sekvenci ukazuje stejné uspořádání:

priority-map-1.core=> (seq p4)
([:g 0] [:b 1] [:a 2] [:c 3] [:f 3] [:e 4] [:d 5] [:i 6] [:j 7] [:h 10])

Otestujme tuto vlastnost ještě na mapě s jinak zadanými prvky:

priority-map-1.core=> (def p4r (priority-map :j 2 :i 1 :h 3 :g 5 :f 4 :e 3 :d 0 :c 10 :b 6 :a 7))
#'priority-map-1.core/p4r
 
priority-map-1.core=> (keys p4r)
(:d :i :j :e :h :f :g :b :a :c)
 
priority-map-1.core=> (vals p4r)
(0 1 2 3 3 4 5 6 7 10)

Prázdnou mapu je možné taktéž použít:

priority-map-1.core=> (def p4e (priority-map))
#'priority-map-1.core/p4e
 
priority-map-1.core=> p4e
{}

Převody prvků z jiných map do prioritní mapy:

priority-map-1.core=> (into (priority-map) p1)
{:g 0 :b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :i 6 :j 7 :h 10}
 
priority-map-1.core=> (into (priority-map) p2)
{:g 0 :b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :i 6 :j 7 :h 10}
 
priority-map-1.core=> (into (priority-map) p3)
{:g 0 :b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :i 6 :j 7 :h 10}

S využitím threading makra zobrazíme uspořádání hodnot v prioritní mapě vzniklé konverzí z jiného typu mapy:

priority-map-1.core=> (->> p1 (into (priority-map)) vals)
(0 1 2 3 3 4 5 6 7 10)
 
priority-map-1.core=> (->> p2 (into (priority-map)) vals)
(0 1 2 3 3 4 5 6 7 10)
 
priority-map-1.core=> (->> p3 (into (priority-map)) vals)
(0 1 2 3 3 4 5 6 7 10)
Poznámka: pochopitelně nejsme omezeni pouze na celočíselné prvky; použít lze jakýkoli hodnoty, které jsou navzájem porovnatelné:
priority-map-1.core=> (priority-map :a "foo" :b "bar" :c "zzz" :d "aaa")
{:d "aaa" :b "bar" :a "foo" :c "zzz"}

Pokus o použití prvků, které nelze navzájem porovnat:

priority-map-1.core=> (priority-map :a "foo" :b "bar" :c "zzz" :d 0)
Execution error (ClassCastException) at clojure.data.priority_map.PersistentPriorityMap/assoc (priority_map.clj:302).
java.lang.String cannot be cast to java.lang.Number

14. Základní operace s mapami: assocdissoc

Mezi dvě základní operace, které je možné provádět s mapami, patří operace reprezentované funkcemi nazvanými assoc a dissoc. První z těchto funkcí přidá k již existující mapě novou dvojici klíč-hodnota (či několik dvojic klíč-hodnota) a vrátí novou mapu rozšířenou o tyto prvky (mapy jsou totiž neměnné datové typy, podobně jako seznamy a vektory). Druhá funkce – dissoc – plní opačnou roli, protože z nějaké mapy odstraní dvojici/e klíč-hodnota pro zadaný klíč či několik klíčů (jediným voláním dissoc je tedy možné odstranit více prvků). I tato funkce nemění původní mapu, ale vrací namísto toho novou datovou strukturu, která ovšem s původní mapou většinu prvků sdílí:

priority-map-1.core=> (doc assoc)
-------------------------
clojure.core/assoc
([map key val] [map key val & kvs])
  assoc[iate]. When applied to a map, returns a new map of the
    same (hashed/sorted) type, that contains the mapping of key(s) to
    val(s). When applied to a vector, returns a new vector that
    contains val at index. Note - index must be <= (count vector).
 
 
priority-map-1.core=> (doc dissoc)
-------------------------
clojure.core/dissoc
([map] [map key] [map key & ks])
  dissoc[iate]. Returns a new map of the same (hashed/sorted) type,
  that does not contain a mapping for key(s).

Ukažme si chování obou zmíněných funkcí assoc a dissoc na jednoduchém příkladu:

Nejprve vytvoříme mapu, jejímiž klíči jsou symboly a hodnotami řetězce (zejména použití symbolů pro klíče je v Clojure idiomatické, což jsme si již ukázali výše):

priority-map-1.core=> (def client {:id 42
  #_=>              :name "Sheldon"
  #_=>              :surname "Cooper"
  #_=>              :real-name "Jim Parsons"})
#'user/client

Zobrazíme obsah této mapy (povšimněte si, že prvky jsou zobrazeny náhodně, protože se jedná o hashmapu):

priority-map-1.core=> client
{:name "Sheldon", :surname "Cooper", :id 42, :real-name "Jim Parsons"}

Funkcí assoc vytvoříme novou mapu, do níž bude přidán další prvek:

priority-map-1.core=> (assoc client :iq 187)
{:name "Sheldon", :surname "Cooper", :iq 187, :id 42, :real-name "Jim Parsons"}

Původní mapa zůstala nezměněna:

priority-map-1.core=> client
{:name "Sheldon", :surname "Cooper", :id 42, :real-name "Jim Parsons"}

Funkcí dissoc vytvoříme mapu s odstraněným jedním prvkem či dvěma prvky:

priority-map-1.core=> (dissoc client :surname)
{:name "Sheldon", :id 42, :real-name "Jim Parsons"}
 
priority-map-1.core=> (dissoc client :name :surname)
{:id 42, :real-name "Jim Parsons"}

Opět se můžeme přesvědčit o tom, že původní mapa zůstala nezměněna:

priority-map-1.core=> client
{:name "Sheldon", :surname "Cooper", :id 42, :real-name "Jim Parsons"}
Poznámka: pro mapy existuje tranzientní ekvivalent, pro nějž jsou definovány funkce assoc! a dissoc! (s vykřičníkem na konci). Výsledné hodnoty těchto funkcí jsou opět tranzientními mapami, které je možné v případě potřeby navázat na symbol původní tranzientní mapy.

15. Vyhledávání prvků, získání klíčů a hodnot

Mezi další důležité operace, které se s mapami většinou provádí, patří zjištění, zda mapa obsahuje prvek (tj. klíč-hodnota). Pro tento účel nám Clojure nabízí hned několik funkcí. Opět si tyto funkce nejlépe odzkoušíme na jednoduchých příkladech.

Funkce budou otestovány na mapě, jejímiž klíči jsou římské číslice a hodnotami odpovídající číslice arabské:

priority-map-1.core=> (def numbers {"I" 1 "II" 2 "III" 3 "IV" 4 "V" 5})
#'user/numbers

Zobrazíme obsah této mapy (povšimněte si, že prvky jsou zobrazeny náhodně, protože se jedná o hashmapu:

priority-map-1.core=> (println numbers)
{III 3, II 2, V 5, I 1, IV 4}
nil

První funkcí je predikát contains?, kde otazník naznačuje, že se vždy vrací pravdivostní hodnota true či false v závislosti na tom, zda v mapě existuje prvek s daným klíčem:

priority-map-1.core=> (contains? numbers "I")
true
 
priority-map-1.core=> (contains? numbers 1)
false
 
priority-map-1.core=> (contains? numbers "xyzzy")
false

Druhá důležitá funkce je get, která vrací hodnotu navázanou na zadaný klíč, popř. nil, pokud klíč nebyl nalezen. Pokud se do mapy ukládají i hodnoty nil, nezbývá většinou nic jiného, než kombinace get+contains?:

priority-map-1.core=> (get numbers "V")
5
 
priority-map-1.core=> (get numbers "xyzzy")
nil

Funkce find je podobná funkci get, ale namísto hodnoty navázané na klíč vrací dvojici klíč+hodnota:

priority-map-1.core=> (find numbers "V")
["V" 5]
 
priority-map-1.core=> (find numbers "xyzzy")
nil
 
priority-map-1.core=> (type (find numbers "V"))
clojure.lang.MapEntry

Získat je možné všechny klíče, všechny hodnoty či provést selekci na základě sekvence klíčů (to jsme si již odzkoušeli u všech typů map výše):

priority-map-1.core=> (keys numbers)
("III" "II" "V" "I" "IV")
 
priority-map-1.core=> (vals numbers)
(3 2 5 1 4)
 
priority-map-1.core=> (select-keys numbers ["I" "IV" "V"])
{"V" 5, "IV" 4, "I" 1}
 
priority-map-1.core=> (select-keys numbers ["I" "IV" "neznamy"])
{"IV" 4, "I" 1}

Výběr jednoho prvku je možné provést i tím, že se zapíše volání (klíč mapa), což je v Clojure idiomatické:

priority-map-1.core=> (def numbers1 {:I 1 :II 2 :III 3 :IV 4 :V 5 :VI 6})
#'user/numbers1
 
priority-map-1.core=> (:III numbers1)
3

Podívejme se na praktičtější příklad používající mapu namísto struktury/záznamu a dvojí způsob získání jedné hodnoty na základě klíče:

priority-map-1.core=> (def client {:id 42
  #_=>              :name "Sheldon"
  #_=>              :surname "Cooper"
  #_=>              :real-name "Jim Parsons"})
#'user/client
 
priority-map-1.core=> client
{:name "Sheldon", :surname "Cooper", :id 42, :real-name "Jim Parsons"}
 
priority-map-1.core=> (get client :name)
"Sheldon"
 
priority-map-1.core=> (:name client)
"Sheldon"
Poznámka: toto je velmi flexibilní a funkcionálně pojatá náhrada za hodnotové objekty.

16. Operace merge a zipmap

Posledními dvěma důležitými operacemi nad mapami, s nimiž se lze v reálných aplikacích velmi často setkat, jsou operace reprezentované funkcemi merge a zipmap. Funkce nazvaná merge slouží ke spojení dvou či většího množství map. Nejprve opět použijeme známou strukturu obsahující základní informace o Sheldonovi:

priority-map-1.core=> (def client {:id 42
  #_=>              :name "Sheldon"
  #_=>              :surname "Cooper"
  #_=>              :real-name "Jim Parsons"})
#'user/client
 
priority-map-1.core=> client
{:name "Sheldon", :surname "Cooper", :id 42, :real-name "Jim Parsons"}

Nyní zavoláme funkci merge, jejímž výsledkem bude nová mapa:

priority-map-1.core=> (merge client {:iq 187 :degrees ["Ph.D." "Sc.D."]})
{:name "Sheldon", :surname "Cooper", :iq 187, :id 42, :degrees ["Ph.D." "Sc.D."], :real-name "Jim Parsons"}

Původní mapa zůstala nezměněna:

priority-map-1.core=> client
{:name "Sheldon", :surname "Cooper", :id 42, :real-name "Jim Parsons"}

Lépe bude patrný význam funkce merge u map se shodnými klíči. Při spojování v takovém případě „vyhraje“ hodnota uložená v poslední mapě vstupující do merge:

priority-map-1.core=> (def numbers1 {"I" 1 "II" 2 "III" 3 "IV" 4 "V" 5 "VI" 6})
#'user/numbers1
 
priority-map-1.core=> (def numbers2 {"VI" "sest" "VII" 7 "VIII" 8 "IX" 9 "X" 9})
#'user/numbers2
 
priority-map-1.core=> (merge numbers1 numbers2)
{"III" 3, "VIII" 8, "II" 2, "V" 5, "VII" 7, "X" 9, "VI" "sest", "IX" 9, "I" 1, "IV" 4}

Ovšem:

priority-map-1.core=> (merge numbers2 numbers1)
{"III" 3, "VIII" 8, "II" 2, "V" 5, "VII" 7, "X" 9, "VI" 6, "IX" 9, "I" 1, "IV" 4}

Velmi užitečná je v praxi funkce nazvaná zipmap, která umožňuje zkombinovat dvě sekvence do jediné mapy. První sekvence obsahuje klíče, druhá sekvence hodnoty. Můžeme tedy psát například:

priority-map-1.core=> (zipmap ["I" "II" "III" "IV" "V" "VI"]
  #_=>         [1 2 3 4 5 6])
{"VI" 6, "V" 5, "IV" 4, "III" 3, "II" 2, "I" 1}

Pravověrný Clojure programátor by ovšem napsal (se stejným výsledkem):

priority-map-1.core=> (zipmap ["I" "II" "III" "IV" "V" "VI"]
  #_=>         (range 1 7))
{"VI" 6, "V" 5, "IV" 4, "III" 3, "II" 2, "I" 1}

Pozor ovšem na to, že zipmap nejde jednoduše použít s nekonečnými lazy sekvencemi. Toto není dobrý nápad:

(zipmap (range) (repeat 42))

(Stačí ovšem, aby první sekvence byla konečná).

17. Specifické operace pro priority-map

Funkce assoc vrací v případě prioritní mapy novou mapu s přeuspořádanými prvky:

priority-map-1.core=> (assoc p4 :e 100)
{:g 0 :b 1 :a 2 :c 3 :f 3 :d 5 :i 6 :j 7 :h 10 :e 100}
 
priority-map-1.core=> (assoc p4 :i -100)
{:i -100 :g 0 :b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :j 7 :h 10}

Operace conj dovoluje vytvořit novou mapu s připojenými novými prvky:

priority-map-1.core=> (doc conj)
-------------------------
clojure.core/conj
([coll x] [coll x & xs])
  conj[oin]. Returns a new collection with the xs
    'added'. (conj nil item) returns (item).  The 'addition' may
    happen at different 'places' depending on the concrete type.

Takto to vypadá v praxi:

priority-map-1.core=> (conj p4 {:foo 99})
{:g 0 :b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :i 6 :j 7 :h 10 :foo 99}
 
priority-map-1.core=> (conj p4 {:bar 0})
{:bar 0 :g 0 :b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :i 6 :j 7 :h 10}

Ovšem – na rozdíl od běžných map – je kontrolován typ nově vkládané hodnoty:

priority-map-1.core=> (conj p4 {:foo :bar})
Execution error (ClassCastException) at clojure.data.priority_map.PersistentPriorityMap/assoc (priority_map.clj:302).
java.lang.Long cannot be cast to clojure.lang.Keyword

Další funkce umožňuje měnit hodnotu prvku se zadaným klíčem aplikací nějaké funkce:

priority-map-1.core=> (doc update)
-------------------------
clojure.core/update
([m k f] [m k f x] [m k f x y] [m k f x y z] [m k f x y z & more])
  'Updates' a value in an associative structure, where k is a
  key and f is a function that will take the old value
  and any supplied args and return the new value, and returns a new
  structure.  If the key does not exist, nil is passed as the old value.

Pro ostatní typy map tato operace nemění pořadí prvků, ovšem pro prioritní mapy tomu tak být může:

priority-map-1.core=> (update p4 :g inc)
{:g 1 :b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :i 6 :j 7 :h 10}
 
priority-map-1.core=> (update p4 :e #(*2 %))
{:e nil :g 0 :b 1 :a 2 :c 3 :f 3 :d 5 :i 6 :j 7 :h 10}

Velmi specifické jsou operace peek a pop:

priority-map-1.core=> (doc peek)
-------------------------
clojure.core/peek
([coll])
  For a list or queue, same as first, for a vector, same as, but much
  more efficient than, last. If the collection is empty, returns nil.
 
priority-map-1.core=> (doc pop)
-------------------------
clojure.core/pop
([coll])
  For a list or queue, returns a new list/queue without the first
  item, for a vector, returns a new vector without the last item. If
  the collection is empty, throws an exception.  Note - not the same
  as next/butlast.

Tyto operace nelze u běžných map jiných typů použít:

priority-map-1.core=> (peek p1)
Execution error (ClassCastException) at priority-map-1.core/eval6095 (form-init1137606523006859476.clj:1).
clojure.lang.PersistentHashMap cannot be cast to clojure.lang.IPersistentStack
 
priority-map-1.core=> (pop p1)
Execution error (ClassCastException) at priority-map-1.core/eval6097 (form-init1137606523006859476.clj:1).
clojure.lang.PersistentHashMap cannot be cast to clojure.lang.IPersistentStack
 
priority-map-1.core=> (peek p2)
Execution error (ClassCastException) at priority-map-1.core/eval6099 (form-init1137606523006859476.clj:1).
clojure.lang.PersistentTreeMap cannot be cast to clojure.lang.IPersistentStack
 
priority-map-1.core=> (pop p2)
Execution error (ClassCastException) at priority-map-1.core/eval6101 (form-init1137606523006859476.clj:1).
clojure.lang.PersistentTreeMap cannot be cast to clojure.lang.IPersistentStack
 
priority-map-1.core=> (peek p3)
Execution error (ClassCastException) at priority-map-1.core/eval6103 (form-init1137606523006859476.clj:1).
clojure.lang.PersistentArrayMap cannot be cast to clojure.lang.IPersistentStack
 
priority-map-1.core=> (pop p3)
Execution error (ClassCastException) at priority-map-1.core/eval6109 (form-init1137606523006859476.clj:1).
clojure.lang.PersistentArrayMap cannot be cast to clojure.lang.IPersistentStack

Tyto operace jsou určeny pro práci se sekvencemi (získanými například z vektorů, front nebo seznamů, popř. z nekonečných sekvencí), ovšem pro účely prioritní mapy byly redefinovány:

priority-map-1.core=> p4
{:g 0 :b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :i 6 :j 7 :h 10}
 
priority-map-1.core=> (pop p4)
{:b 1 :a 2 :c 3 :f 3 :e 4 :d 5 :i 6 :j 7 :h 10}
 
priority-map-1.core=> (peek p4)
[:g 0]

Z předchozích příkladů je patrné, že pop vrací mapu bez prvku s nejnižší prioritou, zatímco peek vrací právě onen prvek s nejnižší prioritou. Toto jsou dvě ze tří operací prioritní fronty; třetí operací je přidání prvku, což zajišťuje nám již známá funkce conj.

UI21_tip

Nakonec si ukažme filtraci prvků podle jejich priority:

priority-map-1.core=> (subseq p4 < 4)
([:g 0] [:b 1] [:a 2] [:c 3] [:f 3])
 
priority-map-1.core=> (subseq p4 > 4)
([:d 5] [:i 6] [:j 7] [:h 10])
Poznámka: vidíme, že prioritní mapy jsou sice poměrně úzce zaměřeným, ovšem na druhou stranu flexibilním a užitečným datovým typem, který by se mohl stát součástí základní knihovny jazyka Clojure (podobně jako prioritní fronty).

18. Repositář s demonstračním příkladem

Projekt, v němž je definována závislost na knihovně s prioritní mapou, byl uložen do Git repositáře, který je dostupný na adrese https://github.com/tisnik/clojure-examples/. Konkrétně se jedná o projekt nazvaný priority-map (https://github.com/tisnik/clojure-examples/tree/master/priority-map-1).

19. Odkazy na předchozí části seriálu o programovacím jazyku Clojure

  1. Clojure 1: Úvod
    http://www.root.cz/clanky/clojure-aneb-jazyk-umoznujici-tvorbu-bezpecnych-vicevlaknovych-aplikaci-pro-jvm/
  2. Clojure 2: Symboly, kolekce atd.
    http://www.root.cz/clanky/clojure-aneb-jazyk-umoznujici-tvorbu-bezpecnych-vicevlaknovych-aplikaci-pro-jvm-2-cast/
  3. 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/
  4. 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/
  5. 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/
  6. Clojure 6: Podpora pro paralelní programování
    http://www.root.cz/clanky/programovaci-jazyk-clojure-6-futures-nejsou-jen-financni-derivaty/
  7. Clojure 7: Další funkce pro paralelní programování
    http://www.root.cz/clanky/programovaci-jazyk-clojure-7-dalsi-podpurne-prostredky-pro-paralelni-programovani/
  8. 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/
  9. 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/
  10. Clojure 10: Kooperace mezi Clojure a Javou
    http://www.root.cz/clanky/programovaci-jazyk-clojure-10-kooperace-mezi-clojure-a-javou-pokracovani/
  11. Clojure 11: Generátorová notace seznamu/list comprehension
    http://www.root.cz/clanky/programovaci-jazyk-clojure-11-generatorova-notace-seznamu-list-comprehension/
  12. 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/
  13. 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/
  14. Clojure 14: Základy práce se systémem maker
    http://www.root.cz/clanky/programovaci-jazyk-clojure-14-zaklady-prace-se-systemem-maker/
  15. Clojure 15: Tvorba uživatelských maker
    http://www.root.cz/clanky/programovaci-jazyk-clojure-15-tvorba-uzivatelskych-maker/
  16. Programovací jazyk Clojure – triky při práci s řetězci
    http://www.root.cz/clanky/programovaci-jazyk-clojure-triky-pri-praci-s-retezci/
  17. Programovací jazyk Clojure – triky při práci s kolekcemi
    http://www.root.cz/clanky/programovaci-jazyk-clojure-triky-pri-praci-s-kolekcemi/
  18. Programovací jazyk Clojure – práce s mapami a množinami
    http://www.root.cz/clanky/programovaci-jazyk-clojure-prace-s-mapami-a-mnozinami/
  19. Programovací jazyk Clojure – základy zpracování XML
    http://www.root.cz/clanky/programovaci-jazyk-clojure-zaklady-zpracovani-xml/
  20. Programovací jazyk Clojure – testování s využitím knihovny Expectations
    http://www.root.cz/clanky/programovaci-jazyk-clojure-testovani-s-vyuzitim-knihovny-expectations/
  21. Programovací jazyk Clojure – některé užitečné triky použitelné (nejenom) v testech
    http://www.root.cz/clanky/programovaci-jazyk-clojure-nektere-uzitecne-triky-pouzitelne-nejenom-v-testech/
  22. Enlive – výkonný šablonovací systém pro jazyk Clojure
    http://www.root.cz/clanky/enlive-vykonny-sablonovaci-system-pro-jazyk-clojure/
  23. Nástroj Leiningen a programovací jazyk Clojure: tvorba vlastních knihoven pro veřejný repositář Clojars
    http://www.root.cz/clanky/nastroj-leiningen-a-programovaci-jazyk-clojure-tvorba-vlastnich-knihoven-pro-verejny-repositar-clojars/
  24. Novinky v Clojure verze 1.8.0
    http://www.root.cz/clanky/novinky-v-clojure-verze-1–8–0/
  25. Asynchronní programování v Clojure s využitím knihovny core.async
    http://www.root.cz/clanky/asynchronni-programovani-v-clojure-s-vyuzitim-knihovny-core-async/
  26. Asynchronní programování v Clojure s využitím knihovny core.async (pokračování)
    http://www.root.cz/clanky/asynchronni-programovani-v-clojure-s-vyuzitim-knihovny-core-async-pokracovani/
  27. Asynchronní programování v Clojure s využitím knihovny core.async (dokončení)
    http://www.root.cz/clanky/asynchronni-programovani-v-clojure-s-vyuzitim-knihovny-core-async-dokonceni/
  28. Vytváříme IRC bota v programovacím jazyce Clojure
    http://www.root.cz/clanky/vytvarime-irc-bota-v-programovacim-jazyce-clojure/
  29. Gorilla REPL: interaktivní prostředí pro programovací jazyk Clojure
    https://www.root.cz/clanky/gorilla-repl-interaktivni-prostredi-pro-programovaci-jazyk-clojure/
  30. Multimetody v Clojure aneb polymorfismus bez použití OOP
    https://www.root.cz/clanky/multimetody-v-clojure-aneb-polymorfismus-bez-pouziti-oop/
  31. Práce s externími Java archivy v programovacím jazyku Clojure
    https://www.root.cz/clanky/prace-s-externimi-java-archivy-v-programovacim-jazyku-clojure/
  32. Clojure 16: Složitější uživatelská makra
    http://www.root.cz/clanky/programovaci-jazyk-clojure-16-slozitejsi-uzivatelska-makra/
  33. Clojure 17: Využití standardních maker v praxi
    http://www.root.cz/clanky/programovaci-jazyk-clojure-17-vyuziti-standardnich-maker-v-praxi/
  34. Clojure 18: Základní techniky optimalizace aplikací
    http://www.root.cz/clanky/programovaci-jazyk-clojure-18-zakladni-techniky-optimalizace-aplikaci/
  35. Clojure 19: Vývojová prostředí pro Clojure
    http://www.root.cz/clanky/programovaci-jazyk-clojure-19-vyvojova-prostredi-pro-clojure/
  36. 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/
  37. Clojure 21: ClojureScript aneb překlad Clojure do JS
    http://www.root.cz/clanky/programovaci-jazyk-clojure-21-clojurescript-aneb-preklad-clojure-do-javascriptu/
  38. Leiningen: nástroj pro správu projektů napsaných v Clojure
    http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure/
  39. 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/
  40. 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/
  41. 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/
  42. 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/
  43. 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/
  44. Programovací jazyk Clojure a databáze (1.část)
    http://www.root.cz/clanky/programovaci-jazyk-clojure-a-databaze-1-cast/
  45. Pluginy pro Leiningen
    http://www.root.cz/clanky/leiningen-nastroj-pro-spravu-projektu-napsanych-v-clojure-pluginy-pro-leiningen/
  46. 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/
  47. 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/
  48. 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/
  49. 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/
  50. Seesaw: knihovna pro snadnou tvorbu GUI v jazyce Clojure
    http://www.root.cz/clanky/seesaw-knihovna-pro-snadnou-tvorbu-gui-v-jazyce-clojure/
  51. Seesaw: knihovna pro snadnou tvorbu GUI v azyce Clojure (2)
    http://www.root.cz/clanky/seesaw-knihovna-pro-snadnou-tvorbu-gui-v-jazyce-clojure-2/
  52. 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/
  53. Programovací jazyk Clojure a práce s Gitem
    http://www.root.cz/clanky/programovaci-jazyk-clojure-a-prace-s-gitem/
  54. Programovací jazyk Clojure a práce s Gitem (2)
    http://www.root.cz/clanky/programovaci-jazyk-clojure-a-prace-s-gitem-2/
  55. 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/
  56. Pixie: lehký skriptovací jazyk s „kouzelnými“ schopnostmi
    https://www.root.cz/clanky/pixie-lehky-skriptovaci-jazyk-s-kouzelnymi-schopnostmi/
  57. Programovací jazyk Pixie: funkce ze základní knihovny a použití FFI
    https://www.root.cz/clanky/pro­gramovaci-jazyk-pixie-funkce-ze-zakladni-knihovny-a-pouziti-ffi/
  58. Novinky v Clojure verze 1.9.0
    https://www.root.cz/clanky/novinky-v-clojure-verze-1–9–0/
  59. Validace dat s využitím knihovny spec v Clojure 1.9.0
    https://www.root.cz/clanky/validace-dat-s-vyuzitim-knihovny-spec-v-clojure-1–9–0/
  60. Použití jazyka Gherkin při tvorbě testovacích scénářů pro aplikace psané v Clojure
    https://www.root.cz/clanky/pouziti-jazyka-gherkin-pri-tvorbe-testovacich-scenaru-pro-aplikace-psane-v-nbsp-clojure/
  61. Použití jazyka Gherkin při tvorbě testovacích scénářů pro aplikace psané v Clojure (2)
    https://www.root.cz/clanky/pouziti-jazyka-gherkin-pri-tvorbe-testovacich-scenaru-pro-aplikace-psane-v-nbsp-clojure-2/
  62. Incanter: prostředí pro statistické výpočty s grafickým výstupem založené na Clojure
    https://www.root.cz/clanky/incanter-prostredi-pro-statisticke-vypocty-s-grafickym-vystupem-zalozene-na-clojure/
  63. Incanter: operace s maticemi
    https://www.root.cz/clanky/incanter-operace-s-maticemi/
  64. Interpret programovacího jazyka Clojure integrovaný do Jupyter Notebooku
    https://www.root.cz/clanky/interpret-programovaciho-jazyka-clojure-integrovany-do-jupyter-notebooku/
  65. Babashka: interpret Clojure určený pro rychlé spouštění utilit z příkazového řádku
    https://www.root.cz/clanky/babashka-interpret-clojure-urceny-pro-rychle-spousteni-utilit-z-prikazoveho-radku/
  66. Pokročilý streaming založený na Apache Kafce, jazyku Clojure a knihovně Jackdaw
    https://www.root.cz/clanky/pokrocily-streaming-zalozeny-na-apache-kafce-jazyku-clojure-a-knihovne-jackdaw/
  67. Pokročilý streaming založený na Apache Kafce, jazyku Clojure a knihovně Jackdaw (2. část)
    https://www.root.cz/clanky/pokrocily-streaming-zalozeny-na-apache-kafce-jazyku-clojure-a-knihovne-jackdaw-2-cast/
  68. Pokročilý streaming založený na projektu Apache Kafka, jazyku Clojure a knihovně Jackdaw (streamy a kolony)
    https://www.root.cz/clanky/pokrocily-streaming-zalozeny-na-projektu-apache-kafka-jazyku-clojure-a-knihovne-jackdaw-streamy-a-kolony/
  69. Řídicí struktury využitelné v programovacím jazyku Clojure
    https://www.root.cz/clanky/ridici-struktury-vyuzitelne-v-programovacim-jazyku-clojure/
  70. Řídicí struktury využitelné v programovacím jazyku Clojure (dokončení)
    https://www.root.cz/clanky/ridici-struktury-vyuzitelne-v-programovacim-jazyku-clojure-dokonceni/

20. Odkazy na Internetu

  1. Understanding Clojure's PersistentVector implementation
    http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation
  2. Understanding Clojure's PersistentHashMap (deftwice…)
    http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice.html
  3. Assoc and Clojure's PersistentHashMap: part ii
    http://blog.higher-order.net/2010/08/16/assoc-and-clojures-persistenthashmap-part-ii.html
  4. Ideal Hashtrees (paper)
    http://lampwww.epfl.ch/pa­pers/idealhashtrees.pdf
  5. data.priority-map API Reference
    https://clojure.github.io/da­ta.priority-map/
  6. Clojure Sequences
    http://clojure.org/sequences
  7. Clojure Data Structures
    https://clojure.org/referen­ce/data_structures
  8. hash-map
    https://clojure.github.io/clo­jure/clojure.core-api.html#clojure.core/hash-map
  9. sorted-map
    https://clojure.github.io/clo­jure/clojure.core-api.html#clojure.core/sorted-map
  10. array-map
    https://clojuredocs.org/clo­jure.core/array-map
  11. Clojure Hashmaps Explained: How to Retrieve Values From and Update Hashmaps
    https://www.freecodecamp.or­g/news/clojure-hashmaps-explained-how-to-retrieve-values-from-and-update-hashmaps/
  12. Clojure Data Structures Tutorial
    https://purelyfunctional.tv/gu­ide/clojure-collections/
  13. Are maps in Clojure ordered?
    https://stackoverflow.com/qu­estions/34401121/are-maps-in-clojure-ordered
  14. Clojure: how to conj to front of hash map in swap! function
    https://stackoverflow.com/qu­estions/33042116/clojure-how-to-conj-to-front-of-hash-map-in-swap-function
  15. The Clojure Toolbox
    http://www.clojure-toolbox.com/
  16. Transient Data Structureshttp://clojure.or­g/transients
  17. Rails Conf 2012 Keynote: Simplicity Matters by Rich Hickey
    https://www.youtube.com/wat­ch?v=rI8tNMsozo0
  18. Clojure Performance Guarantees
    https://www.innoq.com/blog/st/2010/04/clo­jure-performance-guarantees/
  19. Time complexity of operations on collections
    https://groups.google.com/g/clo­jure/c/xpqap7HShWw?pli=1
  20. five common forms of Clojure keywords
    https://blog.jeaye.com/2017/10/31/clo­jure-keywords/

Autor článku

Pavel Tišnovský vystudoval VUT FIT a v současné době pracuje ve společnosti Red Hat, kde vyvíjí nástroje pro OpenShift.io.