Hlavní navigace

Funkce vyššího řádu v knihovně Underscore

15. 3. 2016
Doba čtení: 25 minut

Sdílet

Ve druhém článku o JavaScriptové knihovně Underscore se seznámíme s použitím funkcí vyššího řádu, která tato knihovna vývojářům nabízí. Díky nim lze mnoho algoritmů zjednodušit a zkrátit.

Obsah

1. Funkce vyššího řádu v knihovně Underscore

2. Funkce map a její význam při práci s kolekcemi

3. První demonstrační příklad – použití funkce map při práci s poli či kolekcemi

4. Výběr prvků z kolekcí pomocí funkcí filterreject

5. Druhý demonstrační příklad – použití funkcí filterreject

6. Rozhodování na základě stavu kolekcí zjištěných funkcemi someevery

7. Třetí demonstrační příklad – použití funkcí someevery

8. Kombinace chování filter a reject: funkce partition

9. Čtvrtý demonstrační příklad – použití funkce partition

10. Funkce reduce a reduceRight

11. Pátý demonstrační příklad – použití funkcí reduce a reduceRight

12. Výpočet faktoriálu s použitím funkce reduce

13. Šestý demonstrační příklad – funkce each a reduce při výpočtu faktoriálu

14. Repositář s demonstračními příklady

15. Odkazy na Internetu

1. Funkce vyššího řádu v knihovně Underscore

Ve druhé části článku o knihovně Underscore, která přináší do JavaScriptu některé prvky funkcionálního programování, si na šestici demonstračních příkladů ukážeme použití takzvaných funkcí vyššího řádu, což jsou v tomto případě funkce, která jako jeden ze svých parametrů akceptují jiné funkce (ať již pojmenované či anonymní). Jedná se konkrétně o funkce určené pro práci s poli a obecnými kolekcemi. V knihovně Underscore nalezneme základní trojici funkcí známých z prakticky všech funkcionálních jazyků: map, filter, reduce (i když někdy mívají tyto funkce odlišné názvy). Ovšem najdeme zde taktéž různé další varianty, například funkce reject (varianta na filter), reduceRight (varianta pro reduce) a taktéž some, every a partition.

Díky existenci těchto funkcí je možné ve vytvářených aplikacích do značné míry při zpracování polí a obecných kolekcí eliminovat programové smyčky, které mohou do programů zanášet zbytečné chyby (a to zejména v JavaScriptu s jeho poněkud zvláštní implementací smyčky typu for-each).

2. Funkce map a její význam při práci s kolekcemi

Pravděpodobně nejdůležitější a současně i velmi snadno pochopitelnou funkcí určenou pro zpracování kolekcí „funkcionálním“ způsobem je funkce nazvaná map. Tato funkce zpracovává všechny prvky vstupní kolekce (což budou většinou prvky běžného pole) a vytváří výslednou kolekci (většinou opět pole). Důležité je, že původní kolekce zůstane nezměněna. Funkce map při konstrukci výsledné kolekce zavolá pro každý prvek vstupní kolekce uživatelem specifikovanou funkci, jejíž návratový kód následně použije. Funkce map tedy potřebuje dva údaje: vstupní kolekci (pole) a funkci, kterou má na jednotlivé prvky této kolekce aplikovat. Tato funkce může být anonymní či neanonymní (pojmenovaná).

Ostatně se podívejme na jednoduchý příklad. Vytvoříme naprosto běžnou pojmenovanou (neanonymní) funkci akceptující nějaké číslo a vracející jeho dvojnásobnou hodnotu:

// bezna neanonymni (pojmenovana) funkce pouzita v map()
function doubleValue(value)
{
    return value*2;
}

Dále si necháme vygenerovat pole obsahující prvky 1 až 10. Použijeme přitom funkci range, s níž jsme se již seznámili minule:

// pole s prvky 1..10
var array1 = _.range(1, 11);
1,2,3,4,5,6,7,8,9,10

S použitím funkce map nyní vytvoříme nové pole, které bude mít deset prvků jako pole původní, ale hodnoty těchto prvků budou mít oproti původním prvkům dvojnásobnou hodnotu:

// vytvorime nove pole se sudymi cisly
var array2 = _.map(array1, doubleValue);
2,4,6,8,10,12,14,16,18,20

V dalším příkladu použijeme anonymní funkci, která se přímo zapíše do volání funkce map. Na první pohled to sice může vypadat poněkud nečitelně, ovšem tento způsob je vhodné si osvojit, protože je mnohdy užitečný a elegantní:

// alternativni zpusob vytvorime nove pole s prevracenymi hodnotami
// a to s pouzitim anonymni funkce
var array3 = _.map(array1, function(value) {return 1.0/value;});
1,0.5,0.3333333333333333,0.25,0.2,0.16666666666666666,0.14285714285714285,0.125,0.1111111111111111,0.1

Podívejme se nyní na použití již existujících metod základních objektů, které jsou v implementacích jazyka JavaScript dostupné. Nejprve vytvoříme pole s řetězci:

// priklad pouziti metod objektu String
// puvodni pole
var names = ["Perl", "Python", "Java", "JavaScript", "C", "C++", "Lua", "Clojure", "Forth", "APL", "BASIC"];

Všechna jména převedeme na verzálky s využitím kombinace map a String.toUpperCase

// pole obsahujici retezce psane verzalkami
var upperCaseNames = _.map(names, String.toUpperCase);

Zcela stejným způsobem si tato jména převedeme na mínusky s využitím kombinace map a String.toLowerCase

// pole obsahujici retezce psane minuskami
var lowerCaseNames = _.map(names, String.toLowerCase);

3. První demonstrační příklad – použití funkce map při práci s poli či kolekcemi

Funkce map popsaná v předchozí kapitole je použita v dnešním prvním demonstračním příkladu, jehož úplný zdrojový kód lze nalézt na adrese https://github.com/tisnik/pre­sentations/blob/master/un­derscore/underscore06.js. Povšimněte si, že se funkci map skutečně dají předat běžné (pojmenované) funkce, anonymní funkce i „metody“ již existujících objektů:

// ------------------------------------------------------------
// Knihovna Underscore.js: demonstracni priklad cislo 6
//                         Pouziti funkce map() pri praci s poli
//                         ci s kolekcemi.
// ------------------------------------------------------------
 
 
 
// funkce pro vypis informaci o vybranem poli (ci o jinem objektu)
function printArrayInfo(expression) {
    var anArray = eval(expression);
    console.log("---------------------------------");
    console.log(expression);
 
    // zjisteni typu objektu (a pripadne delky pole)
    if (anArray instanceof Array) {
        console.log("type:    array");
        console.log("length:  " + anArray.length);
    }
    // jiny typ objektu, nemame zde jistotu, ze existuje atribut length
    else {
        console.log("type:    " + typeof anArray);
    }
    console.log("content: " + anArray);
}
 
 
 
// bezna neanonymni (pojmenovana) funkce pouzita v map()
function doubleValue(value)
{
    return value*2;
}
 
 
 
// pole s prvky 1..10
var array1 = _.range(1, 11);
 
// vytvorime nove pole se sudymi cisly
var array2 = _.map(array1, doubleValue);
 
// alternativni zpusob vytvorime nove pole s prevracenymi hodnotami
// a to s pouzitim anonymni funkce
var array3 = _.map(array1, function(value) {return 1.0/value;});
 
// vypis informaci o vsech trech polich
printArrayInfo("array1");
printArrayInfo("array2");
printArrayInfo("array3");
 
 
 
// pouziti metody objektu Math
var array4 = _.map(array1, Math.sqrt);
printArrayInfo("array4");
 
 
 
// priklad pouziti metod objektu String
// puvodni pole
var names = ["Perl", "Python", "Java", "JavaScript", "C", "C++", "Lua", "Clojure", "Forth", "APL", "BASIC"];
 
// pole obsahujici retezce psane verzalkami
var upperCaseNames = _.map(names, String.toUpperCase);
 
// pole obsahujici retezce psane minuskami
var lowerCaseNames = _.map(names, String.toLowerCase);
 
// vypis informaci o vsech trech polich s retezci
printArrayInfo("names");
printArrayInfo("upperCaseNames");
printArrayInfo("lowerCaseNames");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Výstup generovaný příkladem na konzoli:

---------------------------------
array1
type:    array
length:  10
content: 1,2,3,4,5,6,7,8,9,10
---------------------------------
array2
type:    array
length:  10
content: 2,4,6,8,10,12,14,16,18,20
---------------------------------
array3
type:    array
length:  10
content: 1,0.5,0.3333333333333333,0.25,0.2,0.16666666666666666,0.14285714285714285,0.125,0.1111111111111111,0.1
---------------------------------
array4
type:    array
length:  10
content: 1,1.4142135623730951,1.7320508075688772,2,2.23606797749979,2.449489742783178,2.6457513110645907,2.8284271247461903,3,3.1622776601683795
---------------------------------
names
type:    array
length:  11
content: Perl,Python,Java,JavaScript,C,C++,Lua,Clojure,Forth,APL,BASIC
---------------------------------
upperCaseNames
type:    array
length:  11
content: PERL,PYTHON,JAVA,JAVASCRIPT,C,C++,LUA,CLOJURE,FORTH,APL,BASIC
---------------------------------
lowerCaseNames
type:    array
length:  11
content: perl,python,java,javascript,c,c++,lua,clojure,forth,apl,basic

4. Výběr prvků z kolekcí pomocí funkcí filterreject

V mnoha algoritmech je nutné vybrat prvky z nějaké kolekce na základě zadaných kritérií. Pro tento účel lze v knihovně Underscore použít funkce filter a reject. Tyto funkce akceptují stejné parametry jako funkce map: kolekci (pole) a uživatelem specifikovanou funkci. Ta má ovšem jiný význam, protože se na základě její návratové hodnoty (true či false) rozhoduje, zda se má daný prvek ze vstupní kolekce zkopírovat do kolekce výsledné či nikoli (obecně je tedy výsledná kolekce menší než kolekce vstupní).

Opět se podívejme na příklad. Vytvořme funkci-predikát, která vrací hodnotu true či false na základě testu na sudé číslo:

// bezna neanonymni (pojmenovana) funkce pouzita ve filter() a reject()
function isEven(value)
{
    return value % 2 == 0;
}

Nyní získáme všechny sudé prvky, a to pomocí filter:

// vytvorime nove pole jen se sudymi cisly
var array2 = _.filter(array1, isEven);
2,4,6,8,10

Všechny liché prvky se získají funkcí reject, která tak tvoří opak k funkci filter (v praxi nám to ušetří tvorbu predikátů s logickou negací):

// vytvorime nove pole jen s lichymi cisly
var array3 = _.reject(array1, isEven);
1,3,5,7,9

Podobně můžeme použít anonymní funkce pro získání prvků menších, popř. větších než zadaný limit:

// alternativni zpusob s vyuzitim anonymnich funkci pro ziskani
// pole cisel mensich nez 6 resp. vetsich nez 5
var array4 = _.filter(array1, function(value) {return value <= 5;});
1,2,3,4,5
var array5 = _.reject(array1, function(value) {return value <= 5;});
6,7,8,9,10

5. Druhý demonstrační příklad – použití funkcí filterreject

Použití výše popsaných funkcí nazvaných filter a reject si ukážeme v dnešním druhém demonstračním příkladu, jehož úplný zdrojový kód je vypsán pod tímto odstavcem. Těmto dvěma funkcím vyššího řádu předáváme jak anonymní funkce, tak i funkce neanonymní (pojmenované). Kterou variantu programátor v tomto případě zvolí, záleží čistě na řešené problematice (ve skutečnosti by pravděpodobně bylo jednodušší funkci isEven nepojmenovávat):

// ------------------------------------------------------------
// Knihovna Underscore.js: demonstracni priklad cislo 7
//                         Pouziti funkci filter() a reject()
//                         pri praci s poli ci s kolekcemi.
// ------------------------------------------------------------
 
 
 
// funkce pro vypis informaci o vybranem poli (ci o jinem objektu)
function printArrayInfo(expression) {
    var anArray = eval(expression);
    console.log("---------------------------------");
    console.log(expression);
 
    // zjisteni typu objektu (a pripadne delky pole)
    if (anArray instanceof Array) {
        console.log("type:    array");
        console.log("length:  " + anArray.length);
    }
    // jiny typ objektu, nemame zde jistotu, ze existuje atribut length
    else {
        console.log("type:    " + typeof anArray);
    }
    console.log("content: " + anArray);
}
 
 
 
// bezna neanonymni (pojmenovana) funkce pouzita ve filter() a reject()
function isEven(value)
{
    return value % 2 == 0;
}
 
 
 
// pole s prvky 1..10
var array1 = _.range(1, 11);
 
// vytvorime nove pole jen se sudymi cisly
var array2 = _.filter(array1, isEven);
// vytvorime nove pole jen s lichymi cisly
var array3 = _.reject(array1, isEven);
 
// vypis informaci o vsech trech polich
printArrayInfo("array1");
printArrayInfo("array2");
printArrayInfo("array3");
 
// alternativni zpusob s vyuzitim anonymnich funkci pro ziskani
// pole cisel mensich nez 6 resp. vetsich nez 5
var array4 = _.filter(array1, function(value) {return value <= 5;});
var array5 = _.reject(array1, function(value) {return value <= 5;});
 
printArrayInfo("array4");
printArrayInfo("array5");
 
 
 
// priklad s polem retezcu
// puvodni pole
var names = ["Perl", "Python", "Java", "JavaScript", "C", "C++", "Lua", "Clojure", "Forth", "APL", "BASIC"];
 
// pole obsahujici retezce psane verzalkami
var shortNames = _.filter(names, function(str) {return str.length <= 4;});
 
// pole obsahujici retezce psane minuskami
var longNames  = _.reject(names, function(str) {return str.length <= 4;});
 
// vypis informaci o vsech trech polich s retezci
printArrayInfo("names");
printArrayInfo("shortNames");
printArrayInfo("longNames");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Výstup generovaný příkladem na konzoli:

---------------------------------
array1
type:    array
length:  10
content: 1,2,3,4,5,6,7,8,9,10
---------------------------------
array2
type:    array
length:  5
content: 2,4,6,8,10
---------------------------------
array3
type:    array
length:  5
content: 1,3,5,7,9
---------------------------------
array4
type:    array
length:  5
content: 1,2,3,4,5
---------------------------------
array5
type:    array
length:  5
content: 6,7,8,9,10
---------------------------------
names
type:    array
length:  11
content: Perl,Python,Java,JavaScript,C,C++,Lua,Clojure,Forth,APL,BASIC
---------------------------------
shortNames
type:    array
length:  6
content: Perl,Java,C,C++,Lua,APL
---------------------------------
longNames
type:    array
length:  5
content: Python,JavaScript,Clojure,Forth,BASIC

6. Rozhodování na základě stavu kolekcí zjištěných funkcemi someevery

V případě, že potřebujeme zjistit, zda všechny prvky kolekcí splňují nějakou podmínku (zapsanou samozřejmě opět s využitím libovolné uživatelské či systémové funkce vracející pravdivostní hodnotu), můžeme použít funkci vyššího řádu nazvanou every. Tato funkce postupně prochází jednotlivé prvky kolekce či pole a pro každý prvek zavolá zadanou funkci, stejně jako tomu bylo u již popsaných funkcí filter a reject. Jakmile se nalezne prvek, pro něhož funkce vrací False, vrátí every taktéž False (a to ihned po prvním takovém prvku, neprochází se zbytek kolekce, neboť už je to zbytečné). Pokud se projdou všechny prvky, vrátí se hodnota True. Jestliže tedy chcete zjistit, zda jsou všechny prvky pole sudé, stačí použít:

// test zda pole obsahuje jen suda cisla
_.every(anArray, isEven);

Někdy potřebujeme zjistit, zda alespoň jeden prvek splňuje nějakou podmínku (tedy nikoli všechny prvky). Knihovna Underscore samozřejmě myslí i na tento případ a nabízí programátorům funkci nazvanou some. Způsob volání je shodný s funkcí every, ovšem chování se odlišuje – pokud uživatelem specifikovaná funkce (predikát) vrátí pro nějaký prvek pravdivostní hodnotu True, je hledání ihned ukončeno a taktéž se vrátí True. Jestliže se žádný vhodný prvek nenalezne, nezbude této funkci nic jiného, než vrátit False. Test na existenci alespoň jednoho sudého čísla v poli vypadá takto:

// test zda pole obsahuje alespon jedno sude cislo
_.some(anArray, isEven);

7. Třetí demonstrační příklad – použití funkcí someevery

Chování funkcí every a some je poměrně snadno pochopitelné, proto se již bez dalšího podrobnějšího vysvětlování podívejme na zdrojový kód dnešního třetího demonstračního příkladu, kde jsou tyto dvě funkce vyššího řádu použity pro zjištění informací o třech polích. Samotná pole jsou taktéž vytvořena funkcemi vyššího řádu knihovny Underscore, alespoň je patrné, jak se jednotlivé části této knihovny mohou vzájemně doplňovat:

// ------------------------------------------------------------
// Knihovna Underscore.js: demonstracni priklad cislo 8
//                         Pouziti funkci some() a every()
//                         pri praci s poli ci s kolekcemi.
// ------------------------------------------------------------
 
 
 
// funkce pro vypis informaci o vybranem poli (ci o jinem objektu)
function printArrayInfo(expression) {
    var anArray = eval(expression);
    console.log("---------------------------------");
    console.log(expression);
 
    // zjisteni typu objektu (a pripadne delky pole)
    if (anArray instanceof Array) {
        console.log("type:    array");
        console.log("length:  " + anArray.length);
    }
    // jiny typ objektu, nemame zde jistotu, ze existuje atribut length
    else {
        console.log("type:    " + typeof anArray);
    }
    console.log("content: " + anArray);
}
 
 
 
// bezna neanonymni (pojmenovana) funkce pouzita ve filter() a reject()
function isEven(value)
{
    return value % 2 == 0;
}
 
 
 
// pole s prvky 1..10
var array1 = _.range(1, 11);
 
// vytvorime nove pole jen se sudymi cisly
var array2 = _.filter(array1, isEven);
 
// vytvorime nove pole jen s lichymi cisly
var array3 = _.reject(array1, isEven);
 
// vypis informaci o vsech trech polich
printArrayInfo("array1");
printArrayInfo("array2");
printArrayInfo("array3");
 
 
 
// test zda pole obsahuje jen suda cisla
function containsOnlyEvenValues(anArray)
{
    return _.every(anArray, isEven);
}
 
// test zda pole obsahuje alespon jedno sude cislo
function containsEvenValue(anArray)
{
    return _.some(anArray, isEven);
}
 
console.log("---------------------------------");
 
console.log("array1 contains only even values: " + containsOnlyEvenValues(array1));
console.log("array2 contains only even values: " + containsOnlyEvenValues(array2));
console.log("array3 contains only even values: " + containsOnlyEvenValues(array3));
 
console.log("---------------------------------");
 
console.log("array1 contains at least one even value: " + containsEvenValue(array1));
console.log("array2 contains at least one even value: " + containsEvenValue(array2));
console.log("array3 contains at least one even value: " + containsEvenValue(array3));
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Výstup generovaný příkladem na konzoli:

---------------------------------
array1
type:    array
length:  10
content: 1,2,3,4,5,6,7,8,9,10
---------------------------------
array2
type:    array
length:  5
content: 2,4,6,8,10
---------------------------------
array3
type:    array
length:  5
content: 1,3,5,7,9
---------------------------------
array1 contains only even values: false
array2 contains only even values: true
array3 contains only even values: false
---------------------------------
array1 contains at least one even value: true
array2 contains at least one even value: true
array3 contains at least one even value: false

8. Kombinace chování filter a reject: funkce partition

V předchozím demonstračním příkladu jste si možná všimli této dvojice řádků:

// vytvorime nove pole jen se sudymi cisly
var array2 = _.filter(array1, isEven);
 
// vytvorime nove pole jen s lichymi cisly
var array3 = _.reject(array1, isEven);

V těchto programových řádcích se původní pole (či kolekce) rozděluje na dvě obecně nestejně velké části na základě predikátu isEven volaného pro každý prvek původního pole. Tento způsob rozdělování je pro některé algoritmy typický (rozdělení žáků na propadlíky a ty ostatní apod.), a proto se v knihovně Underscore můžeme setkat s další užitečnou funkcí nazvanou příznačně partition, která původní pole/kolekci rozdělí podle predikátu. Návratovou hodnotou je pole obsahující pouze dva prvky: první část původní kolekce a druhou část (typicky se jedná o 2D pole). Podívejme se na jednoduchý příklad, z něhož bude chování této funkce zřejmé:

// pole s prvky 1..10
var array1 = _.range(1, 11);
// rozdelime pole na zaklade podminky
var partitioned = _.partition(array1, isEven);
// vytvorime nove pole jen se sudymi cisly
var array2 = partitioned[0];
// vytvorime nove pole jen s lichymi cisly
var array3 = partitioned[1];

9. Čtvrtý demonstrační příklad – použití funkce partition

V dnešním čtvrtém demonstračním příkladu se výše popsaná funkce partition použije nejprve k rozdělení pole s prvky 1..10 na ty prvky, které jsou sudé, a dále na prvky, které jsou naopak liché (původní pole se ovšem nijak nezmění; navíc jsem pro jistotu nepřidal problematickou nulu :-). Zajímavější je druhá část příkladu, v níž se rozdělí pole obsahující názvy některých programovacích jazyků na jazyky s krátkými názvy (méně než pět znaků) a samozřejmě na zbytek, tj. na jazyky, jejichž názvy jsou dlouhé pět či více znaků. Podívejme se na úplný zdrojový kód tohoto příkladu, který ve skutečnosti není příliš komplikovaný:

// ------------------------------------------------------------
// Knihovna Underscore.js: demonstracni priklad cislo 9
//                         Pouziti funkce partition()
//                         pri praci s poli ci s kolekcemi.
// ------------------------------------------------------------
 
 
 
// funkce pro vypis informaci o vybranem poli (ci o jinem objektu)
function printArrayInfo(expression) {
    var anArray = eval(expression);
    console.log("---------------------------------");
    console.log(expression);
 
    // zjisteni typu objektu (a pripadne delky pole)
    if (anArray instanceof Array) {
        console.log("type:    array");
        console.log("length:  " + anArray.length);
    }
    // jiny typ objektu, nemame zde jistotu, ze existuje atribut length
    else {
        console.log("type:    " + typeof anArray);
    }
    console.log("content: " + anArray);
}
 
 
 
// bezna neanonymni (pojmenovana) funkce pouzita ve filter() a reject()
function isEven(value)
{
    return value % 2 == 0;
}
 
 
 
// pole s prvky 1..10
var array1 = _.range(1, 11);
 
// rozdelime pole na zaklade podminky
var partitioned = _.partition(array1, isEven);
 
// vytvorime nove pole jen se sudymi cisly
var array2 = partitioned[0];
 
// vytvorime nove pole jen s lichymi cisly
var array3 = partitioned[1];
 
// vypis informaci o vsech trech polich
printArrayInfo("array1");
printArrayInfo("array2");
printArrayInfo("array3");
 
 
 
// priklad s rozdelenim pole retezcu
var names = ["Perl", "Python", "Java", "JavaScript", "C", "C++", "Lua", "Clojure", "Forth", "APL", "BASIC"];
 
// rozdeleni pole retezcu podle toho, jak jsou jednotlive retezce dlouhe
var longAndShortNames = _.partition(names, function(str) {return str.length <= 4;});
 
// pro lepsi citelnost vytvorime samostatne pole kratkych
// a samostatne pole dlouhych retezcu
var shortNames = longAndShortNames[0];
var longNames = longAndShortNames[1];
 
// vypis informaci o vsech trech polich s retezci
printArrayInfo("names");
printArrayInfo("shortNames");
printArrayInfo("longNames");
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Výstup generovaný příkladem na konzoli:

---------------------------------
array1
type:    array
length:  10
content: 1,2,3,4,5,6,7,8,9,10
---------------------------------
array2
type:    array
length:  5
content: 2,4,6,8,10
---------------------------------
array3
type:    array
length:  5
content: 1,3,5,7,9
---------------------------------
names
type:    array
length:  11
content: Perl,Python,Java,JavaScript,C,C++,Lua,Clojure,Forth,APL,BASIC
---------------------------------
shortNames
type:    array
length:  6
content: Perl,Java,C,C++,Lua,APL
---------------------------------
longNames
type:    array
length:  5
content: Python,JavaScript,Clojure,Forth,BASIC

10. Funkce reduce a reduceRight

Posledními dvěma funkcemi vyššího řádu, které nesmějí chybět v repertoáru žádné funkcionálně zaměřené knihovny, je dvojice funkcí pojmenovaná reduce a reduceRight (někdy se setkáme s názvy foldl a foldr atd.). Názvy těchto funkcí naznačují jejich účel – dochází k postupné redukci prvků uložených v kolekci či v poli, a to (postupnou) aplikací zvolené uživatelské funkce na jednotlivé prvky a po krocích počítaný mezivýsledek. Mezi reduce a reduceRight je rozdíl v tom, ze které strany původní kolekce dochází ke kýžené redukci. Podívejme se na typický „školní“ příklad, v němž se sečtou všechny prvky v aritmetické řadě 1..10. Nejprve vytvořme tuto řadu:

// pole s prvky 1..10
var array1 = _.range(1, 11);

Následně vytvořme uživatelskou funkci, která se bude volat pro každý prvek původní kolekce a pro mezivýsledek. Jedná se o značně jednoduchou funkci, které pouze obě předané hodnoty sečte:

// bezna neanonymni (pojmenovana) funkce pouzita v reduce
// i v reduceRight
function add(x,y)
{
    return x+y;
}

Nyní zajistíme postupné volání funkce add na prvky pole s automatickým předáním mezivýsledku. Podle předpokladů bude výsledek funkce reduce v tomto případě totožný s výsledkem vráceným funkcí reduceRight, protože je zcela jedno, v jakém pořadí se prvky sečtou:

// vypocet sumy prvku
var sum1 = _.reduce(array1, add);
55
var sum2 = _.reduceRight(array1, add);
55

Ne všechny operace jsou ovšem asociativní a komutativní, jako je tomu u součtu čísel. Zkusme si vyzkoušet, co se stane ve chvíli, kdy namísto sčítání čísel budeme spojovat řetězce:

// rozdil mezi reduce a reduceRight
var names = ["Perl", "Python", "Java", "JavaScript", "C", "C++", "Lua", "Clojure", "Forth", "APL", "BASIC"];
 
// bezna neanonymni (pojmenovana) funkce pouzita v reduce
// i v reduceRight
function concat(string1,string2)
{
    return string1 + ", " + string2
}

Výsledky mezi reduce a reduceRight budou rozdílné, protože se výsledný řetězec bude skládat opačným způsobem (z výsledků je zřejmé, jak):

 
console.log("reduce: " + _.reduce(names, concat));
reduce: Perl, Python, Java, JavaScript, C, C++, Lua, Clojure, Forth, APL, BASIC
 
console.log("reduceRight: " + _.reduceRight(names, concat));
reduceRight: BASIC, APL, Forth, Clojure, Lua, C++, C, JavaScript, Java, Python, Perl

11. Pátý demonstrační příklad – použití funkcí reduce a reduceRight

Funkce reduce a reduceRight jsou pravděpodobně pochopitelné poněkud hůře, než předchozí funkce vyššího řádu, ovšem i jejich užitečnost může být vysoká. Podívejme se nyní, jak se úryvky kódu, s nimiž jsme se seznámili v předchozí kapitole, použijí v demonstračním příkladu:

// ------------------------------------------------------------
// Knihovna Underscore.js: demonstracni priklad cislo 10
//                         Pouziti funkci reduce a reduceRight
// ------------------------------------------------------------
 
 
 
// pole s prvky 1..10
var array1 = _.range(1, 11);
 
 
// bezna neanonymni (pojmenovana) funkce pouzita v reduce
// i v reduceRight
function add(x,y)
{
    return x+y;
}
 
// vypocet sumy prvku
var sum1 = _.reduce(array1, add);
var sum2 = _.reduceRight(array1, add);
 
console.log("sum1 = " + sum1);
console.log("sum2 = " + sum2);
 
// alternativni zpusob s pouzitim anonymnich funkci
console.log("sum1 = " + _.reduce(array1, function(x,y) {return x+y;}));
console.log("sum2 = " + _.reduceRight(array1, function(x,y) {return x+y;}));
 
 
// rozdil mezi reduce a reduceRight
var names = ["Perl", "Python", "Java", "JavaScript", "C", "C++", "Lua", "Clojure", "Forth", "APL", "BASIC"];
 
 
// bezna neanonymni (pojmenovana) funkce pouzita v reduce
// i v reduceRight
function concat(string1,string2)
{
    return string1 + ", " + string2
}
 
console.log("reduce: " + _.reduce(names, concat));
console.log("reduceRight: " + _.reduceRight(names, concat));
 
// alternativni zpusob s pouzitim anonymnich funkci
console.log("reduce: " + _.reduce(names, function(x,y) {return x+", "+y;}));
console.log("reduceRight: " + _.reduceRight(names, function(x,y) {return x+", "+y;}));
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Výstup generovaný příkladem na konzoli je zobrazen níže:

sum1 = 55
sum2 = 55
sum1 = 55
sum2 = 55
reduce: Perl, Python, Java, JavaScript, C, C++, Lua, Clojure, Forth, APL, BASIC
reduceRight: BASIC, APL, Forth, Clojure, Lua, C++, C, JavaScript, Java, Python, Perl
reduce: Perl, Python, Java, JavaScript, C, C++, Lua, Clojure, Forth, APL, BASIC
reduceRight: BASIC, APL, Forth, Clojure, Lua, C++, C, JavaScript, Java, Python, Perl

Povšimněte si především toho, že funkce reduce a reduceRight mají odlišný výsledek ve chvíli, kdy jsou operace prováděné volanými funkcemi nekomutativní a neasociativní:

12. Výpočet faktoriálu s použitím funkce reduce

Funkci reduce či reduceRight (zde je to opět jedno) můžeme použít pro výpočet faktoriálu, protože si stačí uvědomit, že výpočet faktoriálu je prakticky totožný s algoritmem pro součet aritmetické řady (ten již velmi dobře známe). Liší se jen použitá operace – namísto součtu se provede součin. „Funkcionálně“ zapsaný výpočet faktoriálu může vypadat i tak, že se na sekvenci hodnot vygenerovanou s využitím range aplikuje reduce:

_.reduce(_.range(1,n+1), function(x,y) {return x*y;});

Poznámka: nejedná se o optimální způsob z hlediska spotřeby paměti ani rychlosti, a to kvůli nutnosti generovat prvky zdrojového pole, které se ihned po výpočtu opět zahodí.

Pokud budeme chtít vytvořit tabulku faktoriálu pro zvolená n, můžeme samozřejmě použít programovou smyčku typu for. Ovšem zápis této smyčky je už od dob jazyka C mnohdy zbytečně komplikovaný. Namísto toho je možné použít funkci each, která pro každý prvek vstupní sekvence volá zapsanou funkci. Povšimněte si zde malého ale významného rozdílu oproti map, kde se vracela nová sekvence. To funkce each nedělá a předpokládá, že volaná funkce bude mít nějaký vedlejší efekt:

_.each(_.range(1,11), ...);

Výpočet tabulky faktoriálu pro n=1..10 tedy zapíšeme například takto:

_.each(_.range(1,11), function(n) {console.log(n + "! = " + factorial(n));});

13. Šestý demonstrační příklad – funkce each a reduce při výpočtu faktoriálu

Podívejme se nyní na použití funkce pro výpočet faktoriálu s využitím reduce a range v praxi. V dnešním posledním demonstračním příkladu, jehož zdrojový kód lze nalézt na https://github.com/tisnik/pre­sentations/blob/master/un­derscore/underscore11.js je tato funkce definována a následně použita pro výpočet faktoriálů pro n=1 až n=10. Povšimněte si, že se v tomto příkladu opět nikde neobjevují explicitně zapsané programové smyčky:

// ------------------------------------------------------------
// Knihovna Underscore.js: demonstracni priklad cislo 11
//                         Pouziti funkce each spolecne s funkci
//                         reduce.
// ------------------------------------------------------------
 
 
 
// alternativni zpusob vypoctu faktorialu
function factorial(n)
{
    // vytvori se posloupnost 1..n
    // postupne se jednotlive prvky poslouposti nasobi
    // a vrati se vysledek
    return _.reduce(_.range(1,n+1), function(x,y) {return x*y;});
}
 
// tisk nekolika faktorialu pro vstupni hodnoty 1..10
// (vime jiz, ze funkce range nezahrnuje mezni hodnotu)
 
// funkce each pracuje jako smycka foreach
// (neni to tedy cista funkce, protoze ma a musi mit vedlejsi efekt)
_.each(_.range(1,11), function(n) {console.log(n + "! = " + factorial(n));});
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Výstup generovaný tímto posledním příkladem na konzoli webového prohlížeče ukazuje, že se faktoriály skutečně počítají korektně (minimálně pro celá kladná čísla až do limitu zmíněného níže):

root_podpora

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

Poznámka: podle specifikace by měly všechny implementace JavaScriptu pro numerické hodnoty používat typ double (čísla s plovoucí řádovou čárkou mající dvojitou přesnost) definovaný v IEEE 754. Z tohoto limitu lze odvodit i maximální hodnotu n, pro kterou se faktoriál vypočítá korektně. Hranice leží mezi n=170 a n=171:

170! = 7.257415615307994e+306
171! = Infinity

14. Repositář s demonstračními příklady

Všech šest demonstračních příkladů, které jsme si v dnešním článku popsali, bylo uloženo 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 všech šesti demonstračních příkladů přímé odkazy (navíc je doplněn i odkaz na aktuálně použitou variantu knihovny Underscore):

15. Odkazy na Internetu

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

Byl pro vás článek přínosný?

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.