Haskell - seznamy a skládání funkcí

Jako dobrý zdroj jednoduchých (a čím dál složitějších) problémů pro zkoušení si Haskellu nám může posloužit Project Euler. Např. problém č. 6 po nás chce, abychom spočítali rozdíl mezi součtem čtverců a čtvercem součtů prvních 100 přirozených čísel. Udělejme to obecně pro prvních n.

problem6 :: Int -> Int
problem6 n = (sum [1..n]) ^ 2 - (sum (map (^2) [1..n]))

Definujme si teď seznam všech prvočísel (protože v Haskellu prostě můžeme :)). Nejdříve se nám hodí funkce, která rozhoduje, jestli dané číslo je prvočíslo. Implementace tady není moc efektivní, prostě zkouší všechna čísla menší než odmocnina z testovaného a zjišťuje, jestli je jimi dané číslo dělitelné. Čeho si ale můžete všimnout je, že když budete testovat nějaké hodně velké sudé číslo algoritmus skončí skoro hned. Stačí totiž zkusit dělit dvojkou a výsledek už je jasný, další se nezkouší. Tady je důležité použití funkce and, kdybyste použili (na první pohled ekvivalentní) foldl1 (&&), tak se bude zkoušet dělit všemi čísly, foldl totiž neví, že && s False bude už vždycky False.

Syntax \x -> ... definuje anonymní funkci parametru x. Právě v případě různých funkcí vyšších řádů (map, foldl, …) se často používají.

prime :: Integer -> Bool
prime n | n < 2     = False --cisla mensi nez 2 nejsou prvocisla
        | otherwise = and (map (\x -> (n `mod` x /= 0)) (takeWhile (\x -> x*x <= n) [2..n]))

A ted už můžeme nadefinovat seznam všech prvočísel.

primes :: [Integer]
primes = filter prime [1..]

Prvních n prvočísel pak dostaneme snadno pomocí take.

prvniPrvocisla :: Int -> [Integer]
prvniPrvocisla n = take n primes

A prvočísla menší než nějaké číslo n pomoci takeWhile

prvocislaMensi :: Integer -> [Integer]
prvocislaMensi n = takeWhile (<n) primes

Minule jsme si ukázali (a naprogramovali) základní funkce pro práci se seznamy v Haskellu. Ukázali jsme si na nich základy Haskellovské syntaxe. Dneska se podíváme na další takové funkce a ukážeme si, jak v Haskellu efektivně s těmito funkcemi pracovat.

V Haskellu je běžné, že na většinu práce se seznamy nepotřebujeme nijak rekurzivně volat svoje funkce. Všechny základní iterace už jsou totiž napsané. To samé platí pro většinu ostatních datových typů. Haskell se snaží konstrukce, která se často opakuji napsat obecně.

Z tohoto důvodu můžeme třeba úplně jednoduše napsat Hornerovo schéma. Stačí si uvědomit, co se v něm přesně počítá. Vlastně vždycky chceme vzít předchozí výsledek, vynásobit ho 10 a přičíst k němu další číslo. To je přesně to, co dělá funkce foldl.

Funkci, kterou je potřeba dát foldl jako parametr (10*x + y) nemusíme definovat zvlášť. Můžeme využít anonymní funkce. Syntaxe je jednoduchá, napiše se \, za něj parametry, potom -> a za ní, co má funkce počítat. V případě funkce, která z čísel x a y počítá 10*x + y, tedy anonymní zápis vypadá jako \x y -> 10*x + y.

horner :: Num a => [a] -> a
horner = foldl (\x y -> 10*x + y) 0

Kromě foldl, která je zleva asociativní, ještě existuje verze foldr, která je naopak asociativní zprava. Samotná funkce foldr je užitečná a dá se snadno představit, co dělá. Stačí si uvědomit, že seznam [1,2,3,4,5] se v Haskellu dá definovat pomoci (:) jako 1:2:3:4:5:[]. Funkce foldr dělá to, že (:) nahradí libovolnou funkcí, a [] nahradí nějakou počáteční hodnotou. Např. foldr (:) [] [1,2,3,4,5] vrátí přesně seznam [1,2,3,4,5]. Pokud (:) nahradíme za (+) a [] za 0, dostaneme přesně to, co dělá foldr (+) 0 [1,2,3,4,5]. A to je 1+(2+(3+(4+(5+0)))). (Naproti tomu foldl (+) 0 [1,2,3,4,5] počítá (((((0+1)+2)+3)+4)+5).)

foldr je dokonce tak obecná, že pomoci ní jde napsat libovolnou primitivně rekurzívní funkci (tj. cokoliv, co umíte naprogramovat pomoci for cyklu, ale např. bez while cyklu).

Pro ukázku si můžeme zkusit napsat třeba map pomoci foldr.

foldrMap :: (a -> b) -> [a] -> [b]
foldrMap f = foldr (\x y -> (f x):y) []

Dokonce se pomocí foldr dá napsat i foldl (spíš pro zajímavost, zamyslete se, jak to vlastně funguje a nepoužívejte to, je to hodně skládání funkci).

foldrFoldl f a bs = foldr (\b g x -> g (f x b)) id bs a 

foldr má oproti foldl ještě jednu výhodu. Za určitých okolností může foldr fungovat i na nekonečných seznamech, to foldl nikdy neumí (potřebuje vždycky dojít až na konec seznamu, než začne počítat).

Takže např. foldr (&&) False (repeat False) skončí, ale foldl (&&) False (repeat False) se zacyklí. Rozdíl je v tom, jak je definované (&&), to říká, že když je první argument False, má vrátit False, jinak vrací druhý argument. Při použití foldr se tedy stačí podívat na první argument a je rozhodnuto, zbytek seznamu není třeba vyhodnocovat. U foldl to tak nefunguje, ta musí projít seznam vždycky celý.

Ukažme si menší trik pro definování Fibonacciho čísel. To, co se v něm děje je, že se sčítá seznam Fibonacciho čísel se seznamem o jedna posunutým, tím dostaneme výsledný seznam. Celé to opět funguje jen díky línému vyhodnocení.

fibs :: [Integer]
fibs = 0:1:(zipWith (+) fibs (tail fibs))

Občas se nám může hodit skládat více funkcí dohromady. Máme několik možnosti, jak to udělat. Minule jsme používali tu možnost, že složení funkci f a g jsme psali jako f (g x). To samé se dá zapsat pomoci f $ g x ($ se v zásadě chová jako závorka od místa, kde je, až do konce výrazu), případně (f . g) x.

prictiJedna x = x+1
vynasobDvema x = 2*x

prictiJedna (vynasobDvema 3), je tedy to samé, jako prictiJedna $ vynasobDvema 3 a také jako (prictiJedna . vynasobDvema) 3. Hlavní rozdíl mezi $ a (.) je, že (.) se aplikuje přímo na dvě funkce a vytváří novou funkci. Na druhou stranu jeho nevýhoda je, že funguje jen na funkce s jedním parametrem vpravo.

Díky skládání funkcí si můžeme ušetřit trochu psaní a napsat některé věci stručněji. Například naše Hornerovo schéma jde napsat také jako

horner2 :: Num a => [a] -> a
horner2 = foldl ((+).(*10)) 0

Kromě kratšího kódu to může učinit kód o něco čitelnějším, a občas to dokonce pomůže kompilátoru v optimalizaci. Styl programování, kde v definici funkce nejsou proměnné se nazývá point-free programming. Pokud se to přehání, vzniklý kód nemusí být úplně dobře čitelný, proto si tento styl vysloužil také přezdívku pointless programming. Nepřehánějte to s point-free, ale nebojte se ho použít, a hlavně ho umějte číst. Poslední parametry, pokud to jde, se vynechávají skoro vždy.

Minule jsme psali skalární součin dvou vektoru pomoci zipWith a sum.

skalarniSoucin1 x y = sum (zipWith (*) x y)

Za pomoci operátoru pro aplikaci funkce si můžeme ušetřit pár závorek a to samé napsat také jako

skalarniSoucin2 x y = sum $ zipWith (*) x y

Relativně snadno se také můžeme zbavit posledního y.

skalarniSoucin3 x = (sum . zipWith (*) x)

Udělat z skalárního součinu kompletně point-free funkci už tak snadné není. Přijdete na to, jak ji vytvořit? (Opět je to spíš těžká otázka, pomoci by vám mohl následující operátor, co dělá?)

(.:) = (.).(.)

(Kdo by chtěl googlit, tak na fórech se tomuto operátoru neformálně říká boobs operator, nebo owl operator.)