IB015 – Sbírka úloh
Cvičení 4
4.1 η-redukce, pointfree vs. pointwise zápis
Příklad 4.1.1 Uvažme funkci negp :: (a -> Bool) -> a -> Bool, která neguje výsledek
unárních predikátů (funkcí typu a -> Bool). Tj. funkce negp vrátí opačnou logickou hodnotu,
než by vrátil zadaný predikát na zadané hodnotě.
a) Definujte funkci negp (můžete využít třeba funkci not).
b) Definujte funkci negp jako unární funkci (s použítím pouze jedného formálního parame-
tru).
c) Definujte funkci negp bez použití formálních parametrů.
Příklad 4.1.2 Následující výrazy použijte v lokální definici a vyhodnoťte v interpretru jazyka
Haskell na vhodných parametrech. Po úspěšné aplikaci výrazy upravujte tak, abyste se při jejich
definici vyhnuli použití λ-abstrakce a formálních parametrů.
a) \x -> 3 * x
b) \x -> x ^ 3
c) \x -> 3 + 60 `div` x ^ 2 > 0
d) \x -> [x]
e) \s -> "<" ++ s ++ ">"
f) \x -> 0 < 35 - 3 * 2 ^ x
g) \x y -> x ^ y
h) \x y -> y ^ x
i) \x y -> 2 * x + y
Příklad 4.1.3 Převeďte následující funkce do pointfree tvaru:
a) \x -> (f . g) x
b) \x -> f . g x
c) \x -> f x . g
Příklad 4.1.4 Převeďte následující výrazy do pointwise tvaru:
a) (^2) . mod 4 . (+1)
b) (+) . sum . take 10
c) map f . flip zip [1, 2, 3] (funkce f je definována externě)
d) (.)
e) flip flip 0
f) (.) (+) . (+)
g) (.(.))
Příklad 4.1.5 Určete typ následujících funkcí. Přepište tyto definice funkcí tak, abyste v jejich
definici nepoužili λ-abstrakci a formální parametry (tj. chce se pointfree definice).
a) f x y = y
1
IB015 – Sbírka úloh
b) h x y = q y . q x
Příklad 4.1.6 Zjistěte, co dělají následující funkce a určete jejich typ:
a) h1 = (.(,)) . (.) . (,)
b) h2 = ((,).) . (,)
Příklad 4.1.7 Určete typ následujících výrazů. Pak je převeďte z pointfree tvaru do pointwise
tvaru (vytvořte z nich λ-funkce s dostatečným množstvím parametrů) a upravte je do co možno
nejčitelnější podoby. Dejte si pozor, aby byl výraz po převodu ekvivalentní původnímu výrazu
(významově i typově).
a) flip const map
b) flip . const map
c) flip const . map
d) flip . const . map
e) flip (.) const map
f) flip const (.) map
g) flip (.) const . map
h) flip . const (.) map
i) flip (.) const (.) map
Příklad 4.1.8 Zapište v pointfree tvaru funkci g x = f x c1 c2 c3 ... cn (f je nějaká
pevně daná funkce a c1, c2, . . . , cn jsou konstanty).
Příklad 4.1.9 Převeďte všechny níže uvedené funkce do pointfree tvaru. Při převodu třetí si
pomozte převodem druhé.
a) f1 x y z = x
b) f2 x y z = y
c) f3 x y z = z
Příklad 4.1.10 Převeďte následující funkce do pointfree tvaru:
a) \x -> f . g x
b) \f -> flip f x
c) \x -> f x 1
d) \x -> f 1 x True
e) \x -> f x 1 2
f) const x
Příklad 4.1.11 Převeďte následující funkce do pointfree tvaru:
a) \x -> 0
b) \x -> zip x x
c) \x -> if x == 1 then 2 else 0
d) \_ -> x
Někde je nutné použít funkce const a dist:
2
IB015 – Sbírka úloh
const :: a -> b -> a
const x y = x
dist :: (a -> b -> c) -> (a -> b) -> a -> c
dist f g x = f x (g x)
4.2 Líné vyhodnocování a práce s nekonečnými seznamy
Příklad 4.2.1 Uvažte význam líného vyhodnocování v následujících výrazech:
a) take 10 [1..]
b) let f = f in fst (2, f)
c) let f [] = 3 in const True (f [1])
d) 0 * div 2 0
e) snd ("a" * 10, id)
Příklad 4.2.2 Definujte funkce cycle a replicate pomocí jednodušších funkcí (lze při tom
použít funkci repeat).
Příklad 4.2.3 Pomocí některé z funkcí iterate, repeat, replicate, cycle vyjádřete nekonečné
seznamy:
a) Seznam sestávající z hodnot True.
b) Rostoucí seznam všech mocnin čísla 2.
c) Rostoucí seznam všech mocnin čísla 3 se sudým exponentem.
d) Rostoucí seznam všech mocnin čísla 3 s lichým exponentem.
e) Alternující seznam -1 a 1: [1,-1,1,-1, ...].
f) Seznam řetězců ["", "*", "**", "***", "****", ...].
g) Seznam zbytků po dělení 4 pro seznam [1..]: [1,2,3,0,1,2,3,0,...].
Příklad 4.2.4 Definujte Fibonacciho posloupnost, tj. seznam čísel [0,1,1,2,3,5,8,13,21,34,...].
Můžete ji definovat jako seznam hodnot (typ [Integer] nebo jako funkci, která vrátí konkrétní
Fibonacciho číslo (Integer -> Integer).
Příklad 4.2.5 Pomocí rekurzivní definice a funkce zipWith vyjádřete Fibonacciho posloup-
nost.
Příklad 4.2.6 Elegantním způsobem zapište nekonečný výraz p = 4
1
− 4
3
+ 4
5
− 4
7
+ . . .
4.3 Intensionální seznamy
Příklad 4.3.1 Pomocí intensionálních seznamů definujte funkci divisors, která k zadanému
přirozenému číslu vrátí seznam jeho kladných dělitelů.
3
IB015 – Sbírka úloh
Příklad 4.3.2 Intensionálním způsobem zapište výrazy, které se chovají stejně jako následující
(předpokládejte externě definované funkce/hodnoty f, p, s, x):
a) map f s
b) filter p s
c) map f (filter p s)
d) repeat x
e) replicate n x
f) filter p (map f s)
Příklad 4.3.3 Je možné zapsat intensionálním způsobem prázdný seznam? Pokud ano, jak,
pokud ne, proč?
Příklad 4.3.4 Intensionálním způsobem zapište následující seznamy nebo funkce:
a) [1,4,9,...,k^2] (pro pevně dané externě definované k)
b) funkci f, která ze seznamu seznamů vybere jenom ty delší než 3 prvky
c) "*****"
d) ["","*","**","***",...]
e) seznam seznamů [[1],[1,2],[1,2,3],...]
f) seznam všech dvojic přirozených čísel (zadefinujte tak, aby se ke každému prvku dalo
dopočítat v konečném čase)
Příklad 4.3.5 Intensionálním způsobem zapište následující seznamy nebo funkce:
a) rostoucí seznam druhých mocnin kladných celých čísel menších než 1000, které po dělení
7 dají zbytek 2
b) [[1],[2,2,2],[3,3,3,3,3],[4,4,4,4,4,4,4],...] (hledejte vztah mezi číslem a počtem
jeho výskytů)
c) ["z","yy","xxx",...,"aaa...aaa"] (znak a se v posledním členu vyskytuje přesně
26krát)
d) následující seznam „2D matic“
[ [[1]],
[[1,1],[1,1]],
[[1,1,1],[1,1,1],[1,1,1]], ... ]
Příklad 4.3.6 Napište funkci, která ze seznamu prvků vygeneruje všechny
a) permutace,
b) variace s opakováním,
c) kombinace.
Výsledný seznam ať je lexikograficky seřazen. Tam, kde je to nutné, můžete předpokládat, že
prvky seznamu jsou různé. Také se můžete v případě potřeby omezit na seznamy s porovnatelnými
prvky (tj. typu Eq a => a).
Příklad 4.3.7 Co dělají následující funkce? Nejdříve určete jejich typy.
a) \s -> [ h:t | h <- head s, t <- tail s]
b) \s -> [ h:t | t <- tail s, h <- head s]
4
IB015 – Sbírka úloh
c) \s -> [ h:t | h <- map head s, t <- map tail s]
d) \s -> [ h:t | t <- tail s, let h = head t]
Příklad 4.3.8 Přepište intensionálně zapsané seznamy pomocí funkcí filter, map, concat,
. . . a opačně.
a) \s -> [ t | t <- replicate 2 s, even t]
b) \s -> map (\m -> (m, m^2)) $ filter isPrime $
map (\x -> 2 * x + 1) $ filter acceptable s
c) concat
d) map (+1) . filter even . concat . filter valid
Příklad 4.3.9 Která z níže uvedených funkcí je časově efektivnější? Proč?
f1 :: [a] -> [a]
f1 s = [ s !! n | n <- [0,2..length s] ]
f2 :: [a] -> [a]
f2 (x:_:s) = x : f2 s
f2 _ = []
Příklad 4.3.10 Uvažujme datový typ matic zapsaných ve formě seznamu seznamů prvků
matice (po řádcích):
type Matrix a = [[a]]
Implementujte tyto funkce:
a) add – sčítá dvě matice
b) transpose – transponuje zadanou matici
c) mult – vynásobí dvě matice
Vždy předpokládejte, že matice jsou zadány korektně (každý podseznam má stejnou délku), a
že u sčítání a násobení mají matice kompatibilní rozměry.
Pokud uznáte za vhodné, můžete použít některou funkci při definici jiné.
5
IB015 – Sbírka úloh
Řešení
Řešení 4.1.1
a) Naším cílem je ze zadané funkce vytvořit negovanou funkci. Z typu funkce negp vidíme,
že ji lze zapsat tak, že uvedeme jak funkční argument, tak argument s hodnotou. Pak jen
výsledek volání f obalíme funkcí not, která realizuje logickou negaci.
negp :: (a -> Bool) -> a -> Bool
negp f x = not (f x)
b) Funkci z předchozího příkladu můžeme přepsat do tvaru složení funkcí:
negp f x = (not . f) x
Odtud můžeme následně odstranit formální argument:
negp f = not . f
K tomuto výsledku můžeme dojít i přímo uvědomíme-li si, že negace predikátu je složením
predikátu s funkcí negace.
Pak lze tělo funkce přepsat do prefixového tvaru:
negp f = (.) not f
A následně lze odstranit poslední formální argument f, čímž dostaneme definici plně bez
formálních argumentů:
negp = (.) not
Poznámka: Z hlediska elegance a čistoty kódu by byla většinou programátorů v Haskellu pravděpodobně
preferována varianta negp f = not . f.
Řešení 4.1.2
a) (\x -> 3 * x) (-4)
\x -> 3 * x
\x -> (*) 3 x
(*) 3
nebo
\x -> 3 * x
\x -> (3*) x
(3*)
Lze si vybrat, jestli použijeme prefixový zápis operátoru nebo operátorovou sekci.
b) (\x -> x ^ 3) 5.1
\x -> x ^ 3
\x -> (^) x 3
\x -> flip (^) 3 x
flip (^) 3
nebo
6
IB015 – Sbírka úloh
\x -> x ^ 3
\x -> (^3) x
(^3)
Opět lze vybrat mezi prefixovým zápisem operátoru pomocí flip nebo operátorovou
sekcí.
c) (\x -> 3 + 60 `div` x ^ 2 > 0) 7
\x -> 3 + 60 `div` x ^ 2 > 0
\x -> (3 + (60 `div` (x ^ 2))) > 0
\x -> (>0) ((3+) (div 60 ((^2) x)))
\x -> ((>0) . (3+) . div 60 . (^2)) x
(>0) . (3+) . div 60 . (^2)
d) (\x -> [x]) [[34]]
\x -> [x]
\x -> x:[]
\x -> (:[]) x
(:[])
nebo
\x -> [x]
\x -> x:[]
\x -> (:) x []
\x -> flip (:) [] x
flip (:) []
e) (\s -> "<" ++ s ++ ">") "boxxy"
\s -> "<" ++ s ++ ">"
\s -> "<" ++ (s ++ ">")
\s -> ("<"++) ((++">") s)
\s -> (("<"++) . (++">")) s
("<"++) . (++">")
Poznamenejme, že funkce (++">") . ("<"++) sice představuje ve výsledku stejnou úpravu,
avšak není správním výsledkem, protože by vznikla uzávorkováním ("<" ++ s) ++ ">",
které ale není korektní z hlediska asociativity (++). Dalším důvodem je, že vyhodnocení
by zabralo jiný počet (více) kroků.
f) (\x -> 0 < 35 - 3 * 2 ^ x) 2.5
\x -> 0 < 35 - 3 * 2 ^ x
\x -> 0 < (35 - (3 * (2 ^ x)))
\x -> (0<) ((35-) ((3*) ((2^) x)))
\x -> ((0<) . (35-) . (3*) . (2^)) x
(0<) . (35-) . (3*) . (2^)
g) (\x y -> x ^ y) 2 2000
\x y -> x ^ y
7
IB015 – Sbírka úloh
\x y -> (^) x y
\x -> (^) x
(^)
h) (\x y -> y ^ x) 2 2000
\x y -> y ^ x
\x y -> (^) y x
\x y -> flip (^) x y
\x -> flip (^) x
flip (^)
Tady bychom mohli postupovat následovně v domnění, že se vyhneme použití flip:
\x y -> y ^ x
\x y -> (^x) y
\x -> (^x)
Avšak teď narazíme na problém, že operátorovou sekci nelze upravit tak, abychom mohli
provést η-redukci. Východiskem z této situace je přepsat (^x) na flip (^) x, čímž se
však dostáváme k prvně uvedenému řešení. Problém s použitím operátorové sekce nenastane,
pokud její operand nebude obsahovat formální argument, který budeme potřebovat
odstranit – tedy lze je bez obav použít třeba u číselných operandů.
i) (\x y -> 2 * x + y) (sin 1000) (sum [1..1000])
\x y -> 2 * x + y
\x y -> (+) (2 * x) y
\x -> (+) (2 * x)
\x -> (+) ((2*) x)
\x -> ((+) . (2*)) x
(+) . (2*)
Ačkoliv poslední výraz vypadá možná nelogicky, vzpomeňte si na to, že při skládání
funkcí považujeme oba argumenty za unární funkce, a tedy (+) bereme jako funkci, která
požaduje jeden číselný argument a vrátí „přičitovací“ funkci.
Řešení 4.1.3
a) \x -> (f . g) x
f . g
b) \x -> f . g x
\x -> (.) f (g x)
\x -> ((.) f . g) x
(.) f . g
c) \x -> f x . g
\x -> (.) (f x) g
\x -> flip (.) g (f x)
\x -> (flip (.) g . f) x
flip (.) g . f
8
IB015 – Sbírka úloh
Řešení 4.1.4
a) (^2) . mod 4 . (+1)
\x -> ((^2) . mod 4 . (+1)) x
\x -> (^2) (mod 4 ((+1) x))
\x -> (mod 4 (x + 1)) ^ 2
b) (+) . sum . take 10
\x -> ((+) . sum . take 10) x
\x -> (+) (sum (take 10 x))
\x y -> (+) (sum (take 10 x)) y
\x y -> sum (take 10 x) + y
c) map f . flip zip [1, 2, 3]
\x -> (map f . flip zip [1, 2, 3]) x
\x -> map f (flip zip [1, 2, 3] x)
\x -> map f (zip x [1, 2, 3])
d) (.)
\f g -> (.) f g
\f g -> f . g
\f g x -> (f . g) x
\f g x -> f (g x)
e) flip flip 0
\f -> flip flip 0 f
\f -> flip f 0
\f x -> flip f 0 x
\f x -> f x 0
f) (.) (+) . (+)
\a -> ((.) (+) . (+)) a
\a -> (.) (+) ((+) a)
\a -> (+) . ((+) a)
\a -> (+) . (+) a
\a b -> ((+) . (+) a) b
\a b -> (+) ((+) a b)
\a b c -> (+) ((+) a b) c
\a b c -> a + b + c
(Závorky v posledním kroku je možno odstranit, protože (+) je asociativní zleva.)
g) (.(.))
\f -> f . (.)
\f g -> (f . (.)) g
\f g -> f ((.) g)
\f g -> f (\h x -> (.) g h x)
\f g -> f (\h x -> g (h x))
Řešení 4.1.5
9
IB015 – Sbírka úloh
a) f :: a -> b -> b
f x y = y
f x y = const y x
f x y = flip const x y
f = flip const
b) V tomto případě si třeba dát pozor na funkci q. Vyskytuje se tady ve dvou různých
výskytech a ty mohou (a také i budou) mít odlišné typy (situace podobná jak u head .
head.
Také pozor na to, že pokud by jste chtěli určit typ v interpretu a upravili by jste si funkci
na \q x y -> q y . q x, nedostanete správný výsledek. To je dáno tím, že zadáním
funkce q jako argumentu vynutíte stejný typ pro všechny její výskyty.
h :: a -> b -> c -> d
Převod na pointfree tvar:
h x y = q y . q x
h x y = (q y) . (q x)
h x y = (.) (q y) (q x)
h x y = flip (.) (q x) (q y)
h x y = (flip (.) (q x)) (q y)
h x y = (flip (.) (q x) . q) y
h x = flip (.) (q x) . q
h x = (flip (.) (q x)) . q
h x = (.q) (flip (.) (q x))
h x = ((.q) . flip (.) . q) x
h = (.q) . flip (.) . q
Řešení 4.1.6
a) Nejsnáze to zjistíme převodem na pointwise tvar, který je přehlednější:
(.(,)) . (.) . (,)
Máme složení funkcí, které vyžaduje argument, takže ho dodáme.
\x -> ((.(,)) . (.) . (,)) x
Rozepíšeme výraz dle definice funkce na nejvyšší úrovni, tedy tečky. Tady lze tuto úpravu
zkrátit a rozepsat obě tečky naráz, tedy (f . g . h) x ≡ f (g (h x)).
\x -> (.(,)) ((.) ((,) x))
Opět rozepíšeme funkci na nejvyšší úrovni, tedy (.(,)) na začátku výrazu.
\x -> ((.) ((,) x)) . (,)
Tečka zas vyžaduje argument – dodáme.
\x y -> (((.) ((,) x)) . (,)) y
A rozepíšeme dle definice tečky.
\x y -> ((.) ((,) x)) ((,) y)
Odstraníme implicitní závorky.
\x y -> (.) ((,) x) ((,) y)
Přepis tečky do infixu.
10
IB015 – Sbírka úloh
\x y -> (,) x . (,) y
Opět tečka a přidání argumentu.
\x y z -> ((,) x . (,) y) z
Rozepsání dle definice tečky.
\x y z -> (,) x ((,) y z)
Přepis do „infixového“ tvaru operátoru na tvorbu uspořádaných dvojic.
\x y z -> (x, (y, z))
Tedy odsud vidíme celkem jasně, co funkce h1 dělá, a také snadno určíme její typ:
h1 :: a -> b -> c -> (a, (b, c))
Alternativně k tomuto postupu je zde možnost označit si v původním zadání skládané
funkce jako f, g, h, což zvýší přehlednost. Pak lze upravovat tento výraz a vždy když
narazíme na potřebu použít některou z těchto funkcí, rozepíšeme ji do původního tvaru.
b) Opět postupujeme podobně:
((,).) . (,)
Tečka vyžaduje argument.
\x -> (((,).) . (,)) x
Odstranění implicitních závorek.
\x -> ((,).) ((,) x)
Rozepsání výrazu na nejvyšší úrovni – operátorové sekce.
\x -> (,) . ((,) x)
Tečka vyžaduje argument – dodáme.
\x y -> ((,) . ((,) x)) y
Rozepíšeme vnitro závorek dle definice tečky.
\x y -> (,) (((,) x) y)
Odstranění implicitních závorek a přepis do přirozeného infixového tvaru.
\x y -> (,) (x, y)
Dodání požadovaného argumentu.
\x y z -> (,) (x, y) z
Přepis do přirozeného infixového tvaru.
\x y z -> ((x, y), z)
Typ je h2 :: a -> b -> c -> ((a, b), c).
Řešení 4.1.7 Typy zadaných výrazů jsou následující:
a) a -> a
b) a -> [b] -> (b -> c) -> [c]
c) (a -> b) -> c -> c
d) (a -> b) -> [a] -> c -> [b]
e) a -> [b] -> [a]
f) (a -> b) -> [a] -> [b]
g) výraz není typově správně utvořen
h) (a -> c) -> b -> (b -> a) -> c
11
IB015 – Sbírka úloh
i) (a -> b) -> a -> (c -> d) -> [c] -> [d]
Po převodu do pointwise tvaru a přepsání funkcí dle definic dostaneme funkce uvedené níže.
Navzdory tomu, že některé vypadají, že by se ještě dali zjednodušit, například podpříklad c),
toto zjednodušení není možné vykonat, protože by nezachovalo typovou ekvivalenci.
a) flip const map
\x -> flip const map x
\x -> const x map
\x -> x
b) flip . const map
\x -> (flip . const map) x
\x -> flip (const map x)
\x y z -> flip (const map x) y z
\x y z -> (const map x) z y
\x y z -> const map x z y
\x y z -> map z y
c) flip const . map
\x -> (flip const . map) x
\x -> flip const (map x)
\x y -> flip const (map x) y
\x y -> const y (map x)
\x y -> const y (\z -> map x z)
Funkci const nelze dále rozepsat dle definice, protože bychom přišli o informaci, že x
musí být funkčního typu.
d) flip . const . map
\x -> (flip . const . map) x
\x -> flip (const (map x))
\x y z -> flip (const (map x)) y z
\x y z -> (const (map x)) z y
\x y z -> const (map x) z y
\x y z -> (map x) y
\x y z -> map x y
e) flip (.) const map
(.) map const
map . const
\x -> (map . const) x
\x -> map (const x)
\x y -> map (const x) y
\x y -> map (\z -> const x z) y
f) flip const (.) map
const map (.)
map
\x y -> map x y
g) flip (.) const . map
\x -> (flip (.) const . map) x
12
IB015 – Sbírka úloh
\x -> flip (.) const (map x)
\x -> (.) (map x) const
\x -> map x . const
\x y -> (map x . const) y
\x y -> map x (const y)
Výraz map x očekává jako argument seznam, avšak const y je funkce. Výraz tedy není
typově správně utvořen.
h) flip . const (.) map
\x -> (flip . const (.) map) x
\x -> flip (const (.) map x)
\x y z -> flip (const (.) map x) y z
\x y z -> (const (.) map x) z y
\x y z -> const (.) map x z y
\x y z -> (.) x z y
\x y z -> x (z y)
i) flip (.) const (.) map
(flip (.) const (.)) map
((.) (.) const) map
(.) (.) const map
(.) (const map)
\x y -> (.) (const map) x y
\x y -> const map (x y)
\x y -> const (\z q -> map z q) (x y)
Opět nelze rozepsat const, jelikož bychom ztratili informaci o tom, že x je funkce a její
první argument má stejný typ jako y.
Řešení 4.1.8 Několikrát po sobě použijeme funkci flip.
g = flip (flip ... (flip (flip f c1) c2) ... cn)
Řešení 4.1.9 Nejdříve vhodným použitím funkcí const a flip zabezpečíme, aby se nám
všechny tři formální argumenty nacházely i na pravé straně všech tří funkcí:
f1 x y z = const (const x y) z
f2 x y z = flip const x (const y z)
f3 x y z = flip const x (flip const y z)
Pak už jenom mechanicky převedeme získané výrazy do pointfree tvaru.
f1 = (.) const . const
f2 = flip (.) const . (.) . flip const
f3 = flip (.) (flip const) . (.) . flip const
Řešení 4.1.10
a) \x -> f . g x
\x -> ((.) f) (g x)
(.) f . g
13
IB015 – Sbírka úloh
b) \f -> flip f x
\f -> flip flip x f
flip flip x
c) \x -> f x 1
\x -> flip f 1 x
flip f 1
d) \x -> f 1 x True
\x -> (f 1) x True
\x -> flip (f 1) True x
flip (f 1) True
e) \x -> f x 1 2
\x -> (f x 1) 2
\x -> (flip f 1 x) 2
\x -> (flip f 1) x 2
\x -> flip (flip f 1) 2 x
flip (flip f 1) 2
f) const x
Parametr x samozřejmě nelze odstranit, protože není vázán λ-abstrakcí.
Řešení 4.1.11
a) \x -> 0
\x -> const 0 x
const 0
b) \x -> zip x x
\x -> zip x (id x)
\x -> dist zip id x
dist zip id
c) Není možno převést, poněvadž if-then-else není klasická funkce, ale syntaktická konstrukce,
podobně jako let-in.
d) \_ -> x
\t -> x
\t -> const x t
const x
Řešení 4.2.1
a) Díky lenosti funkce take se nemusíme podívat na více než prvních deset prvků výrazu
[1..], přičemž každý z nich lze získat v konečném čase. Tedy navzdory nekonečnosti
seznamu [1..] dojde k vyhodnocení zadaného výrazu v konečném čase.
b) Funkce f při pokusu o vyhodnocení cyklí: f ∗
f ∗
f ∗
... Avšak opět, funkce
fst vybere z uvedené dvojice jenom první prvek. Tedy k vyhodnocení f nedojde a celý
výraz bude vyhodnocen v konečném čase.
14
IB015 – Sbírka úloh
c) Funkce f je definována jenom pro prázdný seznam, ale ve výrazu je volána na neprázdném
seznamu. Normálně bychom dostali chybovou zprávu Non-exhaustive patterns
in function f, ale díky lenosti vyhodnocování const nedojde k tomuto volání a vyhodnocení
skončí bez chyby.
d) Výraz div 2 0 sám o sobě vrátí chybu divide by zero. Může se zdát, že tady zafunguje
líné vyhodnocování a 0 * div 2 0 se vyhodnotí na 0, protože první argument je 0.
Obecně v tomto případě to však není pravda, protože u aritmetických operátorů vždy
dochází k vyhodnocení obou operandů. Navíc výraz tohoto typu by v matematice stejně
neměl definovanou hodnotu.
e) Při pokusu o vyhodnocení tohoto výrazu dostaneme typovou chybu. Je potřeba mít na
paměti, že syntaktická a typová analýza výrazu předchází jeho vyhodnocování, a tedy
případný problém tohoto typu je vždy zaznamenán a líné vyhodnocování situaci neza-
chrání.
Řešení 4.2.2
cycle = concat . repeat
replicate n = take n . repeat
Řešení 4.2.3
a) repeat True
cycle [True]
iterate id True
b) iterate (2*) 1
c) iterate (9*) 1
d) iterate (9*) 3
e) iterate ((-1)*) 1
iterate negate 1
cycle [1, -1]
f) iterate ('*':) ""
iterate ("*"++) ""
g) iterate (\x -> (mod (x + 1) 4)) 1
cycle [1,2,3,0]
Řešení 4.2.4 Existuje více řešení. Označíme je postupně fibN.
-- standardni, ale neefektivni definice
fib1 0 = 0
fib1 1 = 1
fib1 n = fib1 (n - 1) + fib1 (n - 2)
-- kompaktnejsi zapis fib1
fib2 n = if n == 0 || n == 1 then n else fib2 (n - 1) + fib2 (n - 2)
-- efektivni seznamova definice
15
IB015 – Sbírka úloh
fib3 = fib' (0, 1)
where fib' (x, y) = x : fib' (y, x + y)
-- efektivni definice funkce s akumulacnim parametrem, odvozena z fib3
fib4 n = fib' n (0, 1)
where fib' 0 (x, y) = x
fib' n (x, y) = fib' (n - 1) (y, x + y)
Různá další řešení lze nalézt na stránce http://www.haskell.org/haskellwiki/The_Fibonacci_
sequence.
Řešení 4.2.5
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Řešení 4.2.6 p = sum (zipWith (/) (iterate negate 4) [1,3..])
Řešení 4.3.1
divisors :: Int -> [Int]
divisors n = [ x | x <- [1..n], mod n x == 0 ]
Řešení 4.3.2
a) [ f x | x <- s ]
b) [ x | x <- s, p x ]
c) [ f x | x <- s, p x ]
d) [ x | _ <- [1..] ]
e) [ x | _ <- [1..n] ]
f) [ x | t <- s, let x = f t, p x ]
[ f x | x <- s, p (f x) ]
Řešení 4.3.3 A proč ne. :) Minimálně příklad s intensionálním zápisem seznamových funkcí
dává několik inspirací. Uveďme některá možná řešení:
[ 0 | _ <- [] ] -- pozor typ Num a => [a]
[ 0 | False ] -- opet typ Num a => [a]
[ undefined | _ <- [] ] -- typ OK: [a]
[ undefined | _ <- [1..10], False ] -- typ OK
Poznámka: fukce undefined :: a je polymorfní konstanta, jejíž vyhodnocení vždy způsobí
chybu (obdobně jako u funkce error).
Také poznamenejme, že tato řešení jsou nesprávná:
a) [ | ] – syntaktická chyba, před i za svislítkem musí být výraz
b) [ | x <- s ] – obdobně jako první příklad a taky s není definováno
c) [ x | ] – obdobně jako první příklad, navíc x není definováno
16
IB015 – Sbírka úloh
Řešení 4.3.4
a) [ x^2 | x <- [1..k] ]
b) [[a]] -> [[a]]
= [ t | t <- s, length t > 3 ]
c) [ '*' | _ <- [1..5] ]
d) [ ['*' | _ <- [1..n]] | n <- [0..] ]
e) [ [1..n] | n <- [1..] ]
f) [ (y,x-y) | x <- [2..], y <- [1..(x-1)] ]
Řešení 4.3.5
a) [ x^2 | x <- [1..999], mod x 7 == 2 ]
b) [ [n | _ <- [1..(2*n-1)]] | n <- [1..] ]
c) [ [c | _ <- [1..k] ] | (k, c) <- zip [1..26] ['z','y'..'a'] ]
d) [ [ [1|_<-[1..n]] | _ <- [1..n]] | n <- [1..] ]
Řešení 4.3.6
a) perm :: Eq a => [a] -> [[a]]
perm [] = [[]]
perm s = [m:n | m <- s, n <- perm (filter (m/=) s)]
b) varrep :: Int -> [a] -> [[a]]
varrep 0 s = [[]]
varrep k s = [m:n | m <- s, n <- varrep (k - 1) s]
c) comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb k s =
[m:t | (m, n) <- zip s . tails . tail $ s, t <- comb (k - 1) n]
where
tails [] = [[]]
tails (x:s) = (x:s) : tails s
Tady lze případně použít funkci tails z modulu Data.List, viz http://hackage.haskell.
org/package/base-4.7.0.1/docs/Data-List.html#v:tails.
Řešení 4.3.7 Všechny funkce jsou typu [[a]] -> [[a]]. Pro jednoduchost označme s =
x:xs.
a) Funkce spáruje všemi způsoby prvky x s prvky xs.
b) Podobně jako a), jenom nejdříve zpracovává prvky xs. Výsledek tedy dostaneme v jiném
pořadí.
c) Funkce spáruje všemi způsoby „hlavy“ prvků s s „chvosty“ prvků s.
d) Funkce vrátí seznamy z xs (kromě prvního) s duplikovanými prvními prvky.
Řešení 4.3.8
a) filter even . replicate 2
17
IB015 – Sbírka úloh
b) \s -> [(t, t^2) | x <- s, acceptable x, let t = 2 * x + 1, isPrime t]
c) \s -> [t | x <- s, t <- x]
d) \s -> [t + 1 | x <- s, valid x, t <- x, even t]
Řešení 4.3.9 Nechť n = length s. Lepší časovou složitost má funkce f2, protože projde
seznamem jenom jednou, tedy celkově v čase O(n). Na druhé straně f1 vykoná nejvíce n/2 + 1
volání funkce (!!). Tyto volání se v tomhle případě vykonají každé v čase O(k), kde k je druhý
argument funkce (!!). Dohromady tedy vyžaduje čas O(n2
).
Řešení 4.3.10
a) add :: Num a => Matrix a -> Matrix a -> Matrix a
add = zipWith (zipWith (+))
b) transpose :: Matrix a -> Matrix a
transpose = foldr (zipWith (:)) (repeat [])
c) mult :: Num a => Matrix a -> Matrix a -> Matrix a
mult m1 m2 = [[sum (zipWith (*) x y) | y <- transpose m2] | x <- m1]
18