Skip to content

← Späť

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)

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)

Ú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"

Ú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] == []

Ú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"

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

Ú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

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

Ú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ý.

Ú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

Ú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] == []

Ú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')]

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

Ú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

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

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

Ú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 == []

Ú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 "" == []

Ú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"

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

Ú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"

Úloha 3.3 – skalárny súčin

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

dotProduct [1,2,3] [4,5,6] == 32

Ú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 (<=).

Ú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

Ú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"]

Ú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] == []

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

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

everyNth 3 [1..10] == [3,6,9]
everyNth 2 "abcdef" == "bdf"

Ú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"

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

Ú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

Ú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?

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

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

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

Ú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

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

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

Ú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

Úloha 3F.10 – samohlásky

Pomocou množinovej abstrakcie a elem.

vowelCount :: String -> Int

vowelCount "functional programming" == 7

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

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

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

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

Ú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

Ú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"

Ú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"

Ú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"

Ú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

Ú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"

Ú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"

Ú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"

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

Ú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"

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

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

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

Ú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"

Ú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".

Ú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"

Top