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()
3. Použití funkcí vyššího řádu v knihovně Mori při zpracování sekvencí
4.1 Funkce mori.set() a mori.sortedSet()
4.2 Sjednocení, průnik a rozdíl množin
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()
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ů
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.
mori05.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
// ------------------------------------------------------------
mori05.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>
mori06.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
// ------------------------------------------------------------
mori06.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>
mori07.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
// ------------------------------------------------------------
mori07.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 mori08:
mori08.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
// ------------------------------------------------------------
mori08.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.
mori9.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
// ------------------------------------------------------------
mori09.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>
mori10.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
// ------------------------------------------------------------
mori10.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.
mori11.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
// ------------------------------------------------------------
mori11.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>
mori12.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
// ------------------------------------------------------------
mori12.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/presentations. V tabulce zobrazené pod tímto odstavcem naleznete na zdrojové kódy těchto příkladů přímé odkazy:
8. Odkazy na Internetu
- Mori na GitHubu
https://github.com/swannodette/mori - Mori: popis API (dokumentace)
http://swannodette.github.io/mori/ - Mori: Benchmarking
https://github.com/swannodette/mori/wiki/Benchmarking - Functional data structures in JavaScript with Mori
http://sitr.us/2013/11/04/functional-data-structures.html - Immutable.js
https://facebook.github.io/immutable-js/ - Persistent data structure
https://en.wikipedia.org/wiki/Persistent_data_structure - Understanding Clojure's Persistent Vectors, pt. 1
http://hypirion.com/musings/understanding-persistent-vector-pt-1 - Hash array mapped trie (Wikipedia)
https://en.wikipedia.org/wiki/Hash_array_mapped_trie - Java theory and practice: To mutate or not to mutate?
http://www.ibm.com/developerworks/java/library/j-jtp02183/index.html - Efficient persistent (immutable) data structures
https://persistent.codeplex.com/ - Netscape Enterprise Server (Wikipedia)
https://en.wikipedia.org/wiki/Netscape_Enterprise_Server - SSJS Reference Guide (Server-Side JavaScript)
http://docs.oracle.com/cd/E19957–01/816–6410–10/816–6410–10.pdf - Atom: moderní textový editor
http://www.root.cz/clanky/atom-moderni-textovy-editor/ - Atom: moderní textový editor (dokončení)
http://www.root.cz/clanky/atom-moderni-textovy-editor-dokonceni/ - 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/ - 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/ - Wisp na GitHubu
https://github.com/Gozala/wisp - Wisp playground
http://www.jeditoolkit.com/try-wisp/ - REPL v prohlížeči
http://www.jeditoolkit.com/interactivate-wisp/ - Minification (programming)
https://en.wikipedia.org/wiki/Minification_(programming) - Clojure Macro Tutorial (Part I, Getting the Compiler to Write Your Code For You)
http://www.learningclojure.com/2010/09/clojure-macro-tutorial-part-i-getting.html - Clojure Macro Tutorial (Part II: The Compiler Strikes Back)
http://www.learningclojure.com/2010/09/clojure-macro-tutorial-part-ii-compiler.html - Clojure Macro Tutorial (Part III: Syntax Quote)
http://www.learningclojure.com/2010/09/clojure-macro-tutorial-part-ii-syntax.html - Tech behind Tech: Clojure Macros Simplified
http://techbehindtech.com/2010/09/28/clojure-macros-simplified/ - Fatvat – Exploring functional programming: Clojure Macros
http://www.fatvat.co.uk/2009/02/clojure-macros.html - Eulerovo číslo
http://cs.wikipedia.org/wiki/Eulerovo_??slo - List comprehension
http://en.wikipedia.org/wiki/List_comprehension - List Comprehensions in Clojure
http://asymmetrical-view.com/2008/11/18/list-comprehensions-in-clojure.html - Clojure Programming Concepts: List Comprehension
http://en.wikibooks.org/wiki/Clojure_Programming/Concepts#List_Comprehension - Clojure core API: for macro
http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/for - cirrus machina – The Clojure for macro
http://www.cirrusmachina.com/blog/comment/the-clojure-for-macro/ - Clojure.org: Clojure home page
http://clojure.org/downloads - Clojure.org: Vars and the Global Environment
http://clojure.org/Vars - Clojure.org: Refs and Transactions
http://clojure.org/Refs - Clojure.org: Atoms
http://clojure.org/Atoms - Clojure.org: Agents as Asynchronous Actions
http://clojure.org/agents - A Couple of Clojure Agent Examples
http://lethain.com/a-couple-of-clojure-agent-examples/ - Clojure – Functional Programming for the JVM
http://java.ociweb.com/mark/clojure/article.html - Clojure quick reference
http://faustus.webatu.com/clj-quick-ref.html - 4Clojure
http://www.4clojure.com/ - ClojureDoc
http://clojuredocs.org/ - Clojure (Wikipedia EN)
http://en.wikipedia.org/wiki/Clojure - Clojure (Wikipedia CS)
http://cs.wikipedia.org/wiki/Clojure - Riastradh's Lisp Style Rules
http://mumble.net/~campbell/scheme/style.txt - Dynamic Languages Strike Back
http://steve-yegge.blogspot.cz/2008/05/dynamic-languages-strike-back.html - Scripting: Higher Level Programming for the 21st Century
http://www.tcl.tk/doc/scripting.html - Java Virtual Machine Support for Non-Java Languages
http://docs.oracle.com/javase/7/docs/technotes/guides/vm/multiple-language-support.html - The Lua VM, on the Web
https://kripken.github.io/lua.vm.js/lua.vm.js.html - Lua.vm.js REPL
https://kripken.github.io/lua.vm.js/repl.html - lua2js
https://www.npmjs.com/package/lua2js - lua2js na GitHubu
https://github.com/basicer/lua2js-dist - Seriál o programovacím jazyku Lua
http://www.root.cz/serialy/programovaci-jazyk-lua/ - Source-to-source compiler
https://en.wikipedia.org/wiki/Source-to-source_compiler - JavaScript is Assembly Language for the Web: Sematic Markup is Dead! Clean vs. Machine-coded HTML
http://www.hanselman.com/blog/JavaScriptIsAssemblyLanguageForTheWebSematicMarkupIsDeadCleanVsMachinecodedHTML.aspx - JavaScript is Web Assembly Language and that's OK.
http://www.hanselman.com/blog/JavaScriptIsWebAssemblyLanguageAndThatsOK.aspx - Dart
https://www.dartlang.org/ - CoffeeScript
http://coffeescript.org/ - TypeScript
http://www.typescriptlang.org/ - Lua (programming language)
http://en.wikipedia.org/wiki/Lua_(programming_language) - Static single assignment form (SSA)
http://en.wikipedia.org/wiki/Static_single_assignment_form - LuaJIT 2.0 SSA IRhttp://wiki.luajit.org/SSA-IR-2.0
- The LuaJIT Project
http://luajit.org/index.html - LuaJIT FAQ
http://luajit.org/faq.html - LuaJIT Performance Comparison
http://luajit.org/performance.html - LuaJIT 2.0 intellectual property disclosure and research opportunities
http://article.gmane.org/gmane.comp.lang.lua.general/58908 - LuaJIT Wiki
http://wiki.luajit.org/Home - LuaJIT 2.0 Bytecode Instructions
http://wiki.luajit.org/Bytecode-2.0 - Programming in Lua (first edition)
http://www.lua.org/pil/contents.html - Lua 5.2 sources
http://www.lua.org/source/5.2/ - Tcl Plugin Version 3
http://www.tcl.tk/software/plugin/ - JavaScript: The Web Assembly Language?
http://www.informit.com/articles/article.aspx?p=1856657 - asm.js
http://asmjs.org/ - List of languages that compile to JS
https://github.com/jashkenas/coffeescript/wiki/List-of-languages-that-compile-to-JS - REPL
https://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop - The LLVM Compiler Infrastructure
http://llvm.org/ProjectsWithLLVM/ - clang: a C language family frontend for LLVM
http://clang.llvm.org/ - emscripten
http://kripken.github.io/emscripten-site/ - LLVM Backend („Fastcomp“)
http://kripken.github.io/emscripten-site/docs/building_from_source/LLVM-Backend.html#llvm-backend - Emscripten – Fastcomp na GitHubu
https://github.com/kripken/emscripten-fastcomp - Clang (pro Emscripten) na GitHubu
https://github.com/kripken/emscripten-fastcomp-clang - Why not use JavaScript?
https://ckknight.github.io/gorillascript/
