Stavíme Origami
Origami je Japonské umění, které spočívá v překládání a ohýbání papíru, které vyústí ve všemožné tvary. To si může zkusit každý. Stačí jen kousky papíru správné velikosti a návod, jak pro aktuálně poskládaný papír pokračovat dále. Pak již každý zvládne poskládat z papíru třeba čepici, loďku, ptáčka nebo také dvanáctistěn, jenž můžete každý najít v posluchárně S3 na Malé Straně.
Jistě se ptáte, proč se zmiňujeme o Origami, když je očividně řeč o programování v Haskellu. Představte si nyní, že náš papír reprezentují seznamy. Dobře, ale jak vypadá skládání seznamů?
Mějme v ruce nějaký aktuální stav. Pak jedno složení v seznamu vypadá tak, že vezmeme prvek v seznamu, ten podle návodu zkombinujeme s aktuálním stavem, čímž dostaneme jiný stav a přesuneme se na další prvek. Návod reprezentujeme libovolnou funkci odpovídajícího typu. Jakmile nám dojdou prvky, máme hotové mistrovské dílo, v našem případě konečný stav.
Všimněme si, že většina rekurzivních funkcí, které pracují se seznamem, dělá právě nějaký druh skládání seznamu. Na prázdném seznamu se zastaví a jako výsledek vrátí nějakou transformaci hlavy a rekurzivního výsledku na zbytek seznamu.
Existují dva způsoby jak postupovat. Můžeme se buď nejprve zarekurzit až
ke konci seznamu, kde začneme zpracovávat počáteční stav, který postupně při
návratu z rekurze upravujeme. Též naopak můžeme začít zpracovávání již od
prvního prvku a stav budeme udržovat v akumulátoru. První způsob zachytíme
funkcí foldr, ten druhý pomocí foldl.
foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ start [] = start foldr f start (x:xs) = f x $ foldr f start xs foldl :: (b -> a -> b) -> b -> [a] -> b foldl _ acc [] = acc foldl f acc (x:xs) = foldl f (f acc x) xs
Nyní tyto funkce použijeme k tomu, abychom sečetli všechny prvky v seznamu. Počáteční stav bude nula a návodová funkce bude prostě sčítání.
> foldr (+) 0 [1..5] 15 > foldl (+) 0 [1..5] 15
Který fold použít?
Obě varianty foldu nám vrátily v případě sčítání stejný výsledek. Kdy je však která varianta ta správná? Podívejme se nejprve, na jaký výraz se foldy převedou:
> foldl (∘) v [a, b, c, d, e] (((((v ∘ a) ∘ b) ∘ c) ∘ d) ∘ e) > foldr (∘) v [a, b, c, d, e] (a ∘ (b ∘ (c ∘ (d ∘ (e ∘ v)))))
Oba výrazy tedy mají vzhledem k operaci stejné pořadí prvků seznamu. Podstatně
se změnilo uzávorkování. Zatímco foldl asociuje aplikace zleva, foldr
to dělá zprava. Proto se též liší signatury návodových funkcí.
Co to znamená pro naši rekurzi? Nejprve předpokládejme, že nemáme líné vyhodnocování, tudíž se vyhodnocení provede od nejhlubší závorky. Uvažme příklad se sčítáním:
> foldl (+) 0 [1..5] → ((((0 + 1) + 2) + 3) + 4) + 5 → ((( 1 + 2) + 3) + 4) + 5 → (( 3 + 3) + 4) + 5 → ( 6 + 4) + 5 → 10 + 5 → 15 > foldr (+) 0 [1..5] → 1 + (2 + (3 + (4 + (5 + 0)))) → 1 + (2 + (3 + (4 + 5 ))) → 1 + (2 + (3 + 9 )) → 1 + (2 + 12 ) → 1 + 14 → 15
Pro foldl, abychom mohli začít redukovat, nám stačí první prvek seznamu,
vyhodnocení odpovídá používání akumulátoru a dostáváme příjemně efektivní
koncovou rekurzi. Naopak foldr musí nejprve dojít ke konci seznamu, a pak jej
redukovat "pozpátku", použití zásobníku se v tomto případě nevyhneme a
vyhodnocení bude potřebovat lineární prostor.
Z tohoto důvodu se foldl často říká levý fold a foldr pravý fold.
Nyní se však do hry dostane líné vyhodnocování. Podívejme se nejprve, jak se
změní vyhodnocení levého foldu. Zde se najednou stane to, že protože hodnotu
budeme chtít potenciálně až "později", Haskell si zapamatuje celý uzávorkovaný
výraz. Potom si jiná část programu řekne o výsledek, což bude vnější závorka.
Ta ale obsahuje striktní (+), tudíž její vyhodnocení vynutí vyhodnocení
vnitřní závorky. Takto pokračujeme, dokud se nedostaneme do nejhlubší závorky,
kterou můžeme vyhodnotit a pak se vrátit zpět.
Ve výsledku dostaneme stejný výraz, ale najednou místo konstantní paměti najednou budeme potřebovat lineární. To není hezké. O co víc, pokud seznam samotný je líný a vytváří se postupně v konstantním čase, zhoršili jsme si paměťovou složitost extrémně.
Z tohoto důvodu nám Haskell poskytuje striktní variantu levého foldu,
nalezitelnou jako funkci foldl'. Ta opravdu dělá to, že průběžně udržuje
akumulátor a běží v konstantním prostoru.
Dobře, a co foldr? Zde nám líné vyhodnocování naopak pomůže! Zapišme si
explicitněji průběh rekurze našeho sčítacího příkladu.
> foldr (+) 0 [1, 2, 3, 4, 5] → 1 + (foldr (+) 0 [2, 3, 4, 5])
To je pořádný rozdíl. Dokud nepotřebujeme výsledek, udělali jsme jen jeden krok a zatím jsme vůbec nevyhodnotili zbytek seznamu. To je velmi dobrá zpráva, protože to může vést k pouze částečnému vyhodnocení seznamu. Samozřejmě, v případě sčítání se při dotaz na výsledek stejně projde celý seznam, ale zkusme nyní něco jiného.
> let f x xs = (2*x) : xs in take 2 $ foldr f [] [1..] → take 2 $ (1 * 2) : (foldr f [] [2..]) → take 2 $ (1 * 2) : (2 * 2) : (foldr f [] [3..]) → (1 * 2) : (2 * 2) : [] → [2,4]
Konstrukce let a = b in c je ekvivalentní c where a = b. Narozdíl od
where, což je speciální syntaxe při definici funkce, je let .. in výraz a
lze jej použít kdekoliv.
Vidíme, že pravý fold umí pracovat i s nekonečnými seznamy a v případech, kdy je vše líné, se opravdu vyhodnotí jen ta část, která nás zajímá.
Co si z tohoto odnést? Pokud opravdu musíme projít celý seznam a chceme levý
fold, vždy je lepší místo toho uvážit jeho striktní variantu foldl'. Naopak,
pokud chceme mít funkci, která umí pracovat s nekonečnými seznamy, chceme
použít pravý fold.
Cvičení: Pomocí foldu naprogramujte funkci product :: [Integer] ->
Integer vracející součin všech čísel seznamu. Který fold použijete?
Cvičení: Naprogramujte funkci length :: [a] -> Integer vracející délku
seznamu.
Cvičení: Naprogramujte funkci sumSq :: [Integer] -> Integer, která vrací
součet druhých mocnin prvků seznamu.
Cvičení: Naprogramujte funkce and a or typů [Bool] -> Bool,
které vyhodnocují n-ární logický and nebo or. Jak se budou chovat na
nekonečném seznamu?
Podívejme se blíže na univerzalitu foldů.
Dříve jsme si naprogramovali funkci map. Když pohlédneme na její
definici, celkem přímočaře v rekurzi vidíme pravý fold. Návodová funkce
odpovídá aplikaci f na hlavu, kterou připojí ke zbytku seznamu. Zbytek
seznamu pak tvoří stav.
map f = foldr (\x xs -> (f x) : xs) [] > map (*2) [1,2,4] → foldr (\x xs -> (x*2) : xs) [] [1,2,4] → (1*2) : foldr (...) [] [2,4] → (1*2) : (2*2) : foldr (...) [] [4] → (1*2) : (2*2) : (4*2) : foldr (...) [] [] → (1*2) : (2*2) : (4*2) : [] → [2,4,8]
To bylo celkem jednoduché. Co třeba taková funkce takeWhile? Návodová funkce
zde vždy zkontroluje predikát. Pokud platí, vrátí prvek a zbylý stav, jinak
vrátí prázdný seznam. Podobným způsobem můžeme napsat i filter, kde ale dle
návodu vrátíme zbytek vždy.
takeWhile f = foldr (check f) [] where check f x xs = if (f x) then x : xs else [] filter f = foldr (check f) [] where check f x xs = if (f x) then x : xs else xs
Konstrukce if p then t else f je výraz, který zkontroluje pred a vrátí
příslušnou větev. Jedná se tedy o ekvivalent stráží, který lze ale použít
kdekoliv. Narozdíl od běžného procedurálního if je else větev povinná, něco
vrátit musíme.
Cvičení: Naprogramujte funkci reverse :: [a] -> [a], která obrací konečný
seznam.
Cvičení: Naprogramujte funkci deleteAll :: Eq a => a -> [a] -> [a], která
odsraní všechny výskyty daného prvku ze seznamu.
Cvičení: Naprogramujte funkci replace :: Eq a => a -> a -> [a] -> [a],
beroucí dvojici x, y a nahrazující všechny výskyty x v seznamu za y.
V typové signatuře Eq a značí, že typ a lze porovnávat rovností. Obdobně,
Ord a popisuje porovnatelné prvky pomocí < a =.
Dobře, tato řešení byla vcelku krotká, rekurze je celkem přímočará a vždy se
zastavuje až na konci seznamu. Zkusme nyní něco složitějšího. Vezměme si funkci
take, která vrací prvních k prvků. Jak ji napsat?
Trochu pomůžeme našemu foldu zvenku. Nejprve si k prvkům přidáme jejich pořadí a pak provedeme fold na této dvojici, který postupně z dvojice zanechá pouze původní prvek. Jakmile se dopočítáme k pořadí, které má být poslední, skončíme vracením prázdného seznamu.
-- očíslovat prvky od 0 enumerate :: [a] -> [(Integer, a)] enumerate = zip [0..] take :: Integer -> [a] -> [a] take n list = foldr step [] (enumerate list) where step (pos, x) xs | pos == n = [] | otherwise = x : xs
Stavy nechť jsou funkce
Kromě pravého foldu jsme zde též využili funkci zip. To se skoro zdá, že jsme
prohráli. Nezoufejme, i zip umíme napsat foldem. Nejprve se podívejme na tuto
magickou definici.
zip xs ys = foldr guide start xs ys where start ys = [] guide x f [] = [] guide x f (y:ys) = (x, y) : (f ys)
Jak funguje? Počátek je typu [b] -> [c], tudíž návodová funkce je typu [a]
-> ([b] -> [c]) -> [b] -> [c]. Z toho vyplývá, že celý foldr start guide xs
vrací typ [b] -> [c]. No a protože vracíme dvojici, tak c = (a, b).
Tudíž, jak postupně procházíme seznam xs, vytváříme mnohanásobně složenou
funkci, kterou pak aplikujeme na správnou část ys.
> zip [1,2,3] → \(y:ys) -> (1,y) : ((foldr (...) [2,3]) ys) → \(y:ys) -> (1,y) : \(y:ys) -> (2,y) : ((foldr (...) [3]) ys) → \(y:ys) -> (1,y) : \(y:ys) -> (2,y) : \(y:ys) -> (3,y) : ((foldr (...) []) ys) → \(y:ys) -> (1,y) : \(y:ys) -> (2,y) : \(y:ys) -> (3,y) : ((\y -> []) ys) > zip [1,2,3] [3,2,1,0] → \(y:ys) -> (1,y) : \(y:ys) -> (2,y) : \(y:ys) -> (3,y) : ((\y -> []) ys) [3,2,1,0] → (1,3) : \(y:ys) -> (2,y) : \(y:ys) -> (3,y) : ((\y -> []) ys) [2,1,0] → (1,3) : (2,2) : \(y:ys) -> (3,y) : ((\y -> []) ys) [1,0] → (1,3) : (2,2) : (3,1) : ((\y -> []) ys) [0] → (1,3) : (2,2) : (3,1) : []
Cvičení: Naprogramujte zipWith pomocí pravého foldu.
Stejnou myšlenkou můžeme rovnou naprogramovat take přímo, bez použití zipu.
Stav budeme reprezentovat funkcí, která bude brát číslo a vrátí seznam. Konec
seznamu nahradíme funkcí, která vždy vrací prázdný seznam. Pak v každém kroku
tuto funkci správně složíme.
take :: Integer -> [a] -> [a] take n xs = foldr guide start xs n where start ys = [] guide x f 0 = [] guide x f n = x : f (n-1)
Struktura návodové funkce se nápadně podobá funkci v zipu, jen jsme rovnou za y dosadili správné číslo.
Když se podíváme na naše foldy blíže, tak jsme sice z čisté rekurze došli k pravému foldu, ale trochu jsme podváděli. Rekurzi jsme si totiž schovali do naší návodové, avšak tentokrát již nerekurzivní, funkce. Fold pak rozepíše explicitně tolik kroků původní rekurze, kolik je potřeba. Tohle je mimochodem dosti podobné způsobu, jak v lambda kalkulu tvořit rekurzivní funkce.
Cvičení: Naprogramujte funkci delete :: Eq a => a -> [a] -> [a], která
odstraní první výskyt prvku x ze seznamu, pokud v něm je.
Cvičení: Naprogramujte funkci replaceFirst :: Eq a => a -> a -> [a] ->
[a], která nahradí první výskyt prvku x na y, pokud x v seznamu je.
Nakonec ukážeme, že foldr je až tak univerzální, že lze pomocí něj napsat
foldl. Znovu použijeme trik s tím, že stav bude funkce. Stejným způsobem
můžeme pomocí pravého foldu nadefinovat i jeho striktní variantu. Použijeme
totiž operátor $! definovaný jako striktní aplikace na správném místě.
foldl f a list = foldr (\b g x -> g (f x b)) id list a foldl' f a list = foldr (\b g x -> g $! (f x b)) id list a
Varianty foldů
Ne vždy má nějaká funkce význam pro prázdný seznam nebo není snadné nadefinovat počáteční prvek. Proto si přidáme upravené verze foldů, které jako počáteční prvek použijí první prvek seznamu.
foldr1 :: (a -> a -> a) -> [a] -> a foldr1 f [] = error "foldr1 on empty list" foldr1 f (x:xs) = foldr f x xs foldl1' :: (a -> a -> a) -> [a] -> a foldl1' f [] = error "foldl1' on empty list" foldl1' f (x:xs) = foldl' f x xs
Na rozdíl od běžného foldu nyní je stav vždy stejného typu, jako prvky seznamu, takže tyto foldy jsou slabší.
Cvičení: Naprogramujte minimum a maximum typů Ord a => [a] -> a,
které pro neprázdné seznamy porovnatelných prvků vrací jejich minimum nebo
maximum. Můžete použít funkce min a max typů Ord a => a -> a -> a.
Cvičení: Dává smysl naprogramovat součet nebo součin pomocí jedničkové varianty foldu? Proč ano a proč ne?
Cvičení: Naprogramujte funkci scalarProduct, která spočítá skalární
součin dvou vektorů.
Cvičení: Naprogramujte funkci sorted :: Ord a => [a] -> Bool, která
kontroluje, že seznam odpovídá seřazené posloupnosti.
Dále se někdy může hodit si zapamatovat všechny mezivýsledky, které při
skládání dostaneme. Takové funkce najdeme pod názvem scan. Obdobně, podle
typu foldu máme typ scanu.
scanr :: (a -> b -> b) -> b -> [a] -> [b] scanr _ start [] = [start] scanr f start (x:xs) = f x q : qs where (qs@(q:_)) = scanr f start xs scanr1 :: (a -> a -> a) -> [a] -> [a] scanr1 _ [] = [] scanr1 _ [x] = [x] scanr1 f (x:xs) = f x q : qs where (qs@(q:_)) = scanr1 f xs scanl :: (b -> a -> b) -> b -> [a] -> [b] scanl' :: (b -> a -> b) -> b -> [a] -> [b] scanl1 :: (a -> a -> a) -> [a] -> [a] scanl1' :: (a -> a -> a) -> [a] -> [a]
Operátor @ je užitečný operátor použitelný v Pattern Matchingu, který
způsobí, že levou stranu rozbalí do pravé strany. Tudíž p@(a,b) odpovídá
dvojici p, která se skládá z prvků a a b.
Cvičení: Naprogramujte funkci prefixSum, která vrací prefixové součty na
seznamu.
Cvičení: Pomocí scanu na [0,0..] naprogramujte funkci arithSeq ::
Integer -> [Integer], která pro k vrací aritmetickou posloupnost [0, k, 2k,
...].
Cvičení: Pomocí scanu na [1,1..] naprogramujte funkci geomSeq ::
Integer -> [Integer], která pro k vrací geometrickou posloupnost [1, k, k²,
...].
V Haskellu je podstatně lepší psát funkce jako skládání základních funkcí jako
map, filter, fold, než přímou rekurzí. Přímá rekurze je totiž srovnatelná
s asemblérem a používání goto, zatímco základní funkce představují vyšší
konstrukce jako if, while. Obvykle pak programátor udělá méně chyb a lépe
to udává pravý úmysl programátora, co vlastně chtěl udělat. Nesmíme to ale
přehnat, viz zip.
Podívejme se ještě, jak snadno můžeme díky línému vyhodnocování definovat Fibonacciho čísla.
fib :: [Integer] fib = 0 : 1 : zipWith (+) fib $ tail fib
Máme rekurzivní definici, která odkazuje sama na sebe. Ale díky línému
vyhodnocování budeme vždy znát dostatečně dlouhý prefix fib na to, aby
zipWith (+) uměl spočítat následující číslo.
Nakonec si dovolíme poznámku k efektivitě. Haskell umí na pravém foldu dělat optimalizace, kdy se vyhne vytváření meziseznamů, takže programování pomocí foldů dává smysl.