Skip to content

← Späť

Exercises - kamil

Useful Files

  1. Ako s tým pracovať
  2. Pripomenutie: where
  3. Ťahák funkcií – čo robia na príkladoch
  4. Úroveň 1 – základy where, práca s prvkami zoznamu
  5. Úloha 1.1 – obdĺžnik
  6. Úloha 1.2 – BMI
  7. Úloha 1.3 – stred zoznamu
  8. Úloha 1.4 – výmena krajných prvkov
  9. Úloha 1.5 – druhé mocniny párnych čísel
  10. Úloha 1.6 – dlhé slová
  11. Úloha 1.7 – ceny s DPH
  12. Úloha 1.8 – je zoznam usporiadaný na koncoch?
  13. Úroveň 2 – rekurzia a porovnávanie vzorov
  14. Úloha 2.1 – počet párnych
  15. Úloha 2.2 – vlastné take a drop
  16. Úloha 2.3 – vlastné zip
  17. Úloha 2.4 – reverse s akumulátorom
  18. Úloha 2.5 – maximum
  19. Úloha 2.6 – číslice čísla
  20. Úloha 2.7 – Collatzova postupnosť
  21. Úloha 2.8 – Fibonacciho čísla
  22. Úloha 2.9 – skupiny rovnakých prvkov
  23. Úloha 2.10 – vloženie do usporiadaného zoznamu a triedenie
  24. Úroveň 3 – map, filter, concatMap, replicate, zipWith, reverse
  25. Úloha 3.1 – zdvojenie prvkov
  26. Úloha 3.2 – rozbalenie dvojíc
  27. Úloha 3.3 – skalárny súčin
  28. Úloha 3.4 – rozdiely susedov
  29. Úloha 3.5 – palindróm z textu
  30. Úloha 3.6 – očíslovanie položiek
  31. Úloha 3.7 – pozície prvku
  32. Úloha 3.8 – každý n-tý prvok
  33. Úloha 3.9 – najlepší študent
  34. Úloha 3.10 – Pascalov trojuholník
  35. Úroveň 3F – foldr, foldl a množinové abstrakcie
  36. Úloha 3F.1 – listOr dvoma spôsobmi
  37. Úloha 3F.2 – súčet a súčin
  38. Úloha 3F.3 – map a filter cez foldr
  39. Úloha 3F.4 – dĺžka a otočenie cez foldl
  40. Úloha 3F.5 – číslice na číslo
  41. Úloha 3F.6 – počet prvkov spĺňajúcich podmienku
  42. Úloha 3F.7 – elem cez foldr a lenivosť
  43. Úloha 3F.8 – compress cez foldr
  44. Úloha 3F.9 – priemer jedným prechodom
  45. Úloha 3F.10 – samohlásky
  46. Úloha 3F.11 – násobilka
  47. Úloha 3F.12 – dokonalé čísla
  48. Úloha 3F.13 – pytagorejské trojice
  49. Úloha 3F.14 – to isté tromi spôsobmi
  50. Úroveň 4 – text: lines, unlines, words, unwords
  51. Úloha 4.1 – počet slov
  52. Úloha 4.2 – veľké začiatočné písmená
  53. Úloha 4.3 – najdlhšie slovo
  54. Úloha 4.4 – otočenie slov
  55. Úloha 4.5 – výskyty slova
  56. Úloha 4.6 – číslovanie riadkov
  57. Úloha 4.7 – odstránenie prázdnych riadkov
  58. Úloha 4.8 – doplnenie medzerami a tabuľka
  59. Úloha 4.9 – riadky so slovom
  60. Úroveň 5 – väčšie úlohy
  61. Úloha 5.1 – Caesarova šifra
  62. Úloha 5.2 – kódovanie dĺžkou behu
  63. Úloha 5.3 – spracovanie CSV
  64. Úloha 5.4 – matice ako zoznamy zoznamov
  65. Úloha 5.5 – pokladničný bloček
  66. Úloha 5.6 – oddeľovanie tisícov
  67. Úloha 5.7 – štatistika textu

Haskell – úlohy na precvičenie (where, zoznamy, rekurzia)

Ako s tým pracovať

Zbierka má 5 úrovní a doplnkovú úroveň 3F na foldy, od jednoduchých funkcií po väčšie úlohy. Každá úloha je postavená na lokálnych funkciách v where. Riešenia tu nie sú zámerne – keď nejakú úlohu vyriešiš, pošli mi kód a skontrolujem ho.

  • Píš všetko do jedného súboru, napr. precvicovanie.hs, a načítaj ho cez ghci precvicovanie.hs (po zmene :r).
  • Vždy najprv napíš typovú signatúru, až potom telo funkcie.
  • Príklady sú zapísané ako vyraz == ocakavanyVysledok. V GHCi musia vrátiť True.
  • Tip na testovanie: na koniec súboru si daj tests = [ priklad1, priklad2, ... ] a v GHCi spusti and tests.

Pripomenutie: where

where definuje pomocné hodnoty a funkcie, ktoré patria k jednej rovnici. Vidia parametre funkcie a platia pre všetky strážcov (|) tejto rovnice. Musia byť odsadené viac ako názov funkcie.

Pomocné hodnoty bez parametrov:

triangleInfo :: Double -> Double -> Double -> String
triangleInfo a b c
  | not valid = "neplatny trojuholnik"
  | otherwise = "obvod " ++ show obvod ++ ", obsah " ++ show obsah
  where
    obvod = a + b + c
    s     = obvod / 2
    obsah = sqrt (s * (s - a) * (s - b) * (s - c))
    valid = a + b > c && a + c > b && b + c > a

Lokálna funkcia s parametrom, použitá v map:

sumOfSquares :: [Int] -> Int
sumOfSquares xs = sum (map square xs)
  where
    square x = x * x

Rekurzívna pomocná funkcia s akumulátorom (často sa volá go):

sumAcc :: [Int] -> Int
sumAcc xs = go 0 xs
  where
    go acc []     = acc
    go acc (y:ys) = go (acc + y) ys

Ťahák funkcií – čo robia na príkladoch

Každý riadok ukazuje volanie a jeho výsledok, ako keby si ho napísal do GHCi. Funkcie sú zoradené podľa cvičení, v ktorých sa objavili.

Konštruktory a operátory zoznamov (cvičenie 2)

Funkcia Typ Príklad Výsledok
[] [a] [] prázdny zoznam
(:) a -> [a] -> [a] 1 : [2,3] [1,2,3]
(:) 'a' : "hoj" "ahoj"
(++) [a] -> [a] -> [a] [1,2] ++ [3,4] [1,2,3,4]
(++) "ahoj " ++ "svet" "ahoj svet"
(!!) [a] -> Int -> a "haskell" !! 0 'h'
(!!) [10,20,30] !! 2 30
rozsah [1..5] [1,2,3,4,5]
rozsah s krokom [2,4..10] [2,4,6,8,10]
rozsah znakov ['a'..'e'] "abcde"

Základné funkcie pre zoznamy (cvičenie 2)

Funkcia Typ Príklad Výsledok
head [a] -> a head [5,6,7] 5
tail [a] -> [a] tail [5,6,7] [6,7]
last [a] -> a last [5,6,7] 7
init [a] -> [a] init [5,6,7] [5,6]
length [a] -> Int length "ahoj" 4
null [a] -> Bool null [] / null [1] True / False
reverse [a] -> [a] reverse "admin" "nimda"
take Int -> [a] -> [a] take 3 "haskell" "has"
drop Int -> [a] -> [a] drop 3 "haskell" "kell"
elem Eq a => a -> [a] -> Bool elem 'k' "haskell" True
replicate Int -> a -> [a] replicate 3 'x' "xxx"
replicate replicate 2 [1,2] [[1,2],[1,2]]
concat [[a]] -> [a] concat [[1,2],[3],[4,5]] [1,2,3,4,5]
concat concat ["ab","cd"] "abcd"
sum [a] -> a sum [1,2,3,4] 10
product [a] -> a product [1,2,3,4] 24
maximum [a] -> a maximum [3,9,2] 9
minimum [a] -> a minimum [3,9,2] 2
and [Bool] -> Bool and [True,False,True] False
or [Bool] -> Bool or [True,False,True] True

Pozor: head [], tail [], last [], init [] a maximum [] spadnú s chybou.

Funkcie vyššieho rádu (cvičenia 2 a 3)

Funkcia Typ Príklad Výsledok
map (a -> b) -> [a] -> [b] map (*2) [1,2,3] [2,4,6]
map map length ["ahoj","admin"] [4,5]
filter (a -> Bool) -> [a] -> [a] filter even [1,2,3,4,5,6] [2,4,6]
filter filter (/= ' ') "a b c" "abc"
concatMap (a -> [b]) -> [a] -> [b] concatMap (replicate 2) "abc" "aabbcc"
concatMap concatMap show [1,2,3] "123"
zip [a] -> [b] -> [(a,b)] zip [1,2,3] "ab" [(1,'a'),(2,'b')]
unzip [(a,b)] -> ([a],[b]) unzip [(1,'a'),(2,'b')] ([1,2],"ab")
zipWith (a -> b -> c) -> [a] -> [b] -> [c] zipWith (+) [1,2,3] [10,20,30] [11,22,33]
zipWith zipWith replicate [3,1] "ab" ["aaa","b"]
takeWhile (a -> Bool) -> [a] -> [a] takeWhile (< 4) [1,2,5,3] [1,2]
dropWhile (a -> Bool) -> [a] -> [a] dropWhile (< 4) [1,2,5,3] [5,3]
any (a -> Bool) -> [a] -> Bool any even [1,3,4] True
all (a -> Bool) -> [a] -> Bool all even [2,4,5] False
foldr (a -> b -> b) -> b -> [a] -> b foldr (+) 0 [1,2,3] 6
foldr foldr (:) [] "abc" "abc"
foldl (b -> a -> b) -> b -> [a] -> b foldl (+) 0 [1,2,3] 6
foldl foldl (\acc x -> x : acc) [] "abc" "cba"

Text (cvičenie 2 a modul Data.Char)drop

Funkcia Typ Príklad Výsledok
words String -> [String] words "ahoj admin" ["ahoj","admin"]
words words " ahoj admin " ["ahoj","admin"]
unwords [String] -> String unwords ["ahoj","admin"] "ahoj admin"
lines String -> [String] lines "prvy\ndruhy" ["prvy","druhy"]
unlines [String] -> String unlines ["prvy","druhy"] "prvy\ndruhy\n"
show a -> String show 42 "42"
show show [1,2] "[1,2]"
read String -> a read "42" :: Int 42
toUpper Char -> Char toUpper 'a' 'A'
toLower Char -> Char map toLower "AhOj" "ahoj"
isDigit Char -> Bool filter isDigit "a1b22" "122"
isUpper, isLower Char -> Bool filter isUpper "Ahoj Svet" "AS"
ord Char -> Int ord 'a' 97
chr Int -> Char chr 98 'b'

Pozor: unwords a unlines nie sú presný opak words a lines – words zahodí nadbytočné medzery a unlines pridá \n aj za posledný riadok.

Čísla (cvičenie 1)

Funkcia Typ Príklad Výsledok
div Int -> Int -> Int div 17 5 3
mod Int -> Int -> Int mod 17 5 2
/ Double -> Double -> Double 7 / 2 3.5
^ 2 ^ 10 1024
sqrt Double -> Double sqrt 16 4.0
abs abs (-5) 5
even, odd Int -> Bool even 4 / odd 4 True / False
max, min a -> a -> a max 3 7 7
fromIntegral Int -> Double fromIntegral (length [1,2]) / 4 0.5

div a mod sa dajú písať aj ako operátor so spätnými apostrofmi: 17 `div` 5 je to isté ako div 17 5.

Lambda a sekcie operátorov

Zápis Čo znamená Príklad Výsledok
\x -> x * 2 funkcia bez mena (\x -> x * 2) 5 10
(*2) \x -> x * 2 map (*2) [1,2] [2,4]
(2^) \x -> 2 ^ x map (2^) [1,2,3] [2,4,8]
(^2) \x -> x ^ 2 map (^2) [1,2,3] [1,4,9]
(+1) \x -> x + 1 map (+1) [5,8] [6,9]

Ako počítajú foldr a foldl

foldr nahradí každé : v zozname funkciou a [] počiatočnou hodnotou. Zátvorky idú sprava:

[1, 2, 3]           =  1 :  (2 :  (3 :  []))
foldr f z [1,2,3]   =  1 `f` (2 `f` (3 `f` z))

foldr (+) 0 [1,2,3]
= 1 + foldr (+) 0 [2,3]
= 1 + (2 + foldr (+) 0 [3])
= 1 + (2 + (3 + foldr (+) 0 []))
= 1 + (2 + (3 + 0))
= 6

foldl nesie akumulátor zľava – začne počiatočnou hodnotou a postupne k nej pridáva prvky:

foldl f z [1,2,3]   =  ((z `f` 1) `f` 2) `f` 3

foldl (+) 0 [1,2,3]
= foldl (+) (0 + 1) [2,3]
= foldl (+) ((0 + 1) + 2) [3]
= foldl (+) (((0 + 1) + 2) + 3) []
= ((0 + 1) + 2) + 3
= 6

Rozdiel vidno pri operácii, kde záleží na poradí, napríklad odčítaní:

foldr (-) 0 [1,2,3]  =  1 - (2 - (3 - 0))  =  2
foldl (-) 0 [1,2,3]  =  ((0 - 1) - 2) - 3  =  -6

Poradie argumentov funkcie je opačné – pri foldr je akumulátor vpravo, pri foldl vľavo:

foldr (\x acc -> ...) z xs   -- prvok, akumulátor
foldl (\acc x -> ...) z xs   -- akumulátor, prvok

Na krokovej funkcii do foldu sa výborne hodí where:

countSpaces :: String -> Int
countSpaces s = foldr step 0 s
  where
    step c acc
      | c == ' '  = acc + 1
      | otherwise = acc

-- countSpaces "a b c" == 2

Množinové abstrakcie (cvičenie 3)

Tvar [ výraz | vzor <- zoznam, podmienka ] – vezmi prvky zo zoznamu, nechaj tie, ktoré spĺňajú podmienku, a každý prepočítaj výrazom.

[x * 2 | x <- [1..5]]                 == [2,4,6,8,10]
[x | x <- [1..10], even x]            == [2,4,6,8,10]
[x ^ 2 | x <- [1..10], odd x]         == [1,9,25,49,81]
[c | c <- "Ahoj Svet", c /= ' ']      == "AhojSvet"
[(x, y) | x <- [1,2], y <- "ab"]      == [(1,'a'),(1,'b'),(2,'a'),(2,'b')]
[n | (n, b) <- [("Eva",72), ("Adam",43)], b > 50]  == ["Eva"]

Posledný príklad ukazuje, že vľavo od <- môže byť aj vzor, napríklad dvojica.

Na Data.Char treba na začiatku súboru import Data.Char (toUpper, toLower, isDigit, isLower, ord, chr).

Úroveň 1 – základy where, práca s prvkami zoznamu

Cieľ: zvyknúť si pomenovať medzivýsledky vo where a použiť jednoduché map a filter s lokálnou funkciou.

Úloha 1.1 – obdĺžnik

Vráť dvojicu (obvod, obsah) obdĺžnika so stranami a a b. Obvod aj obsah definuj vo where ako obvod a obsah.

rectangleInfo :: Double -> Double -> (Double, Double)

rectangleInfo 3 4 == (14.0, 12.0)
Riešenie
rectangleInfo :: Double -> Double -> (Double, Double)
rectangleInfo a b = (obvod, obsah)
  where
    obvod = 2 * (a + b)
    obsah = a * b

Výsledok je dvojica (obvod, obsah); obe hodnoty sú pomenované vo where, takže hlavný riadok čítaš ako vetu.

Úloha 1.2 – BMI

Na základe hmotnosti (kg) a výšky (m) vráť kategóriu: pod 18.5 "podvaha", pod 25 "norma", pod 30 "nadvaha", inak "obezita". Hodnotu bmi vypočítaj vo where a použi ju v strážcoch.

bmiCategory :: Double -> Double -> String

bmiCategory 70 1.75 == "norma"
bmiCategory 50 1.80 == "podvaha"
Riešenie
bmiCategory :: Double -> Double -> String
bmiCategory w h
  | bmi < 18.5 = "podvaha"
  | bmi < 25   = "norma"
  | bmi < 30   = "nadvaha"
  | otherwise  = "obezita"
  where
    bmi = w / h ^ 2

bmi sa vypočíta raz a vidia ho všetci strážcovia. Strážcovia sa skúšajú zhora nadol, preto netreba písať dolné hranice (bmi >= 18.5 && bmi < 25).

Úloha 1.3 – stred zoznamu

Vráť zoznam bez prvého a posledného prvku. Použi tail a init. Pre zoznam kratší ako 2 prvky vráť prázdny zoznam (strážca s length).

middle :: [a] -> [a]

middle [1,2,3,4,5] == [2,3,4]
middle "ab" == ""
middle [7] == []
Riešenie
middle :: [a] -> [a]
middle xs
  | length xs < 2 = []
  | otherwise     = init (tail xs)

-- alternatíva so vzormi
middle' []  = []
middle' [_] = []
middle' xs  = init (tail xs)

tail odstráni prvý prvok, init posledný. Strážca chráni pred init [], ktorý by spadol. Vo vzoroch _ znamená „ľubovoľný prvok, nepotrebujem jeho meno“.

Úloha 1.4 – výmena krajných prvkov

Vymeň prvý a posledný prvok zoznamu. Vo where si definuj prvy, posledny a vnutro (pomocou head, last, init, tail). Zoznamy kratšie ako 2 prvky vráť nezmenené.

swapEnds :: [a] -> [a]

swapEnds [1,2,3,4] == [4,2,3,1]
swapEnds "haskell" == "laskelh"
swapEnds "a" == "a"
Riešenie
swapEnds :: [a] -> [a]
swapEnds xs
  | length xs < 2 = xs
  | otherwise     = posledny : vnutro ++ [prvy]
  where
    prvy     = head xs
    posledny = last xs
    vnutro   = init (tail xs)

Hodnoty vo where sa počítajú lenivo – až keď ich niekto použije. Pre krátky zoznam vráti prvý strážca xs a head xs sa nikdy nevyhodnotí, takže nič nespadne. posledny : vnutro ++ [prvy] sa číta ako posledny : (vnutro ++ [prvy]).

Úloha 1.5 – druhé mocniny párnych čísel

Vyber párne čísla a umocni ich na druhú. Na umocnenie si vo where definuj funkciu square x.

squaresOfEvens :: [Int] -> [Int]

squaresOfEvens [1,2,3,4,5,6] == [4,16,36]
Riešenie
squaresOfEvens :: [Int] -> [Int]
squaresOfEvens xs = map square (filter even xs)
  where
    square x = x * x

-- alternatíva: množinová abstrakcia
squaresOfEvens' xs = [x * x | x <- xs, even x]

Najprv filter nechá párne čísla, potom map každé umocní. Čítaj zvnútra von.

Úloha 1.6 – dlhé slová

Spočítaj, koľko slov je dlhších ako n znakov. Vo where definuj predikát isLong w. Všimni si, že isLong vidí parameter n vonkajšej funkcie.

countLong :: Int -> [String] -> Int

countLong 3 ["ab", "haskell", "fun", "list"] == 2
Riešenie
countLong :: Int -> [String] -> Int
countLong n ws = length (filter isLong ws)
  where
    isLong w = length w > n

isLong má vlastný parameter w, ale n si berie z vonkajšej funkcie – preto nemôže byť definovaná mimo where bez ďalšieho parametra.

Úloha 1.7 – ceny s DPH

Pripočítaj k cenám DPH v percentách. Vo where definuj withVat p.

addVat :: Double -> [Double] -> [Double]

addVat 20 [10, 50] == [12.0, 60.0]
Riešenie
addVat :: Double -> [Double] -> [Double]
addVat rate prices = map withVat prices
  where
    withVat p = p * (1 + rate / 100)

Rovnaký vzor ako 1.6: lokálna funkcia s jedným parametrom, ktorá používa parameter vonkajšej funkcie (rate).

Úloha 1.8 – je zoznam usporiadaný na koncoch?

Vráť True, ak je zoznam neprázdny a jeho prvý prvok je menší ako posledný a zároveň zoznam obsahuje číslo 0. Každú podmienku pomenuj vo where (neprazdny, rastie, maNulu) a výsledok zlož z nich.

checkList :: [Int] -> Bool

checkList [1, 0, 5] == True
checkList [5, 0, 1] == False
checkList [] == False

Pozor: head [] spadne. Zamysli sa, prečo to vďaka lenivému vyhodnocovaniu a && nevadí, ak je neprazdny prvý.

Riešenie
checkList :: [Int] -> Bool
checkList xs = neprazdny && rastie && maNulu
  where
    neprazdny = not (null xs)
    rastie    = head xs < last xs
    maNulu    = elem 0 xs

&& vyhodnocuje zľava a pravú stranu počíta, len ak je ľavá True. Pre [] je neprazdny False, rastie sa nevyhodnotí a head [] sa nezavolá.

Úroveň 2 – rekurzia a porovnávanie vzorov

Cieľ: písať rekurziu cez vzory [] a (x:xs) a používať rekurzívne pomocné funkcie (go) vo where. V tejto úrovni nepoužívaj zabudované funkcie, ktoré úlohu priamo riešia (take, zip, reverse, maximum …).

Úloha 2.1 – počet párnych

Rekurzívne spočítaj párne čísla v zozname. Použi vzory a strážcov.

countEven :: [Int] -> Int

countEven [1,2,4,7,8] == 3
countEven [] == 0
Riešenie
countEven :: [Int] -> Int
countEven [] = 0
countEven (x:xs)
  | even x    = 1 + countEven xs
  | otherwise = countEven xs

Základný prípad [] ukončí rekurziu. Pri neprázdnom zozname sa pozrieme na hlavu x a rekurzívne spracujeme chvost xs.

Úloha 2.2 – vlastné take a drop

myTake :: Int -> [a] -> [a]
myDrop :: Int -> [a] -> [a]

myTake 3 [1..10] == [1,2,3]
myTake 5 "abc" == "abc"
myDrop 2 "haskell" == "skell"
myDrop 9 [1,2] == []
Riešenie
myTake :: Int -> [a] -> [a]
myTake _ [] = []
myTake n (x:xs)
  | n <= 0    = []
  | otherwise = x : myTake (n - 1) xs

myDrop :: Int -> [a] -> [a]
myDrop _ [] = []
myDrop n (x:xs)
  | n <= 0    = x : xs
  | otherwise = myDrop (n - 1) xs

Rekurzia beží na dvoch veciach naraz: číslo klesá a zoznam sa skracuje; skončí sa pri tom, čo nastane skôr. Namiesto x : xs sa dá písať aj as-vzor l@(x:xs) a vrátiť l.

Úloha 2.3 – vlastné zip

Výsledok je taký dlhý ako kratší zo zoznamov.

myZip :: [a] -> [b] -> [(a, b)]

myZip [1,2,3] "ab" == [(1,'a'), (2,'b')]
Riešenie
myZip :: [a] -> [b] -> [(a, b)]
myZip (x:xs) (y:ys) = (x, y) : myZip xs ys
myZip _      _      = []

Prvá rovnica sa použije len vtedy, keď sú oba zoznamy neprázdne. Všetko ostatné (aspoň jeden prázdny) zachytí druhá rovnica so _. Poradie rovníc je dôležité.

Úloha 2.4 – reverse s akumulátorom

Otoč zoznam pomocou funkcie go vo where, ktorá nesie akumulátor. Porovnaj s verziou myReverse (x:xs) = myReverse xs ++ [x] – ktorá je rýchlejšia a prečo?

myReverse :: [a] -> [a]
myReverse xs = go xs []
  where
    go = ...

myReverse [1,2,3] == [3,2,1]
Riešenie
myReverse :: [a] -> [a]
myReverse xs = go xs []
  where
    go []     acc = acc
    go (y:ys) acc = go ys (y : acc)

go [1,2,3] [] → go [2,3] [1] → go [3] [2,1] → go [] [3,2,1] → [3,2,1]. Každý prvok sa len raz prilepí na začiatok akumulátora. Verzia s ++ [x] musí pri každom kroku prejsť celý doterajší výsledok, takže je kvadratická.

Úloha 2.5 – maximum

Rekurzívne nájdi najväčší prvok. Pre prázdny zoznam použi error "prazdny zoznam". Skús dve verzie: priamu rekurziu a verziu s go, ktorá si pamätá doteraz najväčší prvok.

maxList :: [Int] -> Int

maxList [3,9,2] == 9
maxList [-5] == -5
Riešenie
maxList :: [Int] -> Int
maxList []     = error "prazdny zoznam"
maxList [x]    = x
maxList (x:xs) = max x (maxList xs)

-- verzia s akumulátorom
maxList' :: [Int] -> Int
maxList' []     = error "prazdny zoznam"
maxList' (x:xs) = go x xs
  where
    go best []     = best
    go best (y:ys) = go (max best y) ys

V priamej verzii je základný prípad jednoprvkový zoznam [x]. Vo verzii s go je prvý prvok počiatočný „doteraz najväčší“ a go ho porovnáva s ďalšími.

Úloha 2.6 – číslice čísla

Rozlož nezáporné číslo na zoznam číslic (využi mod a div ako pri sumDigits z cvičenia 1). Pomocnú rekurzívnu funkciu daj do where.

digits :: Int -> [Int]

digits 1234 == [1,2,3,4]
digits 0 == [0]
Riešenie
digits :: Int -> [Int]
digits n = go n []
  where
    go k acc
      | k < 10    = k : acc
      | otherwise = go (k `div` 10) (k `mod` 10 : acc)

-- bez akumulátora
digits' n
  | n < 10    = [n]
  | otherwise = digits' (n `div` 10) ++ [n `mod` 10]

mod dá poslednú číslicu, div ju odstráni. Číslice prichádzajú od konca, preto ich go lepí na začiatok akumulátora a poradie vyjde správne. Podmienka k < 10 zaistí, že digits 0 == [0].

Úloha 2.7 – Collatzova postupnosť

Začni číslom n. Ak je párne, ďalšie je n div 2, inak 3*n + 1. Skonči pri 1. Výpočet ďalšieho čísla daj do funkcie next vo where.

collatz :: Int -> [Int]

collatz 6 == [6,3,10,5,16,8,4,2,1]
collatz 1 == [1]

Rozšírenie: longestCollatz :: Int -> Int vráti číslo z rozsahu 1..n s najdlhšou postupnosťou.

Riešenie
collatz :: Int -> [Int]
collatz 1 = [1]
collatz n = n : collatz (next n)
  where
    next k
      | even k    = k `div` 2
      | otherwise = 3 * k + 1

longestCollatz :: Int -> Int
longestCollatz n = snd (maximum [(length (collatz k), k) | k <- [1..n]])

next počíta jeden krok, rekurzia v collatz ich reťazí. V rozšírení vytvoríme dvojice (dĺžka, číslo); maximum porovnáva dvojice najprv podľa prvej zložky, takže vyhrá najdlhšia postupnosť a snd z nej vytiahne číslo.

Úloha 2.8 – Fibonacciho čísla

Vráť prvých n Fibonacciho čísel. Použi go vo where s dvoma akumulátormi (posledné dve čísla) a počítadlom.

fibList :: Int -> [Integer]

fibList 7 == [0,1,1,2,3,5,8]
fibList 0 == []
Riešenie
fibList :: Int -> [Integer]
fibList n = go n 0 1
  where
    go 0 _ _ = []
    go k a b = a : go (k - 1) b (a + b)

a a b sú dve posledné čísla. V každom kroku vrátime a a posunieme okno: nové a je b, nové b je a + b. k počíta, koľko čísel ešte chýba.

Úloha 2.9 – skupiny rovnakých prvkov

Zoskup idúce po sebe rovnaké znaky a spočítaj ich. Vo where si definuj, koľko znakov na začiatku je rovnakých ako x, a čo zostane za nimi (môžeš napísať vlastné rekurzívne pomocné funkcie, alebo použiť takeWhile a dropWhile).

runLength :: String -> [(Char, Int)]

runLength "aaabccdd" == [('a',3), ('b',1), ('c',2), ('d',2)]
runLength "" == []
Riešenie
runLength :: String -> [(Char, Int)]
runLength []     = []
runLength (x:xs) = (x, 1 + length same) : runLength rest
  where
    same = takeWhile (== x) xs
    rest = dropWhile (== x) xs

takeWhile (== x) zoberie rovnaké znaky za x, dropWhile (== x) vráti, čo zostane. 1 + je samotné x. Rekurzia pokračuje na zvyšku.

Úloha 2.10 – vloženie do usporiadaného zoznamu a triedenie

Najprv napíš insert, ktorý vloží prvok na správne miesto do usporiadaného zoznamu. Potom pomocou neho napíš triedenie vkladaním – insert môže byť lokálna funkcia vo where funkcie insertionSort.

insertionSort :: Ord a => [a] -> [a]

insertionSort [5,2,9,1,3] == [1,2,3,5,9]
insertionSort "haskell" == "aehklls"
Riešenie
insertionSort :: Ord a => [a] -> [a]
insertionSort []     = []
insertionSort (x:xs) = insert x (insertionSort xs)
  where
    insert y [] = [y]
    insert y (z:zs)
      | y <= z    = y : z : zs
      | otherwise = z : insert y zs

-- to isté cez foldr
insertionSort' xs = foldr insert [] xs
  where
    insert y [] = [y]
    insert y (z:zs)
      | y <= z    = y : z : zs
      | otherwise = z : insert y zs

Najprv rekurzívne utriedime chvost, potom doň vložíme hlavu. insert ide po usporiadanom zozname, kým nenájde prvý väčší prvok. Druhá verzia ukazuje, že toto je presne vzor foldr.

Úroveň 3 – map, filter, concatMap, replicate, zipWith, reverse

Cieľ: riešiť úlohy bez explicitnej rekurzie, skladaním funkcií vyššieho rádu. Funkcie, ktoré im odovzdávaš, pomenuj vo where (nie lambda), aby bolo jasné, čo robia.

Úloha 3.1 – zdvojenie prvkov

Každý prvok zopakuj n-krát. Použi concatMap a vo where funkciu rep x.

stutter :: Int -> [a] -> [a]

stutter 2 "abc" == "aabbcc"
stutter 3 [1,2] == [1,1,1,2,2,2]
Riešenie
stutter :: Int -> [a] -> [a]
stutter n xs = concatMap rep xs
  where
    rep x = replicate n x

rep urobí z jedného prvku zoznam, napr. 'a' → "aa". concatMap to spraví pre každý prvok a výsledky spojí.

Úloha 3.2 – rozbalenie dvojíc

Opak úlohy 2.9: z dvojíc (počet, prvok) vytvor zoznam. Použi concatMap a replicate.

expand :: [(Int, a)] -> [a]

expand [(3,'a'), (1,'b'), (2,'c')] == "aaabcc"
Riešenie
expand :: [(Int, a)] -> [a]
expand pairs = concatMap unpack pairs
  where
    unpack (k, x) = replicate k x

Lokálna funkcia môže rozložiť dvojicu priamo v parametri vzorom (k, x).

Úloha 3.3 – skalárny súčin

dotProduct :: [Int] -> [Int] -> Int

dotProduct [1,2,3] [4,5,6] == 32
Riešenie
dotProduct :: [Int] -> [Int] -> Int
dotProduct xs ys = sum (zipWith (*) xs ys)

zipWith (*) vynásobí prvky na rovnakých pozíciách ([4,10,18]), sum ich sčíta.

Úloha 3.4 – rozdiely susedov

Vráť rozdiely medzi susednými prvkami. Pomôcka: zipWith so zoznamom posunutým o jeden prvok (tail). Pre prázdny zoznam vráť [] – over si, prečo by inak tail [] spadol.

differences :: [Int] -> [Int]

differences [1,4,9,16] == [3,5,7]
differences [5] == []
differences [] == []

Rozšírenie: isSorted :: [Int] -> Bool pomocou differences alebo zipWith (<=).

Riešenie
differences :: [Int] -> [Int]
differences [] = []
differences xs = zipWith (-) (tail xs) xs

-- bez špeciálneho prípadu: drop 1 na [] nespadne
differences' xs = zipWith (-) (drop 1 xs) xs

isSorted :: [Int] -> Bool
isSorted xs = and (zipWith (<=) xs (drop 1 xs))

Zoznam zarovnaný so sebou posunutým o jeden prvok dá dvojice susedov: [4,9,16] proti [1,4,9]. zipWith najprv rozoberá prvý zoznam, preto by tail [] spadol – drop 1 [] vráti [].

Úloha 3.5 – palindróm z textu

Zisti, či je text palindróm, ak ignorujeme medzery a veľkosť písmen. Vo where definuj cleaned (pomocou filter a map toLower) a porovnaj ho s jeho reverse.

isPalindromeText :: String -> Bool

isPalindromeText "Jelenovi Pivo Nelej" == True
isPalindromeText "Haskell" == False
Riešenie
import Data.Char (toLower)

isPalindromeText :: String -> Bool
isPalindromeText s = cleaned == reverse cleaned
  where
    cleaned = map toLower (filter (/= ' ') s)

Najprv text upravíme do porovnateľného tvaru a pomenujeme ho, potom ho porovnáme s jeho otočením.

Úloha 3.6 – očíslovanie položiek

Očísluj položky od 1. Použi zipWith s nekonečným zoznamom [1..] a vo where funkciu format i s.

numberItems :: [String] -> [String]

numberItems ["mlieko", "chlieb", "syr"] == ["1. mlieko", "2. chlieb", "3. syr"]
Riešenie
numberItems :: [String] -> [String]
numberItems items = zipWith format [1..] items
  where
    format i s = show i ++ ". " ++ s

[1..] je nekonečný, ale zipWith skončí pri kratšom zozname, takže to nevadí. format má dva parametre, lebo zipWith podáva prvky z oboch zoznamov.

Úloha 3.7 – pozície prvku

Vráť indexy (od 0), na ktorých sa prvok nachádza. Pomôcka: zip [0..] xs, potom filter a map fst.

positions :: Eq a => a -> [a] -> [Int]

positions 'a' "banana" == [1,3,5]
positions 7 [1,2,3] == []
Riešenie
positions :: Eq a => a -> [a] -> [Int]
positions x xs = map fst (filter matches (zip [0..] xs))
  where
    matches (_, y) = y == x

-- množinovou abstrakciou
positions' x xs = [i | (i, y) <- zip [0..] xs, y == x]

zip [0..] "banana" dá [(0,'b'),(1,'a'),...]. Necháme dvojice so správnym znakom a z každej vezmeme index.

Úloha 3.8 – každý n-tý prvok

everyNth :: Int -> [a] -> [a]

everyNth 3 [1..10] == [3,6,9]
everyNth 2 "abcdef" == "bdf"
Riešenie
everyNth :: Int -> [a] -> [a]
everyNth n xs = map snd (filter isNth (zip [1..] xs))
  where
    isNth (i, _) = i `mod` n == 0

Rovnaký trik ako 3.7, len filtrujeme podľa indexu (číslujeme od 1) a ponecháme prvok.

Úloha 3.9 – najlepší študent

Vráť meno študenta s najvyšším počtom bodov (pri zhode prvého). Vo where definuj maxPoints (pomocou map snd a maximum) a predikát isBest.

bestStudent :: [(String, Int)] -> String

bestStudent [("Eva",72), ("Adam",43), ("Mia",88), ("John",88)] == "Mia"
Riešenie
bestStudent :: [(String, Int)] -> String
bestStudent xs = fst (head (filter isBest xs))
  where
    maxPoints     = maximum (map snd xs)
    isBest (_, p) = p == maxPoints

Dva kroky: zistíme najvyšší počet bodov, potom nájdeme prvého študenta s týmto počtom. filter zachová poradie, takže head vráti prvého pri zhode.

Úloha 3.10 – Pascalov trojuholník

Vráť n-tý riadok Pascalovho trojuholníka (od 0). Ďalší riadok vznikne sčítaním riadku posunutého doľava a doprava: zipWith (+) (0 : riadok) (riadok ++ [0]). Výpočet ďalšieho riadku daj do nextRow vo where a riadky počítaj rekurzívne.

pascalRow :: Int -> [Integer]

pascalRow 0 == [1]
pascalRow 4 == [1,4,6,4,1]

Rozšírenie: pascal :: Int -> [[Integer]] vráti prvých n riadkov.

Riešenie
pascalRow :: Int -> [Integer]
pascalRow 0 = [1]
pascalRow n = nextRow (pascalRow (n - 1))
  where
    nextRow row = zipWith (+) (0 : row) (row ++ [0])

pascal :: Int -> [[Integer]]
pascal n = map pascalRow [0 .. n - 1]

Pre riadok [1,3,3,1]: [0,1,3,3,1] + [1,3,3,1,0] = [1,4,6,4,1]. Každé číslo je súčet dvoch nad ním.

Úroveň 3F – foldr, foldl a množinové abstrakcie

Cieľ: prepísať rekurzívne vzory na foldr a foldl a vyberať prvky pomocou množinových abstrakcií. Krokovú funkciu foldu vždy pomenuj vo where (napr. step). Ako foldy počítajú, nájdeš v ťaháku vyššie.

Úloha 3F.1 – listOr dvoma spôsobmi

Vráť True, ak je aspoň jedna hodnota True. Najprv rekurziou, potom cez foldr.

listOr :: [Bool] -> Bool

listOr [False, True, False] == True
listOr [] == False
Riešenie
listOr :: [Bool] -> Bool
listOr []     = False
listOr (x:xs) = x || listOr xs

listOr' :: [Bool] -> Bool
listOr' xs = foldr (||) False xs

Porovnaj rekurziu so vzorom foldr: [] → False je počiatočná hodnota, x || ... je operácia. Vďaka lenivému || sa pri prvom True zvyšok nespracuje.

Úloha 3F.2 – súčet a súčin

Pomocou foldr (nie sum ani product).

mySum :: [Int] -> Int
myProduct :: [Int] -> Int

mySum [1,2,3,4] == 10
myProduct [1,2,3,4] == 24

Otázka: akú počiatočnú hodnotu musí mať myProduct a prečo?

Riešenie
mySum :: [Int] -> Int
mySum xs = foldr (+) 0 xs

myProduct :: [Int] -> Int
myProduct xs = foldr (*) 1 xs

Počiatočná hodnota musí byť neutrálny prvok operácie: pre + je to 0, pre * je to 1. S 0 by myProduct vrátil vždy 0.

Úloha 3F.3 – map a filter cez foldr

Kroková funkcia dostane prvok a už spracovaný zvyšok zoznamu.

myMap :: (a -> b) -> [a] -> [b]
myFilter :: (a -> Bool) -> [a] -> [a]

myMap (*2) [1,2,3] == [2,4,6]
myFilter even [1..6] == [2,4,6]
Riešenie
myMap :: (a -> b) -> [a] -> [b]
myMap f xs = foldr step [] xs
  where
    step x acc = f x : acc

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter p xs = foldr step [] xs
  where
    step x acc
      | p x       = x : acc
      | otherwise = acc

acc je už spracovaný zvyšok zoznamu. myMap doň pridá upravený prvok, myFilter prvok pridá alebo vynechá.

Úloha 3F.4 – dĺžka a otočenie cez foldl

myLengthL :: [a] -> Int
myReverseL :: [a] -> [a]

myLengthL "haskell" == 7
myReverseL [1,2,3] == [3,2,1]

Rozpíš si na papier krok za krokom myReverseL [1,2,3] ako v ťaháku.

Riešenie
myLengthL :: [a] -> Int
myLengthL xs = foldl step 0 xs
  where
    step acc _ = acc + 1

myReverseL :: [a] -> [a]
myReverseL xs = foldl step [] xs
  where
    step acc x = x : acc
myReverseL [1,2,3]
= foldl step [] [1,2,3]
= foldl step [1] [2,3]
= foldl step [2,1] [3]
= foldl step [3,2,1] []
= [3,2,1]

Pri foldl je akumulátor prvý parameter krokovej funkcie. Je to presne go s akumulátorom z úlohy 2.4.

Úloha 3F.5 – číslice na číslo

Zo zoznamu číslic poskladaj číslo. Pomocou foldl: akumulátor sa v každom kroku vynásobí 10 a pripočíta sa číslica.

digitsToNumber :: [Int] -> Int

digitsToNumber [1,2,3] == 123
digitsToNumber [] == 0

Kontrola: digitsToNumber (digits 4071) == 4071 (digits z úlohy 2.6).

Riešenie
digitsToNumber :: [Int] -> Int
digitsToNumber ds = foldl step 0 ds
  where
    step acc d = acc * 10 + d

((0 * 10 + 1) * 10 + 2) * 10 + 3 = 123. foldl sa sem hodí, lebo číslice spracúvame zľava, rovnako ako ich čítame.

Úloha 3F.6 – počet prvkov spĺňajúcich podmienku

Pomocou foldr a krokovej funkcie vo where.

countIf :: (a -> Bool) -> [a] -> Int

countIf even [1,2,3,4,6] == 3
countIf (== 'a') "banana" == 3
Riešenie
countIf :: (a -> Bool) -> [a] -> Int
countIf p xs = foldr step 0 xs
  where
    step x acc
      | p x       = acc + 1
      | otherwise = acc

Rovnaká kostra ako myFilter, len namiesto zoznamu akumulujeme číslo.

Úloha 3F.7 – elem cez foldr a lenivosť

myElem :: Eq a => a -> [a] -> Bool

myElem 3 [1,2,3,4] == True
myElem 9 [1,2,3] == False
myElem 3 [1..] == True

Posledný príklad je nekonečný zoznam. Skús, či funguje s foldr a či s foldl – a vysvetli rozdiel.

Riešenie
myElem :: Eq a => a -> [a] -> Bool
myElem y xs = foldr step False xs
  where
    step x acc = x == y || acc

foldr dá krokovej funkcii zvyšok ako ešte nevypočítaný acc. Keď x == y, || sa na acc vôbec nepozrie, takže výpočet skončí aj na nekonečnom zozname. foldl musí najprv prejsť až na koniec zoznamu, aby postavil výraz – na [1..] sa preto zacyklí.

Úloha 3F.8 – compress cez foldr

Úloha z cvičenia 2, tentoraz bez explicitnej rekurzie. Kroková funkcia porovná prvok so začiatkom už spracovaného zvyšku.

compressF :: Eq a => [a] -> [a]

compressF "aaabbbccdaa" == "abcda"
compressF [1,1,2,2,2,1] == [1,2,1]
Riešenie
compressF :: Eq a => [a] -> [a]
compressF xs = foldr step [] xs
  where
    step x [] = [x]
    step x (y:ys)
      | x == y    = y : ys
      | otherwise = x : y : ys

foldr ide sprava, takže step vidí už skomprimovaný zvyšok. Ak sa jeho začiatok rovná x, x nepridáme. Vzory sa dajú použiť aj na akumulátor.

Úloha 3F.9 – priemer jedným prechodom

Pomocou jedného foldl vypočítaj naraz súčet aj počet prvkov (akumulátor je dvojica). Priemer potom vypočítaj vo where.

sumCount :: [Int] -> (Int, Int)
averageF :: [Int] -> Int

sumCount [2,4,6] == (12, 3)
averageF [2,4,6] == 4
Riešenie
sumCount :: [Int] -> (Int, Int)
sumCount xs = foldl step (0, 0) xs
  where
    step (s, c) x = (s + x, c + 1)

averageF :: [Int] -> Int
averageF xs = s `div` c
  where
    (s, c) = sumCount xs

Akumulátor môže byť aj dvojica – nesie dve hodnoty naraz. Vo where sa dá dvojica rovno rozložiť: (s, c) = sumCount xs pomenuje obe zložky.

Úloha 3F.10 – samohlásky

Pomocou množinovej abstrakcie a elem.

vowelCount :: String -> Int

vowelCount "functional programming" == 7
Riešenie
vowelCount :: String -> Int
vowelCount s = length [c | c <- s, c `elem` "aeiou"]

Abstrakcia vyberie len samohlásky, length ich spočíta. Výraz pred | je len c, prvky sa nemenia.

Úloha 3F.11 – násobilka

Vnorená množinová abstrakcia: pre každý riadok i zoznam i*j.

multTable :: Int -> [[Int]]

multTable 3 == [[1,2,3], [2,4,6], [3,6,9]]
Riešenie
multTable :: Int -> [[Int]]
multTable n = [[i * j | j <- [1..n]] | i <- [1..n]]

Vonkajšia abstrakcia vytvára riadky (pre každé i), vnútorná stĺpce (pre každé j). Výsledok je zoznam zoznamov.

Úloha 3F.12 – dokonalé čísla

Číslo je dokonalé, ak sa rovná súčtu svojich deliteľov menších ako ono samo (6 = 1 + 2 + 3). Deliteľov vypočítaj množinovou abstrakciou vo where.

perfectNumbers :: Int -> [Int]

perfectNumbers 500 == [6, 28, 496]
Riešenie
perfectNumbers :: Int -> [Int]
perfectNumbers n = [k | k <- [1..n], isPerfect k]
  where
    isPerfect k      = sum (properDivisors k) == k
    properDivisors k = [d | d <- [1 .. k - 1], k `mod` d == 0]

Rozdelené na tri vrstvy: delitele čísla → test dokonalosti → výber z rozsahu. Každá je jeden riadok a dá sa samostatne vyskúšať.

Úloha 3F.13 – pytagorejské trojice

Všetky trojice (a, b, c) s a <= b <= c <= n, pre ktoré platí a^2 + b^2 == c^2. Použi tri generátory <- v jednej abstrakcii.

pythagorean :: Int -> [(Int, Int, Int)]

pythagorean 15 == [(3,4,5), (5,12,13), (6,8,10), (9,12,15)]
Riešenie
pythagorean :: Int -> [(Int, Int, Int)]
pythagorean n =
  [(a, b, c) | a <- [1..n], b <- [a..n], c <- [b..n], a^2 + b^2 == c^2]

Neskoršie generátory môžu použiť premenné z predchádzajúcich: b <- [a..n] zaistí a <= b, takže nevzniknú duplicity typu (4,3,5).

Úloha 3F.14 – to isté tromi spôsobmi

Vyber zo zoznamu čísla deliteľné 3 a umocni ich na druhú. Napíš tri verzie: rekurziou, cez map a filter, a množinovou abstrakciou. Nakoniec štvrtú cez foldr.

squaresDiv3 :: [Int] -> [Int]

squaresDiv3 [1..10] == [9, 36, 81]
Riešenie
-- 1. rekurzia
squaresDiv3 :: [Int] -> [Int]
squaresDiv3 [] = []
squaresDiv3 (x:xs)
  | x `mod` 3 == 0 = x * x : squaresDiv3 xs
  | otherwise      = squaresDiv3 xs

-- 2. map a filter
squaresDiv3' xs = map square (filter div3 xs)
  where
    square x = x * x
    div3 x   = x `mod` 3 == 0

-- 3. množinová abstrakcia
squaresDiv3'' xs = [x * x | x <- xs, x `mod` 3 == 0]

-- 4. foldr
squaresDiv3''' xs = foldr step [] xs
  where
    step x acc
      | x `mod` 3 == 0 = x * x : acc
      | otherwise      = acc

Všetky štyri robia to isté. Všimni si, že rekurzia a foldr majú rovnakú štruktúru – foldr len vytiahne „prejdi zoznam“ von a necháva ti iba krok.

Úroveň 4 – text: lines, unlines, words, unwords

Cieľ: rozložiť text na riadky alebo slová, spracovať ich a znova zložiť. Typický tvar riešenia je unlines (map spracujRiadok (lines text)) so spracujRiadok vo where. Výsledky s viacerými riadkami si pozri cez putStr (funkcia vstup).

Úloha 4.1 – počet slov

countWords :: String -> Int

countWords "  haskell   je  fajn " == 3
Riešenie
countWords :: String -> Int
countWords s = length (words s)

words sám zahodí nadbytočné medzery, takže stačí spočítať prvky.

Úloha 4.2 – veľké začiatočné písmená

Každému slovu zmeň prvé písmeno na veľké. Vo where definuj capWord so vzormi [] a (c:cs).

capitalize :: String -> String

capitalize "hello functional world" == "Hello Functional World"
Riešenie
import Data.Char (toUpper)

capitalize :: String -> String
capitalize s = unwords (map capWord (words s))
  where
    capWord []     = []
    capWord (c:cs) = toUpper c : cs

Typický tvar: rozlož (words) → uprav každé (map) → zlož (unwords). Lokálna funkcia môže mať viac rovníc so vzormi, rovnako ako funkcia na najvyššej úrovni.

Úloha 4.3 – najdlhšie slovo

Vráť prvé najdlhšie slovo. Vo where definuj ws (slová), maxLen a predikát hasMaxLen.

longestWord :: String -> String

longestWord "the quick brown fox" == "quick"
Riešenie
longestWord :: String -> String
longestWord s = head (filter hasMaxLen ws)
  where
    ws          = words s
    maxLen      = maximum (map length ws)
    hasMaxLen w = length w == maxLen

Pomenovanie ws znamená, že words s napíšeme raz a použijeme na dvoch miestach. Hodnoty vo where môžu používať jedna druhú.

Úloha 4.4 – otočenie slov

Dve funkcie: jedna otočí poradie slov, druhá otočí každé slovo zvlášť.

reverseWords :: String -> String
reverseEachWord :: String -> String

reverseWords "ahoj krasny svet" == "svet krasny ahoj"
reverseEachWord "ahoj svet" == "joha tevs"
Riešenie
reverseWords :: String -> String
reverseWords s = unwords (reverse (words s))

reverseEachWord :: String -> String
reverseEachWord s = unwords (map reverse (words s))

Rozdiel je len v jednom slove: reverse otočí zoznam slov, map reverse otočí každé slovo.

Úloha 4.5 – výskyty slova

Spočítaj, koľkokrát sa slovo nachádza v texte, bez ohľadu na veľkosť písmen. Vo where definuj normalize w = map toLower w.

countOccurrences :: String -> String -> Int

countOccurrences "the" "The cat and the dog" == 2
Riešenie
import Data.Char (toLower)

countOccurrences :: String -> String -> Int
countOccurrences w s = length (filter (== normalize w) (map normalize (words s)))
  where
    normalize x = map toLower x

Obe strany porovnania prevedieme na malé písmená. (== normalize w) je sekcia – funkcia, ktorá porovná svoj argument s hľadaným slovom.

Úloha 4.6 – číslovanie riadkov

Pred každý riadok pridaj jeho číslo. Kombinuj lines, zipWith, [1..] a unlines.

numberLines :: String -> String

numberLines "prvy\ndruhy\ntreti" == "1: prvy\n2: druhy\n3: treti\n"
Riešenie
numberLines :: String -> String
numberLines s = unlines (zipWith format [1..] (lines s))
  where
    format i l = show i ++ ": " ++ l

Rovnaké ako 3.6, len obalené do lines a unlines. unlines pridá \n aj za posledný riadok, preto je v očakávanom výsledku na konci.

Úloha 4.7 – odstránenie prázdnych riadkov

Vyhoď riadky, ktoré sú prázdne alebo obsahujú len medzery. Vo where definuj predikát isBlank.

removeBlankLines :: String -> String

removeBlankLines "a\n\n   \nb\n" == "a\nb\n"
Riešenie
removeBlankLines :: String -> String
removeBlankLines s = unlines (filter notBlank (lines s))
  where
    isBlank l  = all (== ' ') l
    notBlank l = not (isBlank l)

all na prázdnom zozname vráti True, takže isBlank zachytí prázdne riadky aj riadky so samými medzerami jednou podmienkou.

Úloha 4.8 – doplnenie medzerami a tabuľka

Najprv padRight: doplní reťazec medzerami na šírku n (použi replicate). Potom formatTable: každá položka na samostatnom riadku, mená zarovnané na dĺžku najdlhšieho mena, za nimi medzera a počet bodov. Šírku stĺpca vypočítaj vo where.

padRight :: Int -> String -> String
formatTable :: [(String, Int)] -> String

padRight 6 "abc" == "abc   "
formatTable [("Eva",72), ("Adam",43), ("Mia",88)] == "Eva  72\nAdam 43\nMia  88\n"
Riešenie
padRight :: Int -> String -> String
padRight n s = s ++ replicate (n - length s) ' '

formatTable :: [(String, Int)] -> String
formatTable rows = unlines (map formatRow rows)
  where
    width = maximum [length name | (name, _) <- rows]
    formatRow (name, pts) = padRight width name ++ " " ++ show pts

replicate so záporným počtom vráti [], takže padRight nič nepokazí ani pri dlhšom reťazci. width sa vypočíta raz pre celú tabuľku a formatRow ju používa pri každom riadku.

Úloha 4.9 – riadky so slovom

Vráť len tie riadky, ktoré obsahujú zadané slovo (ako celé slovo, nie časť), pred každý daj jeho pôvodné číslo riadku.

grep :: String -> String -> String

grep "fun" "haskell is fun\nfunctions\nfun fun fun" == "1: haskell is fun\n3: fun fun fun\n"

Pomôcka: najprv očísluj všetky riadky (zip [1..] (lines text)), až potom filtruj.

Riešenie
grep :: String -> String -> String
grep w text = unlines (map format (filter hasWord numbered))
  where
    numbered       = zip [1..] (lines text)
    hasWord (_, l) = elem w (words l)
    format (i, l)  = show i ++ ": " ++ l

Číslovanie musí byť pred filtrovaním, inak by sa stratili pôvodné čísla riadkov. elem w (words l) hľadá celé slovo, preto "functions" neprejde.

Úroveň 5 – väčšie úlohy

Cieľ: rozdeliť problém na niekoľko malých funkcií vo where (alebo samostatných funkcií na najvyššej úrovni) a poskladať z nich riešenie. Pred písaním si na papier napíš, aké pomocné funkcie budeš potrebovať a aké majú typy.

Úloha 5.1 – Caesarova šifra

Posuň každé malé písmeno o n miest v abecede (za z pokračuje a), ostatné znaky nechaj tak. Posun jedného znaku daj do shift c vo where. Použi ord, chr, isLower a mod 26. Dešifrovanie je šifrovanie so záporným posunom.

caesar :: Int -> String -> String
uncaesar :: Int -> String -> String

caesar 3 "ahoj, svet" == "dkrm, vyhw"
caesar 1 "xyz" == "yza"
uncaesar 3 (caesar 3 "funkcionalne") == "funkcionalne"
Riešenie
import Data.Char (ord, chr, isLower)

caesar :: Int -> String -> String
caesar n s = map shift s
  where
    shift c
      | isLower c = chr (ord 'a' + (ord c - ord 'a' + n) `mod` 26)
      | otherwise = c

uncaesar :: Int -> String -> String
uncaesar n s = caesar (-n) s

ord c - ord 'a' prevedie písmeno na číslo 0–25, k nemu pripočítame posun, mod 26 zabezpečí pretečenie za z a chr vráti písmeno. V Haskelli mod so zápornými číslami vráti nezáporný výsledok, preto dešifrovanie funguje.

Úloha 5.2 – kódovanie dĺžkou behu

encode zapíše každú skupinu rovnakých znakov ako počet a znak (využi runLength z úlohy 2.9). decode urobí opak (využi concatMap a replicate). Najprv predpokladaj, že počty sú jednociferné.

encode :: String -> String
decode :: String -> String

encode "aaabccdd" == "3a1b2c2d"
decode "3a1b2c2d" == "aaabccdd"
decode (encode "hello") == "hello"

Rozšírenie: viacciferné počty, napr. decode "12a" == "aaaaaaaaaaaa" (pomôže takeWhile isDigit, dropWhile isDigit a read).

Riešenie
import Data.Char (isDigit)

encode :: String -> String
encode s = concatMap format (runLength s)
  where
    format (c, k) = show k ++ [c]

decode :: String -> String
decode []         = []
decode (d:c:rest) = replicate (read [d]) c ++ decode rest

-- rozšírenie: viacciferné počty
decode2 :: String -> String
decode2 [] = []
decode2 s  = replicate (read num) c ++ decode2 rest
  where
    num      = takeWhile isDigit s
    (c:rest) = dropWhile isDigit s

decode vzorom (d:c:rest) zoberie naraz dva znaky – číslicu a písmeno. read [d] prevedie jednoznakový reťazec na číslo (typ Int si Haskell odvodí z replicate). V rozšírení where rozloží zvyšok vzorom (c:rest).

Úloha 5.3 – spracovanie CSV

Každý riadok vstupu obsahuje meno a body z niekoľkých testov oddelené čiarkou. Vytvor správu so súčtom bodov pre každého študenta. Pomocné funkcie vo where:

  • splitOn :: Char -> String -> [String] – rozdelí reťazec podľa znaku (napíš rekurzívne alebo cez takeWhile/dropWhile),
  • parseLine – z riadku vyrobí dvojicu (meno, súčet), čísla preveď cez read,
  • formatLine – z dvojice vyrobí riadok výstupu.
csvReport :: String -> String

csvReport "Eva,10,20,5\nAdam,7,8,9\nMia,15,15,15" == "Eva: 35\nAdam: 24\nMia: 45\n"

Rozšírenie: na koniec správy pridaj riadok Najlepsi: Mia (využi myšlienku z úlohy 3.9).

Riešenie
csvReport :: String -> String
csvReport input = unlines (map formatLine (map parseLine (lines input)))
  where
    splitOn :: Char -> String -> [String]
    splitOn _ [] = [""]
    splitOn sep (c:cs)
      | c == sep  = "" : rest
      | otherwise = (c : head rest) : tail rest
      where
        rest = splitOn sep cs

    parseLine line = (name, sum (map read nums))
      where
        (name : nums) = splitOn ',' line

    formatLine (name, total) = name ++ ": " ++ show total

splitOn spracuje najprv zvyšok reťazca; ak je znak oddeľovač, začne nový kus "", inak znak prilepí na začiatok prvého kusu. Lokálne funkcie môžu mať vlastné where (vnorené odsadenie) aj vlastnú typovú signatúru. V parseLine rozloží vzor (name : nums) výsledok na meno a zoznam čísel.

Úloha 5.4 – matice ako zoznamy zoznamov

Matica je [[Int]], kde každý vnútorný zoznam je riadok.

  • transpose' – rekurzívne: prvý riadok výsledku je map head, zvyšok je transpozícia map tail. Zastav, keď sú riadky prázdne.
  • matrixAdd – vnorené zipWith.
  • matrixMul – prvok výsledku je skalárny súčin riadku prvej matice a stĺpca druhej (využi dotProduct z úlohy 3.3 a transpose').
transpose' :: [[a]] -> [[a]]
matrixAdd :: [[Int]] -> [[Int]] -> [[Int]]
matrixMul :: [[Int]] -> [[Int]] -> [[Int]]

transpose' [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
matrixAdd [[1,2],[3,4]] [[10,20],[30,40]] == [[11,22],[33,44]]
matrixMul [[1,2],[3,4]] [[5,6],[7,8]] == [[19,22],[43,50]]
Riešenie
transpose' :: [[a]] -> [[a]]
transpose' []       = []
transpose' ([] : _) = []
transpose' rows     = map head rows : transpose' (map tail rows)

matrixAdd :: [[Int]] -> [[Int]] -> [[Int]]
matrixAdd a b = zipWith (zipWith (+)) a b

matrixMul :: [[Int]] -> [[Int]] -> [[Int]]
matrixMul a b = [[dotProduct row col | col <- cols] | row <- a]
  where
    cols = transpose' b

map head vezme prvý stĺpec, map tail zvyšok matice. Vonkajší zipWith páruje riadky, vnútorný zipWith (+) prvky v nich. Pri násobení transponujeme b, aby sme mali stĺpce ako zoznamy a mohli použiť dotProduct.

Úloha 5.5 – pokladničný bloček

Položka nákupu je trojica (názov, množstvo, cena za kus). Vytvor bloček: jeden riadok na položku a nakoniec celková suma. Vo where definuj itemTotal, formatItem a total. Na prevod Int na Double použi fromIntegral.

receipt :: [(String, Int, Double)] -> String

receipt [("chlieb",2,1.5), ("mlieko",3,0.5), ("syr",1,4.25)]
  == "chlieb x2 = 3.0\nmlieko x3 = 1.5\nsyr x1 = 4.25\nSpolu: 8.75\n"
Riešenie
receipt :: [(String, Int, Double)] -> String
receipt items = unlines (map formatItem items ++ ["Spolu: " ++ show total])
  where
    itemTotal (_, q, p) = fromIntegral q * p
    formatItem (name, q, p) =
      name ++ " x" ++ show q ++ " = " ++ show (itemTotal (name, q, p))
    total = sum (map itemTotal items)

fromIntegral je potrebný, lebo Int a Double sa v Haskelli nedajú priamo násobiť. Riadok so súčtom prilepíme na koniec zoznamu riadkov cez ++ ešte pred unlines.

Úloha 5.6 – oddeľovanie tisícov

Zapíš nezáporné číslo s medzerou po každých troch cifrách sprava. Postup: show, reverse, rozdelenie na trojice (vlastná rekurzívna funkcia chunks vo where, využi take a drop), otočenie späť a spojenie.

formatThousands :: Int -> String

formatThousands 1234567 == "1 234 567"
formatThousands 999 == "999"
formatThousands 1000 == "1 000"

Rozšírenie: podpora záporných čísel, formatThousands (-45000) == "-45 000".

Riešenie
formatThousands :: Int -> String
formatThousands n = reverse (unwords (chunks (reverse (show n))))
  where
    chunks [] = []
    chunks s  = take 3 s : chunks (drop 3 s)

formatThousands' :: Int -> String
formatThousands' n
  | n < 0     = '-' : formatThousands (abs n)
  | otherwise = formatThousands n

"1234567" → otočené "7654321" → trojice ["765","432","1"] → "765 432 1" → otočené "1 234 567". Otáčame preto, lebo trojice sa počítajú sprava.

Úloha 5.7 – štatistika textu

Vytvor viacriadkovú správu o texte: počet riadkov, počet slov, počet znakov bez medzier a koncov riadkov, najdlhšie slovo (z úlohy 4.3) a priemernú dĺžku slova (celočíselne, div). Každý údaj vypočítaj vo where pod vlastným menom.

textStats :: String -> String

textStats "haskell je fajn\nlisty su lenive"
  == "Riadky: 2\nSlova: 6\nZnaky: 26\nNajdlhsie: haskell\nPriemer: 4\n"
Riešenie
textStats :: String -> String
textStats s = unlines
  [ "Riadky: "    ++ show (length ls)
  , "Slova: "     ++ show (length ws)
  , "Znaky: "     ++ show chars
  , "Najdlhsie: " ++ longestWord s
  , "Priemer: "   ++ show (chars `div` length ws)
  ]
  where
    ls    = lines s
    ws    = words s
    chars = sum (map length ws)

Počet znakov bez medzier a koncov riadkov je súčet dĺžok slov. Každý údaj je pomenovaný vo where, takže hlavná časť je len zoznam riadkov výstupu.


Top