Cvičenie 3 – Zoznamy (foldr, foldl, list comprehension)¶
Useful Files¶
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.
Navigation¶
- Krok 1: Funkcie foldr a foldl
- Úloha 1.1 – listAnd
- Úloha 1.2 – myLength
- Krok 2: Množinové abstrakcie
- Úloha 2.1 – divisors
- Úloha 2.2 – isPrime
- Krok 3: Komplexnejšia úloha
- Úloha 3.1 – histogram
- Zdroje
Krok 1: Funkcie foldr a foldl¶
Pri spracovaní zoznamov často potrebujeme prejsť zoznam a aplikovať operáciu na prvý prvok zoznamu a rekurzívne spracovaný zvyšok zoznamu (akoby sme nahradzovali operátor : inou operáciou):
Tento vzor realizuje funkcia foldr. Takže príklad vyššie sa dá prepísať ako
Typ funkcie foldr je nasledovný:
Úloha 1.1 – listAnd¶
Definujte funkciu 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.
-- rekurzia
listAndR :: [Bool] -> Bool
listAndR [] = True
listAndR (x:xs)
| x == False = False
| otherwise = listAndR xs
-- foldr
listAnd :: [Bool] -> Bool
-- listAnd xs = foldr (&&) True xs
listAnd = foldr (&&) True
-- foldr (&&) True už je funkcia, ktorá čaká zoznam — nemusíš jej ho dávať explicitne cez xs
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:
Tá sa dá prepísať pomocou foldl:
ale aj pomocou foldr:
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:
Úloha 1.2 – myLength¶
Definujte funkciu myLength, ktorá vráti dĺžku zoznamu. Nepoužívajte vstavanú funkciu length.
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
Napríklad:
Úloha 2.1 – divisors¶
Implementujte funkciu divisors, ktorej výsledkom je zoznam deliteľov kladného celého čísla:
divisors :: Integer -> [Integer]
divisors n = [d | d <- [1..n], n `mod` d == 0]
-- Čítaj to takto: "pre každé d od 1 po n, ponechaj ho len vtedy,
-- keď n delené d nemá zvyšok (mod je 0, teda d je deliteľ n)".
-- Na príklade divisors 12:
-- prejde d postupne cez [1, 2, 3, ..., 12]
-- testuje 12 `mod` d == 0 pre každé:
-- 1→0 ✓, 2→0 ✓, 3→0 ✓, 4→0 ✓, 5→2 ✗, 6→0 ✓, 7..11 ✗, 12→0 ✓
-- výsledok: [1, 2, 3, 4, 6, 12]
-- divisors 12 = [1, 2, 3, 4, 6, 12]
-- divisors 7 = [1, 7]
-- divisors 1 = [1]
| Symbol | Čo robí |
|---|---|
\| |
V list comprehension oddeľuje výsledný výraz od podmienok/zdroja — čítaj ako „také, že" |
<- |
Postupne naviaže premennú na každý prvok zoznamu vpravo („vyber z") |
.. |
Rozsah — [1..n] vygeneruje postupnosť 1, 2, 3, ..., n |
mod |
Vráti zvyšok po celočíselnom delení |
== |
Porovnanie — vráti True, ak sú si obe strany rovné |
Úloha 2.2 – isPrime¶
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).
isPrime :: Integer -> Bool
isPrime n = divisors n == [1, n]
-- Číslo je prvočíslo práve vtedy, keď má presne dvoch deliteľov: 1 a seba samého.
-- Takže ak sa zoznam deliteľov rovná presne [1, n], je to prvočíslo.
-- isPrime 7 = True -- divisors 7 = [1, 7]
-- isPrime 12 = False -- divisors 12 = [1, 2, 3, 4, 6, 12]
-- isPrime 1 = False -- divisors 1 = [1] (nerovná sa [1, 1])
-- isPrime 2 = True -- divisors 2 = [1, 2]
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 – histogram¶
Definujte funkciu, ktorá vykreslí histogram zo zadaného zoznamu prostredníctvom znakov |, kde výška každého stĺpca 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 numbers = unlines (legendC `beside` (histogramBody counts `above` [legendL]))
where
counts = histogramCounts numbers
legendL = legendLine (length counts)
legendC = legendColumn (maximum counts)
width = length counts
height = maximum counts
histogramCounts :: [Int] -> [Int]
histogramCounts xs = [count x xs | x <- [0..maximum xs]]
count x xs = length (filter (==x) xs)
histogramBody :: [Int] -> [String]
histogramBody counts = map (histogramLine counts) levels
where levels = reverse [1..maximum counts]
histogramLine counts level = concatMap (histogramCell level) counts
histogramCell level count
| count >= level = " |"
|otherwise = " "
legendLine :: Int -> String
legendLine width = concatMap legendCell [0..width-1]
legendCell n
| n `mod` 5 == 0 = rfill 2 (show n)
| otherwise = " "
legendColumn :: Int -> [String]
legendColumn height = map legendCell (reverse [1..height]) ++ [" "]
rfill :: Int -> String -> String
rfill width str = replicate (width - length str) ' ' ++ str
-- poloz dva bloky riadkov vedla seba (riadok po riadku)
beside :: [String] -> [String] -> [String]
beside left right = zipWith (++) left right
-- poloz dva bloky riadkov pod seba
above :: [String] -> [String] -> [String]
above top bottom = top ++ bottom
Vysvetlenie¶
Histogram sa skladá z blokov riadkov ([String]), ktoré sa nakoniec poskladajú dokopy:
Každá „bunka" má šírku 2 znaky (" |", " ", " 5", "10"), preto sú stĺpce aj legenda zarovnané.
Vysvetlenie je na malom príklade xs = [1,2,0,2,1,2].
histogramCounts – pre každé číslo od 0 po maximum xs spočíta, koľkokrát sa v zozname vyskytuje (pomocou count, rovnako ako v cv2).
histogramCounts [1,2,0,2,1,2]
-- maximum = 2, x prejde [0, 1, 2]
-- count 0 = 1, count 1 = 2, count 2 = 3
-- = [1, 2, 3]
histogramCell – jedna bunka stĺpca. Ak je počet výskytov aspoň taký vysoký ako aktuálna úroveň (riadok), vykreslí " |", inak medzery.
histogramLine – jeden riadok histogramu pre danú úroveň. concatMap zavolá histogramCell level na každý počet a výsledné reťazce spojí do jedného.
histogramLine [1,2,3] 2
-- = histogramCell 2 1 ++ histogramCell 2 2 ++ histogramCell 2 3
-- = " " ++ " |" ++ " |"
-- = " | |"
histogramBody – všetky riadky histogramu. Úrovne idú zhora dole (reverse [1..maximum counts]), lebo pri výpise sa ako prvý vypíše horný riadok.
histogramBody [1,2,3]
-- levels = reverse [1..3] = [3, 2, 1]
-- = [ " |" -- úroveň 3
-- , " | |" -- úroveň 2
-- , " | | |" ] -- úroveň 1
rfill – doplní reťazec medzerami zľava na zadanú šírku (zarovnanie doprava).
legendCell – bunka legendy. Vypíše len každú piatu hodnotu (n mod 5 == 0), ostatné nahradí medzerami.
legendLine – spodný riadok s číslami položiek 0, 1, …, width-1.
legendColumn – ľavý stĺpec s hodnotami. Ide tiež zhora dole a na konci má navyše prázdnu bunku " " pre riadok, v ktorom je legendLine.
above – položí bloky pod seba (++ na zoznamoch riadkov). beside – položí bloky vedľa seba: zipWith (++) spojí prvý riadok s prvým, druhý s druhým atď.
histogram – všetko poskladá dokopy a unlines spojí riadky do jedného reťazca s \n na konci každého riadku.
histogram [1,2,0,2,1,2]
-- counts = [1,2,3]
-- legendC = [" "," "," "," "]
-- histogramBody counts `above` [legendL]
-- = [" |", " | |", " | | |", " 0 "]
-- legendC `beside` (...)
-- = [" |", " | |", " | | |", " 0 "]
Výstup putStr (histogram [1,2,0,2,1,2]):
Poznámka: width a height vo where funkcie histogram sa nikde nepoužívajú, dajú sa vymazať.
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]