Exercises - kamil¶
Useful Files¶
Navigation¶
- Ako s tým pracovať
- Pripomenutie:
where - Ťahák funkcií – čo robia na príkladoch
- Úroveň 1 – základy
where, práca s prvkami zoznamu - Úloha 1.1 – obdĺžnik
- Úloha 1.2 – BMI
- Úloha 1.3 – stred zoznamu
- Úloha 1.4 – výmena krajných prvkov
- Úloha 1.5 – druhé mocniny párnych čísel
- Úloha 1.6 – dlhé slová
- Úloha 1.7 – ceny s DPH
- Úloha 1.8 – je zoznam usporiadaný na koncoch?
- Úroveň 2 – rekurzia a porovnávanie vzorov
- Úloha 2.1 – počet párnych
- Úloha 2.2 – vlastné
takeadrop - Úloha 2.3 – vlastné
zip - Úloha 2.4 –
reverses akumulátorom - Úloha 2.5 – maximum
- Úloha 2.6 – číslice čísla
- Úloha 2.7 – Collatzova postupnosť
- Úloha 2.8 – Fibonacciho čísla
- Úloha 2.9 – skupiny rovnakých prvkov
- Úloha 2.10 – vloženie do usporiadaného zoznamu a triedenie
- Úroveň 3 –
map,filter,concatMap,replicate,zipWith,reverse - Úloha 3.1 – zdvojenie prvkov
- Úloha 3.2 – rozbalenie dvojíc
- Úloha 3.3 – skalárny súčin
- Úloha 3.4 – rozdiely susedov
- Úloha 3.5 – palindróm z textu
- Úloha 3.6 – očíslovanie položiek
- Úloha 3.7 – pozície prvku
- Úloha 3.8 – každý n-tý prvok
- Úloha 3.9 – najlepší študent
- Úloha 3.10 – Pascalov trojuholník
- Úroveň 3F –
foldr,foldla množinové abstrakcie - Úloha 3F.1 –
listOrdvoma spôsobmi - Úloha 3F.2 – súčet a súčin
- Úloha 3F.3 –
mapafiltercezfoldr - Úloha 3F.4 – dĺžka a otočenie cez
foldl - Úloha 3F.5 – číslice na číslo
- Úloha 3F.6 – počet prvkov spĺňajúcich podmienku
- Úloha 3F.7 –
elemcezfoldra lenivosť - Úloha 3F.8 –
compresscezfoldr - Úloha 3F.9 – priemer jedným prechodom
- Úloha 3F.10 – samohlásky
- Úloha 3F.11 – násobilka
- Úloha 3F.12 – dokonalé čísla
- Úloha 3F.13 – pytagorejské trojice
- Úloha 3F.14 – to isté tromi spôsobmi
- Úroveň 4 – text:
lines,unlines,words,unwords - Úloha 4.1 – počet slov
- Úloha 4.2 – veľké začiatočné písmená
- Úloha 4.3 – najdlhšie slovo
- Úloha 4.4 – otočenie slov
- Úloha 4.5 – výskyty slova
- Úloha 4.6 – číslovanie riadkov
- Úloha 4.7 – odstránenie prázdnych riadkov
- Úloha 4.8 – doplnenie medzerami a tabuľka
- Úloha 4.9 – riadky so slovom
- Úroveň 5 – väčšie úlohy
- Úloha 5.1 – Caesarova šifra
- Úloha 5.2 – kódovanie dĺžkou behu
- Úloha 5.3 – spracovanie CSV
- Úloha 5.4 – matice ako zoznamy zoznamov
- Úloha 5.5 – pokladničný bloček
- Úloha 5.6 – oddeľovanie tisícov
- Ú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 cezghci 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 spustiand 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:
Rekurzívna pomocná funkcia s akumulátorom (často sa volá go):
Ť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í:
Poradie argumentov funkcie je opačné – pri foldr je akumulátor vpravo, pri foldl vľavo:
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.
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).
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.
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.
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.
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.
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.
Riešenie
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?
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.
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.
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.
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.
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.
Riešenie
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.
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¶
Riešenie
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.
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¶
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.
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.
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).
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.
Kontrola: digitsToNumber (digits 4071) == 4071 (digits z úlohy 2.6).
Riešenie
((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.
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.
Riešenie
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.
Riešenie
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.
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.
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.
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¶
Riešenie
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).
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.
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.
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.
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.
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 ceztakeWhile/dropWhile),parseLine– z riadku vyrobí dvojicu (meno, súčet), čísla preveď cezread,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 jemap head, zvyšok je transpozíciamap 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židotProductz úlohy 3.3 atranspose').
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.