ULOHY
-------

1. Co robia nasledovne fold* funkcie?
a) foldr (+) 1
b) foldl (&&) True
c) foldl1 const
d) flip (foldr map)
e) not . foldr (||) False . map not

2. Zapiste funkcie pomocou vhodnej akumulacnej funkcie:
a) f. vracajucu zdvojene prvky zoznamu, t.j. f [1,2] ~> [1,1,2,2]
b) f. spajajucu zoznamy v zadanom zozname, t.j.
   f [[1,2,3],[6,5,4],[],[2,3]] ~> [1,2,3,6,5,4,2,3]
c) standardnu funkciu map
d) standardnu funkciu length
e) f. ktora prevedie binarny zapis cisla na dekadicky (najmenej vyznamny bit
   je uvedeny ako posledny), t.j. f [1,0,0] ~> 4

3. V com sa map a zipWith podobaju?

4. Opakovanie: Urcte typy vyrazov (predpokladajte, ze cisla maju typ Int)
a) [(||), (&&)]
b) let { f m = g; g n = 1 } in (f, g)
c) const const
d) map id
e) \a b -> a b
f) \t -> zipWith t [] [10..]
g) [[], [[]]]

5. Ktore z nasledujucich vyrazov su korektne? U korektnych urcte, co robia.
a) putStr "a" >>= putStr
b) getLine >> getLine >> getLine
c) getLine >>= putStr >> getLine >>= \y -> putStr y
d) getLine >> putStr
e) putStr "password: " >> getLine >>=
     \x -> putStr (if x == "1!4S" then "ok" else "err")
f) return "ahoj" >>= head
g) getLine >>= id >>= putStr



 RIESENIA
----------

1.
a) foldr (+) 1 [a0, a1, a2, a3] ~> a0 + (a1 + (a2 + (a3 + 1)))
   funkcia vytvori sucet cisel v zozname zvacseny o 1
b) funkcia vrati True prave vtedy, ked zoznam neobsahuje False, pretoze
   akonahle sa aspon raz vyskytne v logickom sucine False, vysledok uz
   bude nutne False a nic to nezvrati
c) foldl1 const [a0, a1, a2, a3] ~> const (const (a0 a1) a2) a3 ~> a0
   vlastne foldl1 const = head
d) flip (foldr map) [(+2), (2^)] [1..4] ~> foldr map [1..4] [(+2), (2^)] ~>
   map (+2) (map (2^) [1..4]) ~> [4,6,10,18]
   postupne aplikuje na vsetky prvky funkcie zo zadaneho zoznamu
e) \s -> not (foldr (||) False (map not s))
   najprv je vhodne urcit, co robit foldr (||) False
   foldr (||) False [a0, a1, a2] ~> a0 || (a1 || (a2 || False)
   teda je to vlastne logicke alebo viacerych hodnot (True, ak aspon jedna
   zadana hodnota je True), oznacme si funkciu foldr (||) False ako or
   (v skutocnosti takato funkcia existuje a je definovana presne takto);
   potom mame \s -> not (or (map not s)), to vsak znamena, ze mame zoznam
   hodnot, ktore najprv znegujeme, urobime z nich logicky sucet a vysledok
   znegujeme, t.j. f(a0, a1, a2) = (a0' + a1' + a2')'; avsak podla
   De Morganovych zakonov mame, ze (a0' + a1' + a2')' = a0 * a1 * a2, teda
   zadana funkcia je vlastne logicky sucin vsetkych hodnot a mozeme ju
   zapisat aj ako foldr (&&) True, co vlastne definicia vstavanej funkcie and

2. Co je dolezite si uvedomit pri zapisovani funkcii pomocou foldr/foldl je,
   ze ako dva argumenty berie nejaku funkciu a "pociatocnu hodnotu". Pociatocna
   hodnota sa vracia pre prazdny zoznam. Zaujimavejsie to je s funkciou, kde
   vstupuje do hry rekurzia. Nech fun s = foldr f z s. Funkcia f je definovana
   tak, ze vracia hodnotu 'fun s', pricom ako argumenty dostava hodnoty 'head s'
   a fun (tail s), cize hodnotu funkcie fun na chvoste zoznamu s. Prave tu je
   skryta ta rekurzia, a preto sa na taketo priklady netreba pozerat ako
   na nieco nezvladnutelne ale staci vymysliet funkciu, ktora dokaze vyratat
   fun s zo znalosti head s a fun (tail s).

a) foldr (\x s -> x:x:s) []
b) foldr (++) [], tato funkcia je definovana ako concat
c) foldr ((:) . f) [] alebo foldr (\x s -> f x : s) []
d) foldr (+1) 0
e) foldl (\s digit -> 2 * s + digit) 0

3. map f [a0, a1, a2] = [f a0, f a1, f a2]
   zipWith f [a0, a1, a2] [b0, b1, b2] = [f a0 b0, f a1 b1, f a2 b2]

4. Na https://is.muni.cz/auth/cd/1433/podzim2010/IB015/priklpredzk/20663907
   mozete najst ukazku, ako je mozne algoritmickym sposobom urcovat typy
   vyrazov; je to sice niekedy zdlhavejsia metoda, avsak je ju mozne pouzit
   vzdy; co sa este moze hodit, je previest si vyraz pred jeho otypovanim
   do nejakeho vhodnejsieho, pre otypovanie jednoduchsieho tvaru, ak je to mozne
a) [Bool -> Bool -> Bool]
b) g :: a -> Int, odtial f :: b -> (a -> Int) a teda pre typ (f, g) dostavame
   (b -> a -> Int, a -> Int)
c) prve const ma typ a -> b -> a, druhe c -> d -> c; zaroven plati
   a = c -> d -> c, teda dostavame b -> a = b -> (c -> d -> c) a po premenovani
   a odstraneni implicitnych zatvoriek a -> b -> c -> b
d) map :: (a -> b) -> [a] -> [b], id :: c -> c
   ma platit a -> b = c -> c, cize dostavame a = c = b, cize vysledny typ bude
   [a] -> [b] = [a] -> [a]
e) vysledny typ bude typ(a) -> typ(b) -> typ(a b)
   nech b :: t1; na typ b nemame ziadne dalsie obmedzenie; vieme, ze a berie
   ako argument vyraz typu t1 a nieco vracia, cize a :: t1 -> t2; zaroven
   a b :: t2; teda vo vysledku dostavame (t1 -> t2) -> t1 -> t2
f) vysledny typ bude typ(t) -> typ(zipWith ...)
   zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
   [] :: [d]
   [10..] :: [Int]
   t :: e
   musi platit e = a -> b -> c, [d] = [a], [b] = [Int], teda mame
   b = Int, d = a, e = a -> Int -> c, cize vysledny typ (a -> b -> c) -> [c]
   bude (a -> Int -> c) -> [c]
g) mozeme postupne urcit typy prvkov zoznamu: [] :: [a], [[]] :: [[b]], zaroven
   musi platit [a] = [[b]], kedze prvky zoznamu musia mat rovnaky typ;
   najspecifickejsy typ je [[b]] a kedze mame zoznam takychto prvkov, vysledny
   typ bude [[[b]]]

5.
a) nok - putStr "a" :: IO (), teda druhe putStr dostane prostrednictvom (>>=)
   ako argument hodnotu (), avsak putStr vyzaduje argument typu String
b) ok - trikrat nacita od pouzivatela retazec, avsak vzdy ho zahodi; typ celeho
   vyrazu je kvoli (>>) urceny typom poslednej zlozky, t.j. IO String
c) ok - nacita retazec, vypise ho, nacita dalsi a tiez ho vypise
d) nok - nesedi typ druheho argumentu (>>): (>>) ocakava IO b, ale typ
   putStr je a -> IO ()
e) ok - vypise "password: ", nacita retazec a ak nacitalo "1!4S", vypise "ok",
   inak "err"
f) nok - head :: [a] -> a, v tomto pripade [a] = [Char], avsak a musi byt v tvare
   IO b, co [Char] rozhodne nie je
g) nok - nesedi typ druheho vyrazu id; vyraz ma tvar (getLine >>= id) >>= putStr,
   getLine :: IO String, id :: a -> a, (>>=) :: IO c -> (c -> IO d) -> IO d
   IO c = IO String, a -> a = c -> IO d; avsak c = String, teda String = IO d,
   co je chyba, kedze tieto typy nie su kompatibilne