IB015 – Sbírka úloh
Cvičení 2
2.1 Datové typy
Příklad 2.1.1 Napište rekurzivní funkci divBy3, která celočíselně vydělí zadaný argument
číslem 3 bez použití funkce div.
Příklad 2.1.2 S pomocí interpretru určete typy následujících výrazů a najděte další výrazy
stejného typu.
a) 'a'
b) "ahoj"
c) not
d) (&&)
e) (||)
f) True
Příklad 2.1.3 Nalezněte příklady hodnot následujících typů:
a) Bool
b) Integer
c) Double
d) False
e) ()
f) (Int, Integer)
g) (Integer, Double, Bool)
h) ((), (), ())
Příklad 2.1.4 Určete typy následujících výrazů, zkontrolujte si řešení pomocí interpretu.
a) True
b) "True"
c) not True
d) True || False
e) True && "1"
f) f 1, kde funkce f je definovaná jako
f :: Integer -> Integer
f x = x * x + 2
g) f 3.14, kde f je definovaná stejně jako v části f
h) g 3 8, kde g je definovaná jako
g :: Int -> Int -> Int
g x y = x * y - 6
Příklad 2.1.5 Odstraňte všechny nadbytečné (implicitní) závorky z následujících typů:
1
IB015 – Sbírka úloh
a) (a -> (b -> c)) -> ((a -> b) -> (a -> c))
b) (a -> a) -> ((a -> (b -> (a, b)) -> (b -> a)) -> b)
Příklad 2.1.6 Jaký nejobecnejší typ může funkce f mít, aby byla funkce g korektně otypo-
vatelná?
g x = x (f x)
Příklad 2.1.7 Je možné unifikovat typ zadané funkce s daným typem?
a) id, a -> b -> a
b) const, (a -> b) -> a
c) const, (a -> b) -> c
d) map, a -> b -> c -> d -> e
Nezapomeňte, že funkce je nutno otypovat čerstvými typovými proměnnými.
2.2 Funkce na seznamech
Příklad 2.2.1 Rozhodněte, které z následujících seznamů jsou správně utvořené. U nesprávných
rozhodněte proč, u správně utvořených určete typ. Konzultujte své řešení s interpretrem.
a) [1, 2, 3]
b) (1:2):3:[]
c) 1:2:3:[]
d) 1:(2:(3:[]))
e) [1, 'a', 2]
f) [ [], [1, 2], 1:[] ]
g) [ 1, [1, 2], 1:[] ]
h) []:[]
Příklad 2.2.2 Určete typy seznamů:
a) ["a", "b", "c"]
b) ['a', 'b', 'c']
c) "abc"
d) [(True, ()), (False, ())]
e) [(++) "abc" "def", "X" ++ "Y" ++ "Z"]
f) [(&&), (||)]
g) []
h) [[]]
i) [[], [""]]
Příklad 2.2.3 Napište funkci filterList :: a -> [a] -> [a], která ze seznamu odstraní
všechny výskyty prvku zadaného prvním argumentem (nepoužívejte fce map, filter).
2
IB015 – Sbírka úloh
Příklad 2.2.4 Definujte funkce myHead :: [a] -> a (která vrátí první prvek seznamu) a
myTail :: [a] -> [a] (která vrátí seznam bez prvního prvku). Nepoužívejte knihovní funkce
head, tail.
Příklad 2.2.5 Pro následující vzory a seznamy určete, které vzory mohou reprezentovat které
seznamy. Stanovte, jak se navážou proměnné ze vzoru.
vzory:
[], x, [x], [x,y], (x:s), (x:y:s), [x:s], ((x:y):s)
seznamy:
[1], [1,2], [1,2,3], [[]], [[1]], [[1],[2,3]]
Příklad 2.2.6 Napište následující rekurzivní funkce za pomoci vzorů:
a) oddLength :: [a] -> Bool, která vrátí True, pokud je seznam liché délky, jinak False
(pomocí vzorů, bez použití funkce length).
b) listSum :: [Int] -> Int, která dostane seznam čísel a vrátí součet všech jeho prvků.
c) deleteElem :: Eq a => a -> [a] -> [a], která ze seznamu odstraní všechny výskyty
prvku zadaného prvním argumentem (nepoužívejte funkce map, filter).
d) listsEqual :: Eq a => [a] -> [a] -> Bool, která dostane na vstup dva seznamy a
vrátí True právě tehdy, když se rovnají (bez použití funkce == na celé seznamy).
Příklad 2.2.7 Definujte funkci getLast :: [a] -> a, která vrátí poslední prvek neprázdného
seznamu. Nesmíte použít funkci last.
Příklad 2.2.8 Definujte funkci stripLast :: [a] -> [a], která pro neprázdný seznam vrátí
tentýž seznam bez posledního prvku. Nesmíte použít funkci init.
Příklad 2.2.9 Pomocí rekurze napište funkci elem' :: Eq a => a -> [a] -> Bool, která
vrací True, pokud je první argument obsažen v seznamu zadaném druhým argumentem, jinak
vrací False.
Příklad 2.2.10 Pomocí funkce init definujte funkci median, která vrátí medián konečného
uspořádaného neprázdného seznamu. Medián seznamu je jeho v pořadí prostřední prvek. Pro
seznam se sudým počtem prvků vraťte levý z dvojice ve středu.
Příklad 2.2.11 Definujte funkci len :: [a] -> Integer, která spočítá délku seznamu. Nesmíte
použít funkci length.
Příklad 2.2.12 Napište funkci doubles, která bere ze seznamu po dvou prvcích a vytváří
seznam uspořádaných dvojic. Pokud má seznam lichý počet prvků, poslední prvek se zahodí.
doubles [1,2,3,4,5] = [(1,2), (3,4)]
doubles [0,1,2,3] = [(0,1), (2,3)]
Příklad 2.2.13 Definujte rekurzivní funkci add1 :: [Integer] -> [Integer], která vrátí
seznam, v němž je každý prvek o 1 větší než ve vstupním seznamu.
3
IB015 – Sbírka úloh
Příklad 2.2.14 Definujte rekurzivní funkci multiplyN :: Integer -> [Integer] -> [Integer],
která vrátí seznam, v němž je každý prvek v druhém seznamovém parametru vynásoben číslem,
které je prvním parametrem funkce.
Příklad 2.2.15 Definujte funkci sums :: [[Int]] -> [Int], která ze seznamu seznamů čísel
získá seznam součtů vnitřních seznamů. Funkci zadefinujte bez použití knihovních funkcí map
a sum. Příklad použití funkce:
sums [[1,2,3], [0,1,0], [100], []] ∗
[6, 1, 100, 0]
Příklad 2.2.16 Definujte rekurzivní funkci applyToList :: (a -> b) -> [a] -> [b], která
vezme funkci a seznam, a aplikuje danou funkci na každý prvek seznamu.
Příklad 2.2.17 Definujte funkce add1 a multiplyN znovu a co nejkratším zápisem pomocí
funkce applyToList.
Příklad 2.2.18 Definujte funkci evens :: [Integer] -> [Integer], která ze seznamu čísel
vybere jenom sudá.
Příklad 2.2.19 Definujte funkci evens :: [Integer] -> [Integer], která ze seznamu vybere
sudá čísla. Použijte funkci filter.
Příklad 2.2.20 S využitím funkce map a knihovní funkce toUpper :: Char -> Char z modulu
Data.Char (tj. je třeba použít import Data.Char, na začátku souboru, nebo :m + Data.Char
v interpretru) definujte novou funkci toUpperStr, která převádí řetězec písmen na řetězec
velkých písmen, tj. toUpperStr "bob" ∗
"BOB".
Příklad 2.2.21 Definujte funkci multiplyEven :: [Integer] -> [Integer], která vezme
seznam čísel a vrátí seznam, který bude obsahovat všechna sudá čísla původního seznamu
vynásobená 2. Nepoužívejte rekurzi explicitně.
Příklad: multiplyEven [2,3,4] ∗
[4,8], multiplyEven [6,6,3] ∗
[12,12].
Příklad 2.2.22 Definujte funkci sqroots :: [Double] -> [Double], která ze zadaného seznamu
vybere kladná čísla a ta odmocní. (Využijte mimo jiné funkce (>0) a sqrt.)
Příklad 2.2.23 Vymyslete (vzpomeňte si) na další funkce pracující se seznamy, pojmenujte je
v Haskellu nerezervovaným slovem, definujte je a vyzkoušejte svoji definici v interpretru jazyka
Haskell. Můžete se inspirovat například funkcemi zde
http://www.postgresql.org/docs/current/static/functions-string.html.
Příklad 2.2.24 Napište funkci fromend, která dostane přirozené číslo x a seznam, a vrátí
x-tý prvek seznamu od konce. Například fromend 3 [1,2,3,4] se vyhodnotí na 2. Jestli má
seznam méně prvků jako x, funkce skončí s chybovou hláškou.
Příklad 2.2.25 Definujte funkci maxima, která dostane seznam seznamů čísel a vrátí seznam
maximálních prvků jednotlivých seznamů. Například maxima [[5,3],[2,7,13]] se vyhodnotí
na [5,13]. Pomozte si například funkcí maximum, která vrátí největší prvek seznamu.
4
IB015 – Sbírka úloh
Příklad 2.2.26 Napište funkci vowels, která dostane seznam řetězců a vrátí seznam řetězců
takových, že v každém řetězci ponechá jenom samohlásky (ale zachová jejich pořadí). Například
vowels ["ABC","DEF"] se vyhodnotí na ["A","E"].
Příklad 2.2.27 Zadefinujte funkci palindrome, která na vstupu dostane řetězec a rozhodne o
něm, jestli je palindrom. Napište druhou funkci palindromize, která ze zadaného řetězce udělá
palindrom tak, že na jeho konec doplní co nejméně znaků. Například palindrome "abbcb" se
vyhodnotí na False a palindromize "abbcb" se vyhodnotí na "abbcbba".
Příklad 2.2.28 Napište funkci brackets, která vezme řetězec složený ze znaků '(' a ')' a
rozhodne, jestli se jedná o korektní uzávorkování.
Příklad 2.2.29 Napište funkci domino :: (Eq a) => [(a,a)] -> [(a,a)], která nějakým
způsobem vybere prvky ze zadaného seznamu tak, aby měli dvojice ve výsledném seznamu
vedlejší prvky stejné. Není nutné vybrat nejdelší takový podseznam. Příklad:
domino [(1,2), (5,5), (2,5), (5,1), (2,3)] [(1,2), (2,5), (5,1)]
Bonus: Jakým způsobem by šlo najít optimální řešení využívající co nejvíce kostek?
Příklad 2.2.30 Popište, jak se chová následující funkce a pokuste se ji definovat kratším
zápisem a efektivněji.
s2m :: Integer -> [Integer]
s2m 0 = [0]
s2m n = s2m (n - 1) ++ [ last (s2m(n - 1)) + 2 * n - 1 ]
Bonus: Dokažte, že je vaše nová definice ekvivalentní.
2.3 Lokální definice
Příklad 2.3.1 S využitím lokálních definic upravte následující funkci, která z celočíselných
koeficientů kvadratické rovnice spočítá počet reálných kořenů.
numRoots :: Int -> Int -> Int -> Int
numRoots a b c = if b^2 - 4 * a * c < 0
then 0
else if b^2 - 4 * a * c == 0
then 1 else 2
5
IB015 – Sbírka úloh
Řešení
Řešení 2.1.1 Při řešení si třeba dávat pozor na fakt, že vstupem může být i záporné číslo.
Jinak je jen o tom, že celočíselné delění je vlastně počítaní, kolikrát dokážeme opakovaně
odčítat, kým nezastavíme na čísle ≤ 0:
divBy3 0 = 0
divBy3 1 = 0
divBy3 2 = 0
divBy3 n = if n < 0 then - divBy3 (-n) else 1 + divBy3 (n - 3)
Řešení 2.1.2 Použijte příkazu :t k otypování výrazu v ghci (typ [Char] je ekvivalentní
typu String).
Řešení 2.1.3
a) True, False, not False, 3 > 3, "A" == "c", . . .
Obecně libovolný správně utvořený výraz z logických hodnot a logických spojek a mnohé
další.
b) -1, 0, 42, . . .
Libovolné celé číslo.
c) 3.14, 2.0e-21, 2 ** (-4), ale také 1, 42, . . .
Libovolné desetinné číslo, libovolný výraz vracející desetinné číslo, ale také zápis celého
čísla může být interpretován jako typu Double pokud to odpovídá kontextu v němž je
vyhodnocen. V interpretru si můžete ověřit, že je výraz otypovatelný na typ Double
pomocí :t <výraz> :: Double.
d) False není typ! Jedná se o hodnotu typu Bool.
e) (), takzvaná nultice je typem s jedinou hodnotou (někdy také označujeme jako jednotkový
typ, v angličtině unit, v podstatě odpovídá typu void v C). Ačkoli význam takového
typu nemusí zatím dávat v Haskellu smysl, časem se s ním setkáme. Nultice je jediným
základním typem v Haskellu, kde je typ i hodnota zapisována stejným řetězcem znaků v
kódu.
f) (1, 1), (42, 16), (10 - 5, 10 ^ 10000), . . .
Dvojice, první výraz musí být typu Int, druhý typu Integer.
g) (0, 3.14, True), . . . Trojice, složky musí odpovídat typům.
h) ((), (), ()) je jediná možná hodnota trojice jejímž každým prvkem je nultice.
Řešení 2.1.4
a) Bool, výraz je datovým konstruktorem tohoto typu.
b) String (ekvivalentně [Char]), libovolný výraz v dvojitých uvozovkách je v Haskellu typu
String.
c) Bool, při typování musíme nejprve znát typ funkce not :: Bool -> Bool a hodnoty
True :: Bool. Aplikací funkce se signaturou Bool -> Bool na jeden parametr typu Bool
6
IB015 – Sbírka úloh
dostaneme výraz typu Bool. Typ prvního parametru v signatuře funkce musí souhlasit s
typem reálného prvního parametru při aplikaci, což zde platí.
d) Bool, jednotlivé podvýrazy: (||) :: Bool -> Bool -> Bool, True :: Bool, False
:: Bool. Typy reálných parametrů odpovídají parametrům v signatuře operátoru (||).
e) Nesprávně utvořený výraz. Jednotlivé podvýrazy: (&&) :: Bool -> Bool -> Bool, True
:: Bool, "1" :: String. Typ druhého reálného parametru String neodpovídá typu
druhého parametru signatury, Bool. Haskell neprovádí žádné implicitní typové konverze,
proto výraz nelze otypovat
f) Integer, výraz 1 může být typu Integer, a tedy je možné jej dosadit jako parametr
funkce f.
g) Nesprávně utvořený výraz. Výraz 3.14 nemůže být typu Integer, protože se nejedná o
celé číslo, tedy jej nelze dosadit do funkce f.
h) Int, protože funkce bere dva parametry typu Int a Int vrací. 3 i 8 mohou být Int a tedy
lze je dosadit jako parametry.
Řešení 2.1.5
a) (a -> b -> c) -> (a -> b) -> a -> c
b) (a -> a) -> (a -> (b -> (a, b)) -> b -> a) -> b
Řešení 2.1.6 Vidíme, že f i x jsou funkce. Předpokládejme zatím tedy, že x :: a1 -> a2 a
f :: b1 -> b2. Z aplikací ve výrazu vyplývá, že b1 = a1 -> a2 a b2 = a1.
Typ funkce f tedy musí být unifikovatelný s typem (a -> b) -> a.
Řešení 2.1.7
a) Ne, id :: x -> x, vznikne problém a = b -> a (nekonečný typ).
b) Ne, const :: x -> y -> x, problémy a = y -> a -> b a (y -> x) -> b = x (nekonečné
typy).
c) Ano, const :: x -> y -> x, (a -> b) -> y -> a -> b.
d) Ne, map :: (x -> y) -> [x] -> [y], vznikne problém [y] = c -> d -> e (nekompatibilní
typy).
Existuje jednoduchý způsob, jak tuto úlohu řešit v interpretru – ten umožňuje unifikaci libovolného
konečného počtu funkcí a typů. Stačí zadat
:t [undefined :: t1, ..., undefined :: tm, f1, ..., fn]
kde t1 až tm jsou typy a f1 až fn jsou funkce.
Řešení 2.2.1
a) OK, typ [Integer]
b) chybné, (1:2) je chybný výraz, protože 2 není seznam
c) OK, ekvivalentní a
d) OK, ekvivalentní a, c
e) chybné, různé typy prvků: 1 :: Integer ale 'a' :: Char
f) OK, typ [[Integer]]
g) chybné, různé typy prvků: 1 :: Integer ale [1,2] :: [Integer]
7
IB015 – Sbírka úloh
h) OK, typ [[a]]
Řešení 2.2.2 Použijte příkazu :t k otypování výrazu v ghci (typ [Char] je ekvivalentní
typu String).
a) [[Char]] (což je stejné jako [String])
b) [Char] (což je stejné jako String)
c) [Char] (což je stejné jako String)
d) [(Bool, ())]
e) [String], třeba si dát pozor při otypování takovýchto výrazů. Výraz sice obsahuje funkci
++, která má v tomto kontextu typ String -> String -> String, avšak String ->
String -> String není výsledný typ, protože na funkci už byli aplikovány argumenty, a
tedy typ prvků v seznamu je String.
f) [Bool -> Bool -> Bool]
g) [a], z výrazu nevyplývá žádné omezení na typ prvků, který může obsahovat, proto je typ
prvků úplně obecný, tedy a.
h) [[a]], podobně jako v předešlém případě, žádné omezení na typ prvků vnitřního seznamu.
i) [[[Char]]] (což je stejné jako [[String]]), typové omezení vzniká kvůli konkrétní hodnotě
ve druhém prvku (prázdný řetězec).
Řešení 2.2.3
filterList :: a -> [a] -> [a]
filterList _ [] = []
filterList e (x:xs) = if e == x then filterList e xs else x : filterList e xs
Řešení 2.2.4
myHead :: [a] -> a
myHead (x:_) = x
myHead [] = error "myHead: Empty list."
myTail :: [a] -> [a]
myTail (_:xs) = xs
myTail [] = error "myTail: Empty list."
Řešení 2.2.5
• []
Tento vzor představuje prázdný seznam. Nemůže reprezentovat žádný z uvedených se-
znamů.
• x
Libovolná hodnota (a tedy libovolný seznam) se může navázat na tento vzor. Může reprezentovat
všechny uvedené seznamy.
• [x]
Představuje libovolný jednoprvkový seznam. Z uvedených může reprezentovat seznamy
[1], [[]], [[1]].
8
IB015 – Sbírka úloh
• [x,y]
Představuje libovolný dvouprvkový seznam. Z uvedených může reprezentovat seznamy
[1,2], [[1],[2,3]].
• (x:s)
Libovolný neprázdný seznam. Proměnná x reprezentuje první prvek, proměnná s seznam
ostatních prvků. Tento vzor může reprezentovat všechny uvedené seznamy.
• (x:y:s)
Představuje libovolný seznam, který má alespoň 2 prvky. Proměnná x reprezentuje první
prvek, y druhý prvek a s seznam ostatních prvků. Z uvedených může reprezentovat seznamy
[1,2], [1,2,3], [[1],[2,3]].
• [x:s]
Jednoprvkový seznam, kterého jediným prvkem je neprázdný seznam. Proměnná x reprezentuje
první prvek vnitřního seznamu, proměnná s seznam ostatních prvků vnitřního
seznamu. Z uvedených může reprezentovat pouze seznam [[1]].
• ((x:y):s)
Představuje neprázdný seznam, kterého prvním prvkem je neprázdný seznam. Proměnné
x a y reprezentují první prvek prvního prvku a seznam ostatních prvků prvního prvku,
proměnná s reprezentuje ostatní prvky vnějšího seznamu. Z uvedených může reprezentovat
seznamy [[1]], [[1],[2,3]].
Řešení 2.2.6
a) Existují nejméně dva přístupy k řešení, pokud nechceme explicitně pracovat s délkou seznamu.
Jeden z nich je, že využijeme vzoru (x:y:zs), který bere ze seznamu po dvou
prvcích, tím pádem víme, že pokud tak skončíme na jednom prvku, seznam musel obsahovat
lichý počet prvků:
oddLength :: [a] -> Bool
oddLength [] = False
oddLength [_] = True
oddLength (_:_:zs) = oddLength zs
Druhý přístup k řešení je, že odpověď postupně vyskládáme z prázdného seznamu, protože
víme, že ten obsahuje sudý počet prvků. Každým dalším prvkem odpověď změníme na
opačnou,s posledním prvkem získáme odpověď pro celý seznam:
oddLength :: [a] -> Bool
oddLength [] = False
oddLength (_:xs) = not (oddLength xs)
b) sum je jednoduchým příkladem rekurze na seznamech. Stačí vždy vybrat po jednom prvku
a ten sečíst se součtem zvyšku seznamu, který se rekursivně dopočítá tak, že pro prázdný
seznam vrátíme 0:
listSum :: [Int] -> Int
listSum [] = 0
9
IB015 – Sbírka úloh
listSum (x:xs) = x + sum xs
c) deleteElem funguje tak, že rekurzí prohledá každý prvek seznamu a jednoduše odstraní
ten, který se zhoduje se zadaným. Odstranění přitom ve funkcionálním světe chápeme
tak, že v pořadí skopírujeme do výsledného seznamu vše kromě odstraňovaných prvků:
deleteElem :: (Eq a) => a -> [a] -> [a]
deleteElem _ [] = []
deleteElem d (x:xs) = if x == d then xs' else x:xs'
where xs' = deleteElem d xs
d) Nejdůležitejší je tady uvědomit si, že pokud se zadané seznamy opravdu rovnají, nutnou
podmínkou je i to, že musí v rekurzi skončit na stejných hraničných případech. V
listsEqual využijeme dvou k porovnání hodnot mezi o:
listsEqual :: Eq a => [a] -> [a] -> Bool
listsEqual [] [] = True
listsEqual [] _ = False
listsEqual _ [] = False
listsEqual (x:xs) (y:ys) = x == y && listsEqual xs ys
Všimněme si, že na pořadí této definice podle vzoru opravdu záleží. Kdybychom umístnili
hraničný případ pro oba prázdné seznamy například jako předposlední, v druhém
argumentu listsEqual [] _ by mohl vystoupit i prázdný seznam, protože by se ješte
nevyloučil. To by znamenalo, že by naše funkce nefungovala, protože by i při stejných
seznamech odpovědela záporně.
Řešení 2.2.7 Funkci definujeme po částech. Případ prázdného seznamu nemusíme řešit.
Dalším větším seznamem je jednoprvkový seznam a v tomto případě vrátíme rovnou jeho
jediný prvek:
getLast [x] = x
Všechny zbývající případy seznamů mají dva nebo více prvků. Hledaný poslední prvek u nich
získáme tak, že budeme postupně odstraňovat prvky ze začátku seznamu. Tedy ze zadaného
prvku odstraníme první prvek a na zbytek aplikujeme opět funkci getLast:
getLast (x:xs) = getLast xs
Řešení 2.2.8 Funkci definujeme po částech, obdobně jako funkci getLast. Začneme jednoprvkovým
seznamem, kdy výsledkem je prázdný seznam:
stripLast [x] = []
Všechny zbývající případy seznamů mají dva nebo více prvků. V takovém případu bude první
prvek zadaného seznamu určitě ve výsledném seznamu a o zbytku seznamu musíme rozhodnout
rekurzivně:
stripLast (x:xs) = x : stripLast xs
10
IB015 – Sbírka úloh
Srovnejte s definicí funkce getLast.
Řešení 2.2.9
elem' :: a -> [a] -> Bool
elem' _ [] = False
elem' e (x:xs) = e == x || elem' e xs
Řešení 2.2.10
median :: [a] -> a
median [x] = x
median [x, _] = x
median (_:s) = median (init s)
Řešení 2.2.11
len :: [a] -> Integer
len [] = 0
len (_:xs) = 1 + len xs
Výpočet této funkce probíhá například takto:
len (1:(2:[])) 1 + len (2:[]) 1 + (1 + len []) 1 + (1 + 0) ∗
2
Řešení 2.2.12
doubles :: [a] -> [(a,a)]
doubles (x:y:s) = (x,y) : doubles s
doubles _ = []
Řešení 2.2.13
add1 :: [Integer] -> [Integer]
add1 [] = []
add1 (x:xs) = (x + 1) : add1 xs
Řešení 2.2.14
multiplyN :: Integer -> [Integer] -> [Integer]
multiplyN _ [] = []
multiplyN n (x:xs) = (x * n) : multiplyN n xs
Příklad výpočtu:
multiplyN 2 (1:(2:[])) 1 * 2 : multiplyN 2 (2:[])
1 * 2 : (2 * 2 : multiplyN 2 []) 1 * 2 : (2 * 2 : [])
∗
2 : (4 : []) ≡ [2, 4]
Řešení 2.2.15
11
IB015 – Sbírka úloh
sums :: [[Int]] -> [Int]
sums [] = []
sums (x:xs) = singleSum x : sums xs
where singleSum [] = 0
singleSum (x:xs) = x + singleSum xs
Možné je i řešení bez samostatné funkce pro zpracování vnitřních seznamů (i když je trochu
méně přehledné).
sums' :: [[Int]] -> [Int]
sums' [] = []
sums' ([]:xs) = 0 : sums' xs
sums' ([y]:xs) = y : sums' xs
sums' ((y1:y2:ys):xs) = sums' ((y1+y2 : ys) : xs)
Řešení 2.2.16 Inspirujeme se funkcí multiplyN a zobecníme ji na libovolnou funkci. Tím
dostaneme tento předpis:
applyToList :: (a -> b) -> [a] -> [b]
applyToList _ [] = []
applyToList f (x:xs) = f x : applyToList f xs
Řešení 2.2.17
add1 :: [Integer] -> [Integer]
add1 = applyToList (+1)
multiplyN :: Integer -> [Integer] -> [Integer]
multiplyN n = applyToList (*n)
Řešení 2.2.18
evens :: [Integer] -> [Integer]
evens [] = []
evens (x:xs) = if even x then x : evens xs else evens xs
Řešení 2.2.19
evens :: [Integer] -> [Integer]
evens = filter even
Řešení 2.2.20
import Data.Char
toUpperStr :: String -> String
toUpperStr = map toUpper
Řešení 2.2.21
12
IB015 – Sbírka úloh
multiplyEven :: [Integer] -> [Integer]
multiplyEven xs = map (* 2) (filter even xs)
multiplyEven' :: [Integer] -> [Integer]
multiplyEven' = multiplyN 2 . filter even
Fungovalo by složení funkcí v opačném pořadí? Jakým číslem bychom museli násobit?
Řešení 2.2.22
sqroots :: [Double] -> [Double]
sqroots = map sqrt . filter (>0)
Řešení 2.2.24 Jedním z možných řešení je použití funkce reverse a operátora !! na výběr
prvku podle pozice v seznamu (indexuje se od nuly).
fromend :: Int -> [a] -> a
fromend x s = (reverse s) !! (x-1)
Další možností je využití funkce length – jestli je délka seznamu menší než zadaný argument,
funkce skončí s chybovou hláškou, jinak vybereme prvek podle jeho indexu.
fromend' :: Int -> [a] -> a
fromend' x s = if x > len then error "Too short"
else s !! (len - x)
where len = length s
Zkuste se zamyslet, které z uvedených řešení bude mít menší časovou složitost. Je možné napsat
i rychlejší funkci?
Řešení 2.2.25 Využívajíc knihovní funkce map je řešení velmi krátké.
maxima :: [[Int]] -> [Int]
maxima s = map maximum s
Řešení 2.2.26 Nejdřív si zadefinujeme pomocný predikát isvowel, který o znaku určí, jestli
je samohláskou. Následně jednotlivé řetězce projdeme knihovní funkcí filter.
isvowel :: Char -> Bool
isvowel c = elem (toUpper c) "AEIOUY"
vowels :: [String] -> [String]
vowels s = map (filter isvowel) s
Řešení 2.2.27 Funkci, která rozhodne, jestli je řetězec palindromem, zadefinujeme jednoduše
pomocí funkce reverse a porovnání.
palindrome :: String -> Bool
palindrome str = str == reverse str
Po krátkém zamyslení zjistíme, že na doplnění slova na palindrom nám stačí najít část slova,
která tvoří palindrom, a vznikne vynecháním několika prvních písmen. Vynechané znaky pak
doplníme na konec řetězce v obráceném pořadí.
13
IB015 – Sbírka úloh
palindromize :: String -> String
palindromize s = if (palindrome s) then s
else [head s] ++ (palindromize (tail s)) ++ [head s]
Poznámka: Vzhledem k častému využívání sekvenčního spojování seznamů (++) nemá tato
funkce optimální časovou složitost. Zkuste se zamyslet, jak by se dala napsat efektivnější funkce.
Řešení 2.2.28
brackets :: String -> Bool
brackets s = br s 0 where
br [] k = k == 0
br (x:xs) k = if x == '('
then br xs (k + 1)
else if k <= 0 then False else br xs (k - 1)
Řešení 2.2.29 Zadání je poměrně volné a umožňuje mnoho řešení, dokonce i triviální řešení
domino _ = []. Užitečnější řešení může fungovat takto: Ze seznamu nejprve vybereme první
kostku. Pak opakovaně ve zbytku seznamu najdeme první kostku, která bez otáčení sedí k
aktuálnímu konci řetězce, a ostatní nepoužitelné kostky před ní zahazujeme:
domino :: (Eq a) => [(a,a)] -> [(a,a)]
domino ((x,y):(z,w):s) = if y == z then (x,y) : domino ((z,w):s)
else domino ((x,y):s)
domino s = s
Bonus: Algoritmicky lze tuto úlohu přeložit do řeči teorie grafů jako problém nalezení nejdelší
eulerovské cesty v pseudografu (graf s vícenásobnými hranami a smyčkami), kde vrcholy odpovídají
číslům na kostkách a hrany kostkám.
Řešení 2.2.30
s2m n = map (^2) [0..n]
Řešení 2.3.1
numRoots :: Int -> Int -> Int -> Int
numRoots a b c = let dis = b^2 - 4 * a * c in numH dis
where numH 0 = 1
numH d = if d < 0 then 0 else 2
14