import Data.Char (toLower) -- Labs -- 1. {- Funkcie foldr a foldl cieľ 1 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. -} -- recursion 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: 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 myLength = foldr (\_ acc -> acc + 1) 0 ---------------------------------------------- {- Množinové abstrakcie cieľ 2 ---------------------------------------------- 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 12 == [1, 2, 3, 4, 6, 12] divisors :: Integer -> [Integer] divisors n = [d | d <- [1..n], n `mod` d == 0] -- Všetko sedí presne so zadaním (divisors 12 == [1,2,3,4,6,12]). Riešenie Úlohy 2.1: -- divisors — cez list comprehension (z Kroku 2 v cv3.md): -- 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 == 0pre každé:1→0✓, 2→0✓, 3→0✓, 4→0✓, 5→2✗, 6→0✓, 7..11→nezhoduje sa✗, 12→0✓` -- výsledok: [1, 2, 3, 4, 6, 12] ✓ presne sedí so zadaním -- Glosár symbolov použitých v riešení divisors/isPrime: -- 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é -- Výstup (overené v GHC): -- divisors 12 = [1, 2, 3, 4, 6, 12] -- divisors 7 = [1, 7] -- divisors 1 = [1] -- isPrime 7 = True -- isPrime 12 = False -- isPrime 1 = False -- isPrime 2 = True ---------------------------------------------- -- 2.2 ---------------------------------------------- {- 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 7 == True, isPrime 12 == False 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. -- Overené príklady: -- 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] -- isPrime 1 vyjde správne False (1 nie je prvočíslo), pretože divisors 1 = [1] sa nerovná [1, 1]. ---------------------------------------------- -- 3 ---------------------------------------------- {- Komplexnejšia úloha cieľ 3 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: maximum reverse concat alebo concatMap replicate zipWith unlines Poznámka Implementáciu rozdeľte na niekoľko samostatných funkcií, napríklad: -} 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 ---------------------------------------------- -- main (to run this code: bash> ./start) main :: IO () main = do -- 1.1 -- print (listAndR [True, True, True]) -- print (listAnd [True, True, False]) -- 1.2 -- print (myLength [1,2,3,4,5,6]) -- 2.1 -- print (divisors 12) -- 2.2 -- print (isPrime 12) -- 3 -- 3.1 print (histogramInt values)