Když vidíte začátečníka pracovat s kolekcemi, často se setkáte s tím, že možností první volby je iterace pomocí cyklů a změna stavu. Díky tomu máme spoustu rozbitých aplikací. Ruku na srdce, kdo z vás nemá ve své codebase něco podobného:

var list = new List();
foreach (var item in someCollection) {
  // ... some work
  list.Add(item);
}
return list;

Nádhera! :)

Zapomeňte na cykly a mutace, kdo se v tom má vyznat a hledat chyby? Buďte deklarativní.

Disclaimer

Následující řádky používají techniku obvyklou ve funkcionálních jazycích – rekurzi. Je dost možné, že váš jazyk nemá podporu na úrovni kompilátoru pro rekurzi (tail recursion se optimalizuje tak, že se přepíše na cyklus) a může docházet k tomu, že vám bude přetékat zásobník. V první řadě vždy musíte vědět, co děláte. Ale to platí obecně o všem v programování. C# optimalizovat rekurzi neumí, přesto můžete používat funkcionální koncepty, např. LINQ, který je implementovaný pomocí iterátorů. Následující ukázky budou v F#, který rekurzi optimalizovat umí.

Všechny ukázky si můžete vyzkoušet přímo ve vašem prohlížeči na webu Try F#. Jednotlivé ukázky stačí označit a stisknout Ctrl+Enter.

Článek vychází z Higher-order list operations.

Rekurze

Když zjistíte, že cykly ne, většinou přejdete na rekurzi. Častou chybou však je, že píšete příliš mnoho kódu. Proč? Protože vám třeba chybí znalosti o knihovnách nebo konstruktech jazyka, které nám umožní psát kódu méně. Pojďme si ukázat, jak psát kódu méně a jak některé knihovní funkce vlastně fungují.

Přičítání jedné

Máme za úkol napsat funkci, která projde seznam čísel a přičte ke každému prvku jedničku. V implementaci použijeme datovou strukturu spojový seznam (v C# spíše než LinkedList<T> použijeme ImmutableList<T> z NuGet balíčku Microsoft.Bcl.Immutable) a využijeme rekurze:

let rec add1 lst =
    if List.isEmpty lst then []
    else (List.head lst) + 1 :: add1 (List.tail lst)

add1 [1; 2; 3]

Že jde o rekurzivní funkci nám říká klíčové slovo rec. Funguje to tak, že vezmu první prvek seznamu a přičtu k němu jedničku, ten pak připojím k seznamu (operátor ::), který se spočítá obdobně ze zbytku vstupního seznamu. Pokud je seznam prázdný (nebo jsme došli na konec – každý spojový seznam končí prázdným polem), vrátíme prázdný seznam. Tím se nám rekurze ukončí.

Odčítání jedné

Obdobně naimplementujeme i odčítání:

let rec sub1 lst =
    if List.isEmpty lst then []
    else (List.head lst) - 1 :: sub1 (List.tail lst)

sub1 [1; 2; 3]

Ok, máme funkcionální datovou strukturu, máme rekurzi, je to už teda funkcionální kód?

Tak určitě ne.

Knihovní funkce

Další častou chybou je používání podmínek a ukecaného kódu vůbec. Navíc když se na obě funkce podíváme blíže, zjistíme, že to jsou v podstatě duplicity a jediné, co je odlišuje, je operace sčítání nebo odčítání. Když se oprostíme od implementačních detailů, zjistíme, že neděláme nic jiného než mapování. A tak jde kód přepsat do jednodušší podoby:

let inc x = x + 1
let dec x = x - 1

List.map inc [1; 2; 3]
List.map dec [1; 2; 3]

Nejprve jsme si definovali pomocné funkce pro inkrementaci a dekrementaci prvku a pak použili knihovní funkci List.map, která projde všechny prvky seznamu a na každý aplikuje předanou funkci (v C# je obdobou Enumerable.Select). Důležitým detailem, který nemusí být na první pohled zřejmý, je, že nedojde k úpravě předaného seznamu, ale k vytvoření seznamu nového.

High order function

Jak bychom takovou funkci map naimplementovali? Zkusíme to pomocí jednoduché generalizace našich funkcí add1 a sub1. Už jsme si říkali, že se liší jen v operaci přičtení/odečtení jedničky. Takže z našich funkcí vytvoříme funkci vyššího řádu:

let rec map f lst =
    if List.isEmpty lst then []
    else f(List.head lst)::map f (List.tail lst)

map inc [1 .. 3]

Funkce vyššího řádu se vyznačují tím, že jako parametr přijímají jinou funkci, která definuje, co se uvnitř bude dít (obdoba vzoru strategie z objektového světa). Funkce je takřka stejná jako naše konkrétní ukázky. Jediný rozdíl je, že nyní aplikujeme předanou funkci na první prvek seznamu a pak už je to stejný. Teď tedy máme funkci vyššího řádu, ale pořád je toho kódu zbytečně moc.

Pattern matching

Další skvělou vlastností mnoha funkcionálních jazyků je pattern matching – volba výsledku na základě strukturální podobnosti. Naši map funkci můžeme hezky zjednodušit na:

let rec mapMatch f lst =
    match lst with
    | [] -> []
    | head::tail -> f head::mapMatch f tail

mapMatch dec [1 .. 3]

Kód je de facto stejný jako v předchozím případě, jen nám zmizelo volání knihovních funkcí List.isEmpty, List.head a List.tail a místo nich máme vzory. Prázdný seznam se mapuje na prázdný seznam, seznam s nějakým prvkem se dle vzoru rozdělí na head a tail. Na head se aplikuje funkce a nový tail se vypočítá rekurzí.

List comprehension

Možná jste si všimli, že jsem v ukázkách najednou přestal psát [1; 2; 3;] pro vytvoření seznamu tří čísel, ale přešel k zápisu [1 .. 3]. Funkcionální jazyky mívají pro kolekce větší pochopení a tak nezvládají jen tupé vyjmenování prvků, ale rozumí i složitějším konstrukcím pro vytvoření seznamu (platí i pro pole a sekvence). Zde byl použit operátor rozsahu ... Ve skutečnosti můžeme jít mnohem dál a aplikovat třeba rovnou i mapování:

[for x in 1 .. 3 -> x + 1]

Výsledek je stejný jako v předchozích příkladech. Kód je minimální. Myšlenka zřejmá.

Filtrování kolekcí

Další možností, kde můžeme využít funkce vyššího řádu a pokusíme se zbavit podmínek, je filtrování kolekcí. Funkce filter vrací prvky ze vstupního pole, které splňují předaný predikát:

let even x = x % 2 = 0

let rec filter p lst =
    if List.isEmpty lst then []
    elif p (List.head lst) then List.head lst::filter p (List.tail lst)
    else filter p (List.tail lst)

filter even [1 .. 10]

Nejprve jsme si definovali predikát pro sudá čísla, který budeme používat i v dalších ukázkách, a pak funkci filter implementovanou pomocí podmínek a knihovních funkcí (F# má samozřejmě funkci List.filter již implementovanou, v C# ji hledejte pod názvem Enumerable.Where). Filtr je o něco složitější než mapování, protože se musíme rozhodnout, které prvky chceme a které ne. Ty prvky, které splňují predikát připojíme před zbytek počítaného seznamu. Pokud prvek predikát nesplňuje, pokračuje dál ve výpočtu seznamu. U prázdného seznamu ukončíme rekurzi.

S využitím pattern matchingu kód vypadá následovně:

let rec filterMatch p lst =
    match lst with
    | [] -> []
    | hd::tl when p hd -> hd::filterMatch p tl
    | hd::tl -> filterMatch p tl

filterMatch even [1 .. 10]

Pěkné, že? A ještě ukázka s list comprehension:

[for x in 1 .. 10 do if even x then yield x]

Všimněte si, že zde se nám šipka -> z ukázky pro mapování změnila na do ... yield. Schválně si to zkuste, že jde o stejný kód. Tady už bohužel kompaktní zápis nefunguje, protože tam potřebujeme vložit filtrovací podmínku.

Agregace kolekcí

Další častou operací, kterou se seznamy můžeme dělat, je jejich agregace. Ve funkcionálních jazycích se často můžeme potkat s funkcí fold (v C# Enumerable.Aggregate):

let rec foldr cons nil lst =
    match lst with
    | [] -> nil
    | hd::tl -> cons hd (foldr cons nil tl)

foldr (+) 0 [1 .. 4]

Parametr cons je konstrukční funkce výsledku, nil reprezentuje prázdný prvek.

A ještě tail recursive varianta pro efektivnější zpracování kompilátorem:

let rec foldl cons nil lst =
    match lst with
    | [] -> nil
    | hd::tl -> foldl cons (cons hd nil) tl

foldl (+) 0 [1 .. 4]

Zipování

Další velice důležitou funkcí je zip, která vezme dva seznamy a vytvoří z nich jeden tvořený dvojicemi, podobně jako zip u vaší bundy.

let rec zip lst1 lst2 =
    match lst1, lst2 with
    | [], [] -> []
    | hd1::tl1, hd2::tl2 -> (hd1, hd2)::zip tl1 tl2

zip [1 .. 3] ['a' .. 'c']

Žádný velký objev. :) Novinkou je matchování na více prvků a zavedení n-tic (tuples). Zip je velice šikovná funkce. Schválně jestli vás napadne nějaké rozumné užití. Nebojte se o něj podělit třeba v komentářích.

Také si všimněte, že tu mícháme jabka (int) s hruškama (char) a vše funguje. Není to tím, že by F# byl slabě typový, ale tím, že naše funkce jsou plně generické! Schválně si zkuste v předchozích ukázkách změnit vstupní data.

Rozepnutí

Opakem zipování je unzip, která nám ze seznamu dvojic udělá dva seznamy prvků. A protože nám tato funkce vrací dva seznamy, začíná to být trochu tricky:

let rec unzip lst =
    match lst with
    | [] -> ([], [])
    | (x, y)::tl ->
        let (xs, ys) = unzip tl
        (x::xs, y::ys)

unzip [(1, 'a'); (2, 'b'); (3, 'c')]

Taková nepěkná věc je, že si musíme začít pamatovat výsledek rekurzivního volání, se kterým dále pracujeme. Všimněte si také, že F# umí rozpadnout n-tici do samostatných chlívečků. Nebudu říkat proměnných, protože let vazba je neměnná.

Continuation

Co bychom to byly za funkcionáře, kdybychom nechali takové imperativní přiřazování v naší jinak čisté implementaci? Jak se jen zbavit přiřazení? Co třeba za pomocí continuation? Nic vám to neříká? Co třeba callback? Ten už jistě znáte. :)

let rec unzipk k lst =
    match lst with
    | [] -> k [] []
    | (x, y)::tl -> unzipk (fun xs ys -> k (x::xs) (y::ys)) tl

unzipk (fun xs ys -> xs) [(1, 'a'); (2, 'b'); (3, 'c')]

V této formě musí uživatel funkce přidat callback, ale na druhou stranu si může vybírat, co vlastně chce za výsledek. Funkcionální kompozice je mocná.

Partitioning

Partitioning je něco jako filtrování, jen nám opět vrací dva seznamy. Jeden s pozitivními výsledky a druhý s negativními:

let rec partition p lst =
    match lst with
    | [] -> ([], [])
    | hd::tl ->
        let (ins, outs) = partition p tl
        if p hd then (hd::ins, outs)
        else (ins, hd::outs)

partition even [1 .. 10]

Implementace je dost podobná unzipování, jen teď máme na vstupu pouze jeden prvek a rozhodujeme se, do kterého seznamu ho zařadíme. A opět můžeme implementaci udělat pomocí continuation:

let rec partitionk p k lst =
    match lst with
    | [] -> (k [] [])
    | hd::tl -> partitionk p (fun ins outs ->
                                if p hd then k (hd::ins) outs
                                else k ins (hd::outs)) tl

partitionk even (fun evens odds -> evens) [1 .. 10]

Závěr

Ukázali jsme si, jak si ušetřit spoustu práce pomocí funkcionálního přístupu ke kolekcím. Implementace jednotlivých funkcí je jen ukázkou, jak snadno se dají takové věci implementovat a rychlým průletem, co všechno F# umí. Sice jsme se jen sklouzli po povrchu, ale jako základ je to celkem slušný, ne? :)

Zkuste si pohrát se spustitelnými ukázkami. Zkuste mapování a filtrování implementovat pomocí continuation. Zkuste si třeba filter implementovat pomocí partition. Většina kombinátorů lze totiž implementovat pomocí pouhých tří základních, ale k tomu zase třeba jindy.