Projekt Mori aneb perzistentní datové struktury pro JavaScript (dokončení)

Obsah

1. Projekt Mori aneb perzistentní datové struktury pro JavaScript (dokončení)

2. Zpracování sekvencí v knihovně Mori

   2.1 Malé doplnění k předchozí části: použití funkce mori.range()

   2.2 Funkce mori.repeat()

   2.3 Funkce mori.partition()

   2.4 Funkce mori.interleave()

   2.5 Demonstrační příklady

3. Použití funkcí vyššího řádu v knihovně Mori při zpracování sekvencí

   3.1 Funkce mori.partitionBy()

   3.2 Funkce mori.takeWhile()

   3.3 Funkce mori.filter()

   3.4 Demonstrační příklad

4. Operace s množinami

   4.1 Funkce mori.set() a mori.sortedSet()

   4.2 Sjednocení, průnik a rozdíl množin

   4.3 Demonstrační příklady

5. Operace s mapami

   5.1 Funkce mori.hashMap() a mori.sortedMap()

   5.2 Získání klíčů, hodnot a sloučení map

   5.3 Funkce mori.assoc(), mori.dissoc() a mori.zipmap()

   5.4 Demonstrační příklady

6. Obsah dalšího článku – porovnání Mori s knihovnou Immutable.js

7. Repositář se zdrojovými kódy všech dnešních demonstračních příkladů

8. Odkazy na Internetu

1. Projekt Mori aneb perzistentní datové struktury pro JavaScript (dokončení)

Knihovna Mori, která je, jak jsme se již dozvěděli v první části tohoto článku, založena na programovém kódu ClojureScriptu, přidává do programovacího jazyka JavaScript podporu pro pět strukturovaných a současně i perzistentních datových typů. Připomeňme si, že se jedná o seznamy, vektory, fronty, množiny a mapy. Ovšem důležitější, než samotná existence těchto datových typů, je podpora operací s daty. Právě zde se projevuje funkcionální přístup, který knihovna Mori zdědila z ClojureScriptu: nad všemi podporovanými datovými strukturami existuje jednotné rozhraní nazvané sekvence; namísto metod se používají funkce, které nemodifikují datovou strukturu, ale vrací strukturu novou a konečně mnoho funkcí z knihovny Mori akceptuje jako své parametry jiné funkce (funkce vyššího řádu). Díky těmto vlastnostem je implementace mnoha algoritmů velmi jednoduchá a přímočará (programy totiž nejsou plné programových smyček, které mnohdy jen zastiňují prováděnou operaci).

2. Zpracování sekvencí v knihovně Mori

V mnoha programech je nutné data, se kterými daný program pracuje, nějakým způsobem transformovat, popř. vytvářet data nová (číselné řady atd.). V knihovně Mori je k těmto účelům nabízeno velké množství funkcí. V této kapitole se zaměříme na dvojici funkcí určených pro vytváření číselných řad popř. sekvence stejných hodnot a taktéž na funkce určené pro rozdělování i slučování sekvencí.

2.1 Malé doplnění k předchozí části: použití funkce mori.range()

S funkcí mori.range() jsme se již setkali minule, ovšem nebylo zcela jasně napsáno, jak se tato funkce chová při zadání různých parametrů. Podívejme se tedy na pětici příkladů (tučný řádek označuje příkaz, běžné písmo pak výsledek):

// zadány jsou obě meze
mori.range(1, 10);
(1 2 3 4 5 6 7 8 9)
 
// zadány jsou obě meze a krok
mori.range(1, 10, 2);
(1 3 5 7 9)
 
// krok může být i záporný
mori.range(10, 1, -2);
(10 8 6 4 2)
 
// je zadán jen počet prvků
mori.range(10);
(0 1 2 3 4 5 6 7 8 9)
 
// není zadáno nic, což však nezpůsobí chybu
mori.range();
(nekonečná lazy sekvence)

2.2 Funkce mori.repeat()

Funkce mori.repeat() se částečně podobá funkci mori.range(), ovšem s tím rozdílem, že se vytvoří lazy sekvence obsahující stejné prvky, nikoli číselnou řadu. Pokud se zadá počet prvků, je výsledkem konečná sekvence, pokud se ovšem zadá jen prvek (jediný parametr), je vytvořená lazy sekvence nekonečná. Opět se podívejme na několik příkladů:

// počet prvků i hodnota prvku
mori.repeat(1, 10);
(10)
 
// počet prvků i hodnota prvku
mori.repeat(10, 1);
(1 1 1 1 1 1 1 1 1 1)
 
// počet prvků i hodnota prvku
mori.repeat(10, 'hello');
("hello" "hello" "hello" "hello" "hello" "hello" "hello" "hello" "hello" "hello")
 
// u nekonečné sekvence si musíme dát pozor na to, aby nedošlo k jejímu vyhodnocení
mori.take(42, mori.repeat('*'));
("*" "*" "*" "*" "*" "*" "*" "*" "*" "*" "*"
 "*" "*" "*" "*" "*" "*" "*" "*" "*" "*" "*"
 "*" "*" "*" "*" "*" "*" "*" "*" "*" "*" "*"
 "*" "*" "*" "*" "*" "*" "*" "*" "*")
 

2.3 Funkce mori.partition()

Funkce mori.partition() dokáže rozdělit zadanou sekvenci (ať již konečnou či nekonečnou) na několik částí, přičemž lze zvolit délky jednotlivých „podsekvencí“. Chování této funkce, včetně mezních případů, nejlépe osvětlí příklady:

// sekvence, kterou budeme rozdělovat
var seq = mori.range(0,12);
(0 1 2 3 4 5 6 7 8 9 10 11)
 
// rozdělení na podsekvence o jednom prvku
mori.partition(1, seq);
((0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11))
 
// rozdělení na podsekvence o dvou prvcích
mori.partition(2, seq);
((0 1) (2 3) (4 5) (6 7) (8 9) (10 11))
 
// rozdělení na podsekvence o třech prvcích
mori.partition(3, seq);
((0 1 2) (3 4 5) (6 7 8) (9 10 11))
 
// rozdělení na podsekvence o čtyřech prvcích
mori.partition(4, seq);
((0 1 2 3) (4 5 6 7) (8 9 10 11))
 
// rozdělení na podsekvence o šesti prvcích
mori.partition(6, seq);
((0 1 2 3 4 5) (6 7 8 9 10 11))
 
// mezní případ
mori.partition(20, seq);
()

2.4 Funkce mori.interleave()

Opakem funkce mori.partition() je funkce nazvaná mori.interleave(), která dokáže promíchat prvky ze dvou sekvencí do jediné výsledné sekvence. Opět se podívejme na příklady:

// první sekvence
var seq1 = mori.range(0,12);
(0 1 2 3 4 5 6 7 8 9 10 11)
 
// druhá sekvence
var seq2 = mori.repeat(12, '*');
("*" "*" "*" "*" "*" "*" "*" "*" "*" "*" "*" "*")
 
// promíchání obou sekvencí
mori.interleave(seq1, seq2);
(0 "*" 1 "*" 2 "*" 3 "*" 4 "*" 5 "*" 6 "*" 7 "*" 8 "*" 9 "*" 10 "*" 11 "*")

2.5 Demonstrační příklady

Výše popsané čtyři funkce jsou součástí trojice demonstračních příkladů, jejichž zdrojové kódy budou vypsány pod tímto odstavcem, a to včetně HTML stránek sloužících pro spuštění příkladů ve webovém prohlížeči.

mori₀₅.js

// ------------------------------------------------------------
// Knihovna Mori: demonstracni priklad cislo 5
//
// Otestovani funkce mori.range()
// ------------------------------------------------------------
 
 
 
// vypis informaci o vybrane sekvenci
function printSequenceInfo(declaration) {
    var sequence = eval(declaration);
    console.log("---------------------------------");
    console.log(declaration);
    console.log("length:  " + mori.count(sequence));
    console.log("content: " + sequence);
}
 
printSequenceInfo("mori.range(1, 10)");
printSequenceInfo("mori.range(1, 10, 2)");
printSequenceInfo("mori.range(10, 1, -2)");
printSequenceInfo("mori.range(10)");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

mori₀₅.html

<!doctype html>
<html>
    <head>
        <title>Mori tests #05</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_05.js"></script>
    </head>
    <body>
        <h1>Mori tests #05</h1>
    </body>
</html>

mori₀₆.js

// ------------------------------------------------------------
// Knihovna Mori: demonstracni priklad cislo 6
//
// Otestovani funkce mori.repeat()
// ------------------------------------------------------------
 
 
 
// vypis informaci o vybrane sekvenci
function printSequenceInfo(declaration) {
    var sequence = eval(declaration);
    console.log("---------------------------------");
    console.log(declaration);
    console.log("length:  " + mori.count(sequence));
    console.log("content: " + sequence);
}
 
printSequenceInfo("mori.repeat(1, 10)");
printSequenceInfo("mori.repeat(10, 1)");
printSequenceInfo("mori.repeat(10, 'hello')");
printSequenceInfo("mori.take(42, mori.repeat('*'))");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

mori₀₆.html

<!doctype html>
<html>
    <head>
        <title>Mori tests #06</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_06.js"></script>
    </head>
    <body>
        <h1>Mori tests #06</h1>
    </body>
</html>

mori₀₇.js

// ------------------------------------------------------------
// Knihovna Mori: demonstracni priklad cislo 7
//
// Otestovani funkce mori.partition() a mori.interleave()
// ------------------------------------------------------------
 
 
 
// ziskani typu sekvence
function sequenceType(sequence) {
    return mori.isList(sequence)   ? "list" :
           mori.isVector(sequence) ? "vector" :
           mori.isMap(sequence)    ? "map" :
           mori.isSet(sequence)    ? "set" :
           mori.isSeq(sequence)    ? "sequence" :
           "unknown";
}
 
 
 
// vypis informaci o vybrane sekvenci
function printSequenceInfo(declaration) {
    var sequence = eval(declaration);
    var type = sequenceType(sequence);
    console.log("---------------------------------");
    console.log(declaration);
    console.log("type:    " + type);
    console.log("length:  " + mori.count(sequence));
    console.log("content: " + sequence);
}
 
var seq = mori.range(0,12);
 
printSequenceInfo("mori.partition(1, seq)");
printSequenceInfo("mori.partition(2, seq)");
printSequenceInfo("mori.partition(3, seq)");
printSequenceInfo("mori.partition(4, seq)");
printSequenceInfo("mori.partition(6, seq)");
printSequenceInfo("mori.partition(20, seq)");
 
var seq1 = mori.range(0,12);
var seq2 = mori.repeat(12, '*');
 
printSequenceInfo("seq1");
printSequenceInfo("seq2");
printSequenceInfo("mori.interleave(seq1, seq2)");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

mori₀₇.html

<!doctype html>
<html>
    <head>
        <title>Mori tests #07</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_07.js"></script>
    </head>
    <body>
        <h1>Mori tests #07</h1>
    </body>
</html>

3. Použití funkcí vyššího řádu v knihovně Mori při zpracování sekvencí

V knihovně Mori se v mnoha funkcích používají i takzvané funkce vyššího řádu. S jednou takovou funkcí jsme se již setkali minule – jednalo se o mori.map(). Ve skutečnosti těchto funkcí existuje více; s třemi z nich se seznámíme v navazujících podkapitolách.

3.1 Funkce mori.partitionBy()

Funkce mori.partitionBy() slouží, podobně jako již zmíněná funkce mori.partition(), k rozdělení lazy sekvence do podsekvencí. Ovšem zde se namísto počtu prvků v podsekvenci při rozdělování vyhodnocuje zadaná funkce a teprve ve chvíli, kdy tato funkce změní hodnotu, dojde ke vzniku nové podsekvence. Příklady vše osvětlí:

// funkce používaná pro partitionBy
function f0(n) {
    return "konstanta"
}
 
// funkce používaná pro partitionBy
function f1(n) {
    return n < 6;
}
 
// funkce používaná pro partitionBy
function f2(n) {
    return n % 2 == 1;
}
 
// funkce používaná pro partitionBy
function f3(n) {
    return n % 4 == 3;
}
 
// funkce používaná pro partitionBy
function f4(n) {
    return Math.random() < 0.5;
}
 
// vstupní sekvence
var seq = mori.range(0,12);
(0 1 2 3 4 5 6 7 8 9 10 11)
 
// funkce f0 nemění svou výstupní hodnotu NIKDY
mori.partitionBy(f0, seq)
((0 1 2 3 4 5 6 7 8 9 10 11))
 
// funkce f0 změní výstupní hodnotu ve chvíli, kdy překročíme hodnotu 5
mori.partitionBy(f1, seq)
((0 1 2 3 4 5) (6 7 8 9 10 11))
 
// funkce f0 mění svou výstupní hodnotu VŽDY (pro daný vstup)
mori.partitionBy(f2, seq)
((0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11))
 
mori.partitionBy(f3, seq)
((0 1 2) (3) (4 5 6) (7) (8 9 10) (11))
 
// náhodné rozdělení na podsekvence
mori.partitionBy(f4, seq)
((0 1 2 3 4) (5) (6 7 8 9) (10 11))

3.2 Funkce mori.takeWhile()

Funkce mori.takeWhile() postupně vyhodnocuje prvky vstupní sekvence a vrací je ve formě nové lazy sekvence, ovšem jen do doby, dokud volaná uživatelská funkce vrací pravdivostní hodnotu true:

// funkce používaná pro takeWhile
function f1(n) {
    return n < 6;
}
 
// funkce používaná pro takeWhile
function f2(n) {
    return n % 2 == 1;
}
 
// funkce používaná pro takeWhile
function f3(n) {
    return n % 4 == 3;
}
 
// vstupní sekvence
var seq = mori.range(0,12);
(0 1 2 3 4 5 6 7 8 9 10 11)
 
// u prvku s hodnotou 6 již f1(6) vrátí false
mori.takeWhile(f1, seq)
(0 1 2 3 4 5)
 
mori.takeWhile(f2, seq)
()
 
mori.takeWhile(f3, seq)
()

3.3 Funkce mori.filter()

Funkce mori.filter() taktéž prochází vstupní sekvenci a vytváří výstupní lazy sekvenci z prvků původní sekvence. Ovšem do nové sekvence jsou zařazeny pouze ty prvky, pro něž volaná uživatelská funkce vrátí hodnotu true či jinou hodnotu odlišnou od false (naproti tomu funkce mori.takeWhile() zpracování na tomto místě zastaví). Je libo příklad?:

// funkce používaná pro filter
function f1(n) {
    return n < 6;
}
 
// funkce používaná pro filter
function f2(n) {
    return n % 2 == 1;
}
 
// funkce používaná pro filter
function f3(n) {
    return n % 4 == 3;
}
 
// vstupní sekvence
var seq = mori.range(0,12);
(0 1 2 3 4 5 6 7 8 9 10 11)
 
// f1 vrací true pouze pro hodnoty menší než 6
mori.filter(f1, seq)
(0 1 2 3 4 5)
 
// funkce f2 vrací true v závislosti na dělitelnosti 2
mori.filter(f2, seq)
(1 3 5 7 9 11)
 
// funkce f2 vrací true v závislosti na dělitelnosti 4
mori.filter(f3, seq)
(3 7 11)

3.4 Demonstrační příklad

Všechny tři výše popsané funkce jsou použity v demonstračním příkladu nazvaném mori₀₈:

mori₀₈.js

// ------------------------------------------------------------
// Knihovna Mori: demonstracni priklad cislo 8
//
// Otestovani funkce mori.partitionBy(), mori.takeWhile()
// a mori.filter().
// ------------------------------------------------------------
 
 
 
// ziskani typu sekvence
function sequenceType(sequence) {
    return mori.isList(sequence)   ? "list" :
           mori.isVector(sequence) ? "vector" :
           mori.isMap(sequence)    ? "map" :
           mori.isSet(sequence)    ? "set" :
           mori.isSeq(sequence)    ? "sequence" :
           "unknown";
}
 
 
 
// vypis informaci o vybrane sekvenci
function printSequenceInfo(declaration) {
    var sequence = eval(declaration);
    var type = sequenceType(sequence);
    console.log("---------------------------------");
    console.log(declaration);
    console.log("type:    " + type);
    console.log("length:  " + mori.count(sequence));
    console.log("content: " + sequence);
}
 
function f0(n) {
    return "konstanta"
}
 
function f1(n) {
    return n < 6;
}
 
function f2(n) {
    return n % 2 == 1;
}
 
function f3(n) {
    return n % 4 == 3;
}
 
function f4(n) {
    return Math.random() < 0.5;
}
 
var seq = mori.range(0,12);
 
printSequenceInfo("mori.partitionBy(f0, seq)");
printSequenceInfo("mori.partitionBy(f1, seq)");
printSequenceInfo("mori.partitionBy(f2, seq)");
printSequenceInfo("mori.partitionBy(f3, seq)");
printSequenceInfo("mori.partitionBy(f4, seq)");
 
printSequenceInfo("mori.takeWhile(f1, seq)");
printSequenceInfo("mori.takeWhile(f2, seq)");
printSequenceInfo("mori.takeWhile(f3, seq)");
 
printSequenceInfo("mori.filter(f1, seq)");
printSequenceInfo("mori.filter(f2, seq)");
printSequenceInfo("mori.filter(f3, seq)");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

mori₀₈.html

<!doctype html>
<html>
    <head>
        <title>Mori tests #08</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_08.js"></script>
    </head>
    <body>
        <h1>Mori tests #08</h1>
    </body>
</html>

4. Operace s množinami

Velmi důležitým, i když mnohdy možná poněkud opomíjeným strukturovaným datovým typem, jsou množiny, neboli sets (mimochodem – to, že se množiny nepoužívají tak často, jak to implementace nějakého algoritmu vyžaduje, je častá chyba, která je pravděpodobně způsobena tím, že množiny jakožto samostatný datový typ v některých jazycích neexistují). Tento datový typ skutečně reflektuje některé vlastnosti matematických množin, zejména fakt, že prvek se stejnou hodnotou může být v množině uložen maximálně jedenkrát (v knihovně Mori je ekvivalence hodnot řešena opět funkcionálním způsobem, mj. i rekurzivním porovnáním všech prvků dvou objektů). Vzhledem k tomu, že v mnoha algoritmech je nutné získat seřazené prvky, podporuje knihovna Mori dvě implementace množin – množiny založené na hešovací tabulce a množiny se setříděnými prvky založené na stromech.

4.1 Funkce mori.set() a mori.sortedSet()

Podívejme se nyní na konstruktory množin, které jsou představovány funkcemi mori.set() a mori.sortedSet(). První z těchto funkcí vytvoří množinu (založenou na hešovací mapě, ovšem komplikovanějším způsobem, než je to běžné) ze sekvence, druhá funkce vytvoří množinu (založenou na stromu) kupodivu nikoli ze sekvence, ale z hodnot, které jsou této funkci přímo předány. Podívejme se na příklady konstrukce množin:

// množina se čtyřmi prvky
var set1 = mori.set([1,2,3,4]);
#{1 2 3 4}
 
// množina se čtyřmi prvky
// (pořadí zůstává nezměněno, a to díky interní implementaci množin)
var set2 = mori.set([4,3,2,1]);
#{4 3 2 1}
 
// zde se projeví první vlastnost množiny: každý prvek je uložen maximálně jedenkrát
var set3 = mori.set([1,100,1,1]);
#{1 100}
 
// i zde se projeví první vlastnost množiny: každý prvek je uložen maximálně jedenkrát
var set4 = mori.set(["C", "C++", "Java", "JavaScript", "D", "Lua", "C"])
#{"C" "C++" "Java" "JavaScript" "D" "Lua"}
 
// konstrukce množiny ze sekvence
// (povšimněte si způsobu „rozházení“ prvků)
var hugeSet = mori.set(mori.range(0,100))
#{0 32 64 96 1 33 65 97 2 34 66 98 3 35 67 99 4 36 68 5 37
 69 6 38 70 7 39 71 8 40 72 9 41 73 10 42 74 11 43 75 12 44
 76 13 45 77 14 46 78 15 47 79 16 48 80 17 49 81 18 50 82
 19 51 83 20 52 84 21 53 85 22 54 86 23 55 87 24 56 88 25
 57 89 26 58 90 27 59 91 28 60 92 29 61 93 30 62 94 31 63 95}
 
// množina se setříděnými prvky
var set5 = mori.sortedSet(1,2,3,4);
#{1 2 3 4}
 
// množina se setříděnými prvky
var set6 = mori.sortedSet(4,3,2,1);
#{1 2 3 4}
 
// množina se setříděnými a unikátními prvky
var set7 = mori.sortedSet(1,100,1,1);
#{1 100}
 
// množina se setříděnými a unikátními prvky
var set8 = mori.sortedSet("C", "C++", "Java", "JavaScript", "D", "Lua", "C")
#{"C" "C++" "D" "Java" "JavaScript" "Lua"}

4.2 Sjednocení, průnik a rozdíl množin

Mezi základní operace s množinami patří jejich sjednocení, průnik a rozdíl, které jsou v knihovně Mori představovány funkcemi mori.union(), mori.intersection() a mori.difference(). Chování těchto funkcí by mělo být známé, nicméně si ho pro jistotu otestujme:

// první množina s deseti prvky 0..9
var set1 = mori.set(mori.range(0,10));
#{0 1 2 3 4 5 6 7 8 9}
 
// druhá množina se šesti prvky 0..5
var set2 = mori.set(mori.range(0,6));
#{0 1 2 3 4 5}
 
// třetí množina se šesti prvky 4..9
var set3 = mori.set(mori.range(4,10));
#{4 5 6 7 8 9}
 
// sjednocení množin
mori.union(set2, set3)
#{0 1 2 3 4 5 6 7 8 9}
 
// průnik množin: množiny set2 a set3 se překrývají prvky 4 a 5
mori.intersection(set2, set3)
#{4 5}
 
// rozdíl množin, jsou odebrány dva překrývající se prvky
mori.difference(set2, set3)
#{0 1 2 3}
 
// rozdíl množin, jsou odebrány dva překrývající se prvky
mori.difference(set3, set2)
#{6 7 8 9}
 
// rozdíl množin, vše co zbývá z množiny set1 po odebrání prvků nalezených i v set2
mori.difference(set1, set2)
#{6 7 8 9}
 
// rozdíl množin, vše co zbývá z množiny set1 po odebrání prvků nalezených i v set3
mori.difference(set1, set3)
#{0 1 2 3}

4.3 Demonstrační příklady

Výše popsané funkce pro práci s množinami jsou součástí dvojice demonstračních příkladů, jejichž zdrojové kódy budou vypsány pod tímto odstavcem, a to včetně HTML stránek sloužících pro spuštění příkladů ve webovém prohlížeči.

mori₉.js

// ------------------------------------------------------------
// Knihovna Mori: demonstracni priklad cislo 9
//
// Zakladni vlastnosti mnozin
// ------------------------------------------------------------
 
 
 
// ziskani typu sekvence
function sequenceType(sequence) {
    return mori.isList(sequence)   ? "list" :
           mori.isVector(sequence) ? "vector" :
           mori.isMap(sequence)    ? "map" :
           mori.isSet(sequence)    ? "set" :
           mori.isSeq(sequence)    ? "sequence" :
           "unknown";
}
 
 
 
// vypis informaci o vybrane sekvenci
function printSequenceInfo(declaration) {
    var sequence = eval(declaration);
    var type = sequenceType(sequence);
    console.log("---------------------------------");
    console.log(declaration);
    console.log("type:    " + type);
    console.log("length:  " + mori.count(sequence));
    console.log("content: " + sequence);
}
 
var set1 = mori.set([1,2,3,4]);
var set2 = mori.set([4,3,2,1]);
var set3 = mori.set([1,100,1,1]);
var set4 = mori.set(["C", "C++", "Java", "JavaScript", "D", "Lua", "C"])
 
var set5 = mori.sortedSet(1,2,3,4);
var set6 = mori.sortedSet(4,3,2,1);
var set7 = mori.sortedSet(1,100,1,1);
var set8 = mori.sortedSet("C", "C++", "Java", "JavaScript", "D", "Lua", "C")
 
var hugeSet = mori.set(mori.range(0,100))
 
printSequenceInfo("set1");
printSequenceInfo("set2");
printSequenceInfo("set3");
printSequenceInfo("set4");
printSequenceInfo("set5");
printSequenceInfo("set6");
printSequenceInfo("set7");
printSequenceInfo("set8");
printSequenceInfo("hugeSet");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

mori₀₉.html

<!doctype html>
<html>
    <head>
        <title>Mori tests #09</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_09.js"></script>
    </head>
    <body>
        <h1>Mori tests #09</h1>
    </body>
</html>

mori₁₀.js

// ------------------------------------------------------------
// Knihovna Mori: demonstracni priklad cislo 10
//
// Operace s mnozinami
// ------------------------------------------------------------
 
 
 
// ziskani typu sekvence
function sequenceType(sequence) {
    return mori.isList(sequence)   ? "list" :
           mori.isVector(sequence) ? "vector" :
           mori.isMap(sequence)    ? "map" :
           mori.isSet(sequence)    ? "set" :
           mori.isSeq(sequence)    ? "sequence" :
           "unknown";
}
 
 
 
// vypis informaci o vybrane sekvenci
function printSequenceInfo(declaration) {
    var sequence = eval(declaration);
    var type = sequenceType(sequence);
    console.log("---------------------------------");
    console.log(declaration);
    console.log("type:    " + type);
    console.log("length:  " + mori.count(sequence));
    console.log("content: " + sequence);
}
 
var set1 = mori.set(mori.range(0,10));
var set2 = mori.set(mori.range(0,6));
var set3 = mori.set(mori.range(4,10));
 
printSequenceInfo("set1");
printSequenceInfo("set2");
printSequenceInfo("set3");
printSequenceInfo("mori.union(set2, set3)");
printSequenceInfo("mori.intersection(set2, set3)");
printSequenceInfo("mori.difference(set2, set3)");
printSequenceInfo("mori.difference(set3, set2)");
printSequenceInfo("mori.difference(set1, set2)");
printSequenceInfo("mori.difference(set1, set3)");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

mori₁₀.html

<!doctype html>
<html>
    <head>
        <title>Mori tests #10</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_10.js"></script>
    </head>
    <body>
        <h1>Mori tests #10</h1>
    </body>
</html>

5. Operace s mapami

Mapy (asociativní pole) jakožto strukturovaný datový typ pravděpodobně není nutné čtenářům tohoto článku podrobněji představovat, protože tento datový typ je podporovaný mnoha různými programovacími jazyky, samozřejmě včetně JavaScriptu. Podobně jako je tomu u množin, i mapy jsou v knihovně Mori implementovány dvěma způsoby – buď s využitím hešovací mapy či stromem. Záleží tedy pouze na vývojáři, který typ mapy využije, a to v závislosti na tom, zda je nutné prvky z mapy získávat seřazené (podle klíče) či v náhodném pořadí. Zajímavé je, že klíče mohou být jakéhokoli typu, což možná překvapí programátory v Javě, v níž mohou být klíče pouze objektového typu (reference).

5.1 Funkce mori.hashMap() a mori.sortedMap()

Nejprve si ukažme způsob konstrukce map, a to jak map založených na hešovací funkci, tak i map založených na použití stromu:

// mapa s nesetříděnými dvojicemi klíč-hodnota
mori.hashMap("k9", 9, "k8", 8, "k7", 7, "k6", 6, "k5", 5, "k4", 4, "k3", 3, "k2", 2, "k1", 1);
{"k8" 8, "k7" 7, "k9" 9, "k6" 6, "k5" 5, "k3" 3, "k1" 1, "k4" 4, "k2" 2}
 
// mapa se setříděnými dvojicemi klíč-hodnota
mori.sortedMap("k9", 9, "k8", 8, "k7", 7, "k6", 6, "k5", 5, "k4", 4, "k3", 3, "k2", 2, "k1", 1);
{"k1" 1, "k2" 2, "k3" 3, "k4" 4, "k5" 5, "k6" 6, "k7" 7, "k8" 8, "k9" 9}
 
// mapa s nesetříděnými dvojicemi klíč-hodnota
// (to, že se pořadí prvků nezměnilo, je způsobeno malou velikostí mapy)
mori.hashMap("first", 1, "second", 2, "third", 3);
{"first" 1, "second" 2, "third" 3}

5.2 Získání klíčů, hodnot a sloučení map

Pro získání všech klíčů z libovolné mapy slouží funkce mori.keys(), pro získání všech hodnot pak (logicky) funkce nazvaná mori.vals(). Další důležitou funkcí, která se v programech používá poměrně často, je funkce mori.merge(), která sloučí dvě mapy. Ve chvíli, kdy v obou slučovaných mapách existují dvojice se stejnými klíči, dostane přednost dvojice získaná z druhé mapy:

// mapa s nesetříděnými dvojicemi klíč-hodnota
var map1 = mori.hashMap("k9", 9, "k8", 8, "k7", 7, "k6", 6, "k5", 5, "k4", 4, "k3", 3, "k2", 2, "k1", 1);
 
// mapa se setříděnými dvojicemi klíč-hodnota
var map2 = mori.sortedMap("k9", 9, "k8", 8, "k7", 7, "k6", 6, "k5", 5, "k4", 4, "k3", 3, "k2", 2, "k1", 1);
 
// mapa s nesetříděnými dvojicemi klíč-hodnota
var map3 = mori.hashMap("first", 1, "second", 2, "third", 3);
 
// klíče z první mapy
mori.keys(map1)
("k8" "k7" "k9" "k6" "k5" "k3" "k1" "k4" "k2")
 
// klíče (setříděné) z druhé mapy
mori.keys(map2)
("k1" "k2" "k3" "k4" "k5" "k6" "k7" "k8" "k9")
 
// hodnoty z první mapy
mori.vals(map1)
(8 7 9 6 5 3 1 4 2)
 
// hodnoty z druhé mapy
mori.vals(map2)
(1 2 3 4 5 6 7 8 9)
 
// sjednocení map 1 a 3
mori.merge(map1, map3)
{"k8" 8, "k7" 7, "k9" 9, "k6" 6, "k5" 5, "second" 2,
 "k3" 3, "third" 3, "k1" 1, "k4" 4, "k2" 2, "first" 1}

5.3 Funkce mori.assoc(), mori.dissoc() a mori.zipmap()

Mapy jsou sice, podobně jako i všechny ostatní datové struktury poskytované knihovnou Mori, perzistentní, ovšem to neznamená, že neexistují funkce, které dokážou vrátit novou mapu s přidanou dvojicí klíč-hodnota, či naopak s odebranou dvojicí klíč-hodnota (interně se používá sdílení struktury, takže se nemusíte bát, že se musí jednat o časově náročné operace). První z těchto funkcí se jmenuje mori.assoc() (přidání dat, přesněji vrácení nové mapy s přidanou dvojicí klíč-hodnota), druhá funkce se jmenuje mori.dissoc (odebrání dat). U složitějších (vnořených) map se použije funkce mori.assocIn() a mori.updateIn():

// mapa použitá pro přidání a ubrání prvku
var map2 = mori.sortedMap(1, "first", 2, "second", 3, "third");
 
// výpis obsahu mapy
map2;
{1 "first", 2 "second", 3 "third"}
 
// přidání dvojice klíč-hodnota do mapy
mori.assoc(map2, 4, 'fourth', 5, 'fifth');
{1 "first", 2 "second", 3 "third", 4 "fourth", 5 "fifth"}
 
// odebrání vybraných dvojic klíč-hodnota z mapy (dvojice jsou určeny klíči)
mori.dissoc(map2, 1, 5);
{2 "second", 3 "third"}

Nesmíme zapomenout ani na velmi užitečnou funkci nazvanou mori.zipmap(), která dokáže vytvořit mapu ze dvou sekvencí, přičemž z první sekvence se získají klíče a ze sekvence druhé pak hodnoty. Jedná se tedy o jakousi obdobu funkce mori.interleave(), ovšem vytvořenou přesně pro mapy. Podívejme se na příklad použití:

// funkce použitá pro výpočet druhé sekvence
function factorial(n) {
    var fac = 1;
    for (var i = 2; i <= n; i++) {
        fac = fac * i;
    }
    return fac;
}
 
 
 
// první sekvence čísel 1 až 10
var seq1 = mori.range(1,11);
(1 2 3 4 5 6 7 8 9 10)
 
// druhá sekvence obsahuje faktoriály čísel 1 až 10
var seq2 = mori.map(factorial, seq1);
(1 2 6 24 120 720 5040 40320 362880 3628800)
 
// z obou sekvencí vytvoříme mapu
mori.zipmap(seq1, seq2);
{1 1, 2 2, 3 6, 4 24, 5 120, 6 720, 7 5040, 8 40320, 9 362880, 10 3628800}

5.4 Demonstrační příklady

Výše popsané funkce pro práci s mapami jsou součástí dvojice demonstračních příkladů, jejichž zdrojové kódy budou vypsány pod tímto odstavcem, a to včetně HTML stránek sloužících pro spuštění příkladů ve webovém prohlížeči.

mori₁₁.js

// ------------------------------------------------------------
// Knihovna Mori: demonstracni priklad cislo 11
//
// Zakladni vlastnosti map
// ------------------------------------------------------------
 
 
 
// ziskani typu sekvence
function sequenceType(sequence) {
    return mori.isList(sequence)   ? "list" :
           mori.isVector(sequence) ? "vector" :
           mori.isMap(sequence)    ? "map" :
           mori.isSet(sequence)    ? "set" :
           mori.isSeq(sequence)    ? "sequence" :
           "unknown";
}
 
 
 
// vypis informaci o vybrane sekvenci
function printSequenceInfo(declaration) {
    var sequence = eval(declaration);
    var type = sequenceType(sequence);
    console.log("---------------------------------");
    console.log(declaration);
    console.log("type:    " + type);
    console.log("length:  " + mori.count(sequence));
    console.log("content: " + sequence);
}
 
var map1 = mori.hashMap  ("k9", 9, "k8", 8, "k7", 7, "k6", 6, "k5", 5, "k4", 4, "k3", 3, "k2", 2, "k1", 1);
var map2 = mori.sortedMap("k9", 9, "k8", 8, "k7", 7, "k6", 6, "k5", 5, "k4", 4, "k3", 3, "k2", 2, "k1", 1);
var map3 = mori.hashMap("first", 1, "second", 2, "third", 3);
 
printSequenceInfo("map1");
printSequenceInfo("map2");
printSequenceInfo("mori.keys(map1)");
printSequenceInfo("mori.keys(map2)");
printSequenceInfo("mori.vals(map1)");
printSequenceInfo("mori.vals(map2)");
printSequenceInfo("map3");
printSequenceInfo("mori.merge(map1, map3)");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

mori₁₁.html

<!doctype html>
<html>
    <head>
        <title>Mori tests #11</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_11.js"></script>
    </head>
    <body>
        <h1>Mori tests #11</h1>
    </body>
</html>

mori₁₂.js

// ------------------------------------------------------------
// Knihovna Mori: demonstracni priklad cislo 12
//
// Operace s mapami
// ------------------------------------------------------------
 
 
 
// ziskani typu sekvence
function sequenceType(sequence) {
    return mori.isList(sequence)   ? "list" :
           mori.isVector(sequence) ? "vector" :
           mori.isMap(sequence)    ? "map" :
           mori.isSet(sequence)    ? "set" :
           mori.isSeq(sequence)    ? "sequence" :
           "unknown";
}
 
 
 
// vypis informaci o vybrane sekvenci
function printSequenceInfo(declaration) {
    var sequence = eval(declaration);
    var type = sequenceType(sequence);
    console.log("---------------------------------");
    console.log(declaration);
    console.log("type:    " + type);
    console.log("length:  " + mori.count(sequence));
    console.log("content: " + sequence);
}
 
function factorial(n) {
    var fac = 1;
    for (var i = 2; i <= n; i++) {
        fac = fac * i;
    }
    return fac;
}
 
var seq1 = mori.range(1,11);
var seq2 = mori.map(factorial, seq1);
 
var map1 = mori.zipmap(seq1, seq2);
 
printSequenceInfo("seq1");
printSequenceInfo("seq2");
printSequenceInfo("mori.zipmap(seq1, seq2);");
 
 
var map2 = mori.sortedMap(1, "first", 2, "second", 3, "third");
printSequenceInfo("map2");
printSequenceInfo("mori.assoc(map2, 4, 'fourth', 5, 'fifth')");
printSequenceInfo("mori.dissoc(map2, 1, 5)");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

mori₁₂.html

<!doctype html>
<html>
    <head>
        <title>Mori tests #12</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_12.js"></script>
    </head>
    <body>
        <h1>Mori tests #12</h1>
    </body>
</html>

6. Obsah dalšího článku – porovnání Mori s knihovnou Immutable.js

Knihovna Mori ve skutečnosti (a vlastně i podle očekávání) není jedinou knihovnou, která do programovacího jazyka JavaScript přidává podporu pro perzistentní strukturované datové typy. V souvislosti s rostoucí oblibou funkcionálního programování (resp. přesněji řečeno funkcionálních technik „naroubovaných“ do mainstreamových programovacích jazyků) se objevily i další knihovny mající podobný cíl. Druhou známou knihovnou je JavaScriptová knihovna nazvaná Immutable.js. Shodnými rysy ale i mnohými rozdíly mezi Mori a Immutable.js se budeme zabývat v navazujícím článku.

7. Repositář se zdrojovými kódy všech dnešních demonstračních příkladů

Demonstrační příklady, na nichž jsme si ukazovali vlastnosti knihovny Mori, byly uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/pre­sentations. V tabulce zobrazené pod tímto odstavcem naleznete na zdrojové kódy těchto příkladů přímé odkazy:

8. Odkazy na Internetu

1. Mori na GitHubu
   https://github.com/swannodette/mori
2. Mori: popis API (dokumentace)
   http://swannodette.github.io/mori/
3. Mori: Benchmarking
   https://github.com/swanno­dette/mori/wiki/Benchmarking
4. Functional data structures in JavaScript with Mori
   http://sitr.us/2013/11/04/functional-data-structures.html
5. Immutable.js
   https://facebook.github.io/immutable-js/
6. Persistent data structure
   https://en.wikipedia.org/wi­ki/Persistent_data_structu­re
7. Understanding Clojure's Persistent Vectors, pt. 1
   http://hypirion.com/musin­gs/understanding-persistent-vector-pt-1
8. Hash array mapped trie (Wikipedia)
   https://en.wikipedia.org/wi­ki/Hash_array_mapped_trie
9. Java theory and practice: To mutate or not to mutate?
   http://www.ibm.com/develo­perworks/java/library/j-jtp02183/index.html
10. Efficient persistent (immutable) data structures
    https://persistent.codeplex.com/
11. Netscape Enterprise Server (Wikipedia)
    https://en.wikipedia.org/wi­ki/Netscape_Enterprise_Ser­ver
12. SSJS Reference Guide (Server-Side JavaScript)
    http://docs.oracle.com/cd/E19957–01/816–6410–10/816–6410–10.pdf
13. Atom: moderní textový editor
    http://www.root.cz/clanky/atom-moderni-textovy-editor/
14. Atom: moderní textový editor (dokončení)
    http://www.root.cz/clanky/atom-moderni-textovy-editor-dokonceni/
15. Propojení světa LISPu se světem JavaScriptu s využitím transpřekladače Wisp
    http://www.root.cz/clanky/propojeni-sveta-lispu-se-svetem-javascriptu-s-vyuzitim-transprekladace-wisp/
16. Propojení světa LISPu se světem JavaScriptu s využitím transpřekladače Wisp (2.část)
    http://www.root.cz/clanky/propojeni-sveta-lispu-se-svetem-javascriptu-s-vyuzitim-transprekladace-wisp-2-cast/
17. Wisp na GitHubu
    https://github.com/Gozala/wisp
18. Wisp playground
    http://www.jeditoolkit.com/try-wisp/
19. REPL v prohlížeči
    http://www.jeditoolkit.com/in­teractivate-wisp/
20. Minification (programming)
    https://en.wikipedia.org/wi­ki/Minification_(programmin­g)
21. 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
22. Clojure Macro Tutorial (Part II: The Compiler Strikes Back)
    http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-ii-compiler.html
23. Clojure Macro Tutorial (Part III: Syntax Quote)
    http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-ii-syntax.html
24. Tech behind Tech: Clojure Macros Simplified
    http://techbehindtech.com/2010/09/28/clo­jure-macros-simplified/
25. Fatvat – Exploring functional programming: Clojure Macros
    http://www.fatvat.co.uk/2009/02/clo­jure-macros.html
26. Eulerovo číslo
    http://cs.wikipedia.org/wi­ki/Eulerovo_??slo
27. List comprehension
    http://en.wikipedia.org/wi­ki/List_comprehension
28. List Comprehensions in Clojure
    http://asymmetrical-view.com/2008/11/18/list-comprehensions-in-clojure.html
29. Clojure Programming Concepts: List Comprehension
    http://en.wikibooks.org/wi­ki/Clojure_Programming/Con­cepts#List_Comprehension
30. Clojure core API: for macro
    http://clojure.github.com/clo­jure/clojure.core-api.html#clojure.core/for
31. cirrus machina – The Clojure for macro
    http://www.cirrusmachina.com/blog/com­ment/the-clojure-for-macro/
32. Clojure.org: Clojure home page
    http://clojure.org/downloads
33. Clojure.org: Vars and the Global Environment
    http://clojure.org/Vars
34. Clojure.org: Refs and Transactions
    http://clojure.org/Refs
35. Clojure.org: Atoms
    http://clojure.org/Atoms
36. Clojure.org: Agents as Asynchronous Actions
    http://clojure.org/agents
37. A Couple of Clojure Agent Examples
    http://lethain.com/a-couple-of-clojure-agent-examples/
38. Clojure – Functional Programming for the JVM
    http://java.ociweb.com/mar­k/clojure/article.html
39. Clojure quick reference
    http://faustus.webatu.com/clj-quick-ref.html
40. 4Clojure
    http://www.4clojure.com/
41. ClojureDoc
    http://clojuredocs.org/
42. Clojure (Wikipedia EN)
    http://en.wikipedia.org/wiki/Clojure
43. Clojure (Wikipedia CS)
    http://cs.wikipedia.org/wiki/Clojure
44. Riastradh's Lisp Style Rules
    http://mumble.net/~campbe­ll/scheme/style.txt
45. Dynamic Languages Strike Back
    http://steve-yegge.blogspot.cz/2008/05/dynamic-languages-strike-back.html
46. Scripting: Higher Level Programming for the 21st Century
    http://www.tcl.tk/doc/scripting.html
47. Java Virtual Machine Support for Non-Java Languages
    http://docs.oracle.com/ja­vase/7/docs/technotes/gui­des/vm/multiple-language-support.html
48. The Lua VM, on the Web
    https://kripken.github.io/lu­a.vm.js/lua.vm.js.html
49. Lua.vm.js REPL
    https://kripken.github.io/lu­a.vm.js/repl.html
50. lua2js
    https://www.npmjs.com/package/lua2js
51. lua2js na GitHubu
    https://github.com/basicer/lua2js-dist
52. Seriál o programovacím jazyku Lua
    http://www.root.cz/serialy/pro­gramovaci-jazyk-lua/
53. Source-to-source compiler
    https://en.wikipedia.org/wiki/Source-to-source_compiler
54. JavaScript is Assembly Language for the Web: Sematic Markup is Dead! Clean vs. Machine-coded HTML
    http://www.hanselman.com/blog/Ja­vaScriptIsAssemblyLanguage­ForTheWebSematicMarkupIsDe­adCleanVsMachinecodedHTML­.aspx
55. JavaScript is Web Assembly Language and that's OK.
    http://www.hanselman.com/blog/Ja­vaScriptIsWebAssemblyLangu­ageAndThatsOK.aspx
56. Dart
    https://www.dartlang.org/
57. CoffeeScript
    http://coffeescript.org/
58. TypeScript
    http://www.typescriptlang.org/
59. Lua (programming language)
    http://en.wikipedia.org/wi­ki/Lua_(programming_langu­age)
60. Static single assignment form (SSA)
    http://en.wikipedia.org/wi­ki/Static_single_assignmen­t_form
61. LuaJIT 2.0 SSA IRhttp://wiki.luajit.org/SSA-IR-2.0
62. The LuaJIT Project
    http://luajit.org/index.html
63. LuaJIT FAQ
    http://luajit.org/faq.html
64. LuaJIT Performance Comparison
    http://luajit.org/performance.html
65. LuaJIT 2.0 intellectual property disclosure and research opportunities
    http://article.gmane.org/gma­ne.comp.lang.lua.general/58908
66. LuaJIT Wiki
    http://wiki.luajit.org/Home
67. LuaJIT 2.0 Bytecode Instructions
    http://wiki.luajit.org/Bytecode-2.0
68. Programming in Lua (first edition)
    http://www.lua.org/pil/contents.html
69. Lua 5.2 sources
    http://www.lua.org/source/5.2/
70. Tcl Plugin Version 3
    http://www.tcl.tk/software/plugin/
71. JavaScript: The Web Assembly Language?
    http://www.informit.com/ar­ticles/article.aspx?p=1856657
72. asm.js
    http://asmjs.org/
73. List of languages that compile to JS
    https://github.com/jashke­nas/coffeescript/wiki/List-of-languages-that-compile-to-JS
74. REPL
    https://en.wikipedia.org/wi­ki/Read%E2%80%93eval%E2%80%93prin­t_loop
75. The LLVM Compiler Infrastructure
    http://llvm.org/ProjectsWithLLVM/
76. clang: a C language family frontend for LLVM
    http://clang.llvm.org/
77. emscripten
    http://kripken.github.io/emscripten-site/
78. LLVM Backend („Fastcomp“)
    http://kripken.github.io/emscripten-site/docs/building_from_source/LLVM-Backend.html#llvm-backend
79. Emscripten – Fastcomp na GitHubu
    https://github.com/kripken/emscripten-fastcomp
80. Clang (pro Emscripten) na GitHubu
    https://github.com/kripken/emscripten-fastcomp-clang
81. Why not use JavaScript?
    https://ckknight.github.i­o/gorillascript/