Ciele
- Naučiž sa používať funkcie
foldrafoldlpre prácu so zoznamami. - Naučiž sa používať množinové abstrakcie (list comprehension).
- Vyskúšať vyriešenie väčšej úlohy.
Postup
Krok 1: Funkcie foldr a foldl
Pri spracovaní zoznamov často potrebujeme prejsť zoznam a aplikovať operáciu na prvoz zoznamu a rekurzívne spracovaný zvyšok zoznamu (akoby sme nahradzovali operator : inou operáciou):
f [] = z
f (x:xs) = x `op` f xs
Tento vzor realizuje funkcia foldr. Takže príklad vyššie sa dá prepísať ako
f = foldr op z
Typ funkcie foldr je nasledovný:
foldr :: (a -> b -> b) -> b -> [a] -> b
Úloha 1.1
Definujte fukciu listAnd, ktorá vráti True, ak všetky hodnoty v zozname sú True, inak vráti False. Implementujte ju najprv pomocou rekurzie a potom pomocou foldr.
listAnd :: [Bool] -> Bool
Poznámka
Funkcia foldr umožňuje ukončiť spracovávanie zoznamu skôr, ako sa spracuje celý zoznam. Napríklad, pri implementácii funkcie listAnd pomocou foldr sa False vráti hneď, ako sa narazí na prvú hodnotu False.
Funkcie foldr a foldl si vieme tiež predstaviť ako prechádzanie zoznamu s akumulovaním výsledku. Zoberme si, napríklad, takúto rekurzívnu funkciu:
f acc [] = acc
f acc (x:xs) = f (acc `op` x) xs
Tá sa dá prepísať pomocou foldl:
f initial xs = foldl op initial xs
ale aj pomocou foldr:
f initial xs = foldr (\x acc -> acc `op` x) initial xs
Pri foldr sa akumulátor nachádza na pravej strane, ale pri foldl na ľavej strane, čo je vidieť na typových definíciách:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b
Úloha 1.2
Definujte fukciu myLength, ktorá vráti dĺžku zoznamu. Nepoužívajte vstavanú funkciu length.
myLength :: [a] -> Int
Krok 2: Množinové abstrakcie
Okrem funkcií vyššieho rádu môžeme na spracovanie zoznamov použiť aj tzv. množinové abstrakcie (list comprehension). Tie majú tvar
[ expression | pattern <- list, predicate ]
Napríklad:
[x^2 | x <- [1..10], even x]
Úloha 2.1
Implementujte funkciu divisors, ktorej výsledkom je zoznam deliteľov kladného celého čísla:
divisors :: Integer -> [Integer]
divisors 12 == [1, 2, 3, 4, 6, 12]
Pomocou funkcie divisors definujte funkciu isPrime, ktorá určí, či číslo je prvočíslom (prvočísla sú deliteľné len číslom 1 a samým sebou).
Krok 3: Komplexnejšia úloha
Skúste využiť všetko, čo ste sa doteraz naučili a vyriešiť komplexnejšiu úlohu.
Úloha 3.1
Definujte funkciu, ktorá vykreslí histogram zo zadaného zoznamu prostredníctvom znakov |, kde vyška každého stlpca zodpovedá počtu výskytov príslušného čísla v zozname. Pričom nech je vykreslená aj legenda — čísla položiek dole a hodnoty naľavo. Pritom nech je v legende vypísaná len každá piata hodnota. Napr. pre zoznam uvedený v kóde nižšie nech je výsledok takýto:
*Main> putStr (histogram values)
10 |
| |
| | |
| | | | |
| | | | | | |
5 | | | | | | | | | |
| | | | | | | | | | | |
| | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | |
0 5 10 15
values :: [Int]
values = [6,2,12,10,7,3,0,12,4,8,7,8,10,13,10,8,2,11,17,9,16,12,14,9,9,2,7,3,7,10,1,11,11,13,10,12,15,9,15,13,9,8,16,1,18,9,10,13,15,5,13,15,11,10,8,1,9,13,10,9,7,14,6,6,9,14,12,17,7,7,4,12,11,4,7,8,10,6,14,6,13,14,4,1,10,1,8,11]
histogram :: [Int] -> String
histogram = undefined
Pri realizácii sa vám budú hodiť nasledujúce funkcie:
Poznámka
Implementáciu rozdeľte na niekoľko samostatných funkcií, napríklad:
histogramCounts :: [Int] -> [Int]
histogramBody :: [Int] -> [String]
legendLine :: Int -> String
legendColumn :: Int -> [String]