Skip to content

← Späť

Cvičenie 3 – Zoznamy (foldr, foldl, list comprehension)

Useful Files


Ciele

  1. Naučiť sa používať funkcie foldr a foldl pre prácu so zoznamami.
  2. Naučiť sa používať množinové abstrakcie (list comprehension).
  3. Vyskúšať vyriešenie väčšej úlohy.
  1. Krok 1: Funkcie foldr a foldl
  2. Úloha 1.1 – listAnd
  3. Úloha 1.2 – myLength
  4. Krok 2: Množinové abstrakcie
  5. Úloha 2.1 – divisors
  6. Úloha 2.2 – isPrime
  7. Krok 3: Komplexnejšia úloha
  8. Úloha 3.1 – histogram
  9. 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):

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 – 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.

listAnd :: [Bool] -> Bool
-- 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:

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 – myLength

Definujte funkciu myLength, ktorá vráti dĺžku zoznamu. Nepoužívajte vstavanú funkciu length.

myLength :: [a] -> Int
myLength :: [a] -> Int
myLength = foldr (\_ acc -> acc + 1) 0

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 – divisors

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]
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 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.

-- 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:

legendColumn  beside  histogramBody      ← stĺpce
                      above
                      legendLine         ← čísla dole

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.

histogramCell 2 3 = " |"   -- 3 >= 2
histogramCell 3 2 = "  "   -- 2 <  3

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).

rfill 2 "5"  = " 5"   -- replicate 1 ' ' ++ "5"
rfill 2 "10" = "10"   -- replicate 0 ' ' ++ "10"

legendCell – bunka legendy. Vypíše len každú piatu hodnotu (n mod 5 == 0), ostatné nahradí medzerami.

legendCell 5 = " 5"
legendCell 3 = "  "
legendCell 0 = " 0"   -- 0 `mod` 5 == 0

legendLine – spodný riadok s číslami položiek 0, 1, …, width-1.

legendLine 3 = legendCell 0 ++ legendCell 1 ++ legendCell 2
             = " 0" ++ "  " ++ "  "
             = " 0    "

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.

legendColumn 6 = map legendCell [6,5,4,3,2,1] ++ ["  "]
               = ["  ", " 5", "  ", "  ", "  ", "  ", "  "]

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ď.

["ab", "cd"] `beside` ["12", "34"] = ["ab12", "cd34"]
["ab"] `above` ["cd"]              = ["ab", "cd"]

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]):

       |
     | |
   | | |
   0

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]

Zdroje

  1. Haskell – Prelude

Top