Bonusove ulohy z cviceni jaro 2012 ==================================== Priklady su oznacovane podla slajdov, ktore sa preberaju a licheho (L)/ /sudeho (S) tyzdna. CVICENIE 1L ------------- Explicitne vypiste vsetky implicitne zatvorky vyrazu 3 < (max 54) 7 * 11 `min` 8 / f (f g) + sin (g + f g ^ 2) / 41 *** 3 < (((((max 54) 7) * (11 `min` 8)) / (f (f g))) + ((sin (g + ((f g) ^ 2))) / 41)) *** Problematickejsim podvyrazom mohlo byt sin (g + f g ^ 2). Tam sa casto vyskytovali riesenia sin (g + (f (g ^ 2))), co vsak nie je spravne. Vzdy je nutne rozdelovat vyraz podla operatorov. Teda sin (g + (f g ^ 2)) a dalej sin (g + ((f g) ^ 2)). CVICENIE 2S ------------- Napiste funkciu, ktora zo zadaneho zoznamu cisel na jeden priechod vytvori dvojicu, pricom v prvom clene budu vsetky chvosty (v poradi od najdlhsieho) zacinajuce cislom, na ktorom vracia funkcia (dana ako druhy argument) True (na kazdom prvku zoznamu musi byt volana iba raz) a v druhom clene dvojice bude sucet tych cisel, na ktorych funkcia vratila False. Prazdny zoznam vo vysledku nebude sa vo vyslednom zozname nachadzat nebude. Priklad: filip [1,6,4,-2,43] even ~> ([[6,4,-2,43], [4,-2,43], [-2,43]], 1 + 43) *** filip :: [Int] -> (Int -> Bool) -> ([[Int]], Int) filip [] _ = ([], 0) filip (x:s) f = if f x then ((x:s):m, n) else (m, x + n) where (m, n) = filip s f *** Kedze ide o funkciu na zoznamoch, zase je najlepsie pouzit rekurziu. Definicia na prazdnom zozname je celkom jasna. Mozno si akurat dat pozor, aby tam nebolo nieco ako ([[]], 0). V rekurzivnom pripade si treba uvedomit, ze jej podstatou je znalost vysledku pre filip s f. To mozeme zapisat pomocou notacie where, kde si uz rovno rozbalime jej vysledok do dvoch zloziek usporiadanej dvojice - - m, n. Potom to je uz jednoduche. Podla vysledku funkcie f na prvom prvku zoznamu, co je x, vratime bude priretazeny cely zoznam k prvemu clenu - ((x:s):m, n) - alebo pripocitame jeho hodnotu k druhemu - (m, x + n). CVICENIE 2L ------------- Napiste funkciu simulujucu skladanie domina zo zoznamu obsahujuceho dvojice. Funkcia bude mat typ domino :: [(Int, Int)] -> [(Int, Int)]. Vzdy zoberie prvy prvok zoznamu a k nemu pripoji dalsiu nasledujucu dvojicu, s ktorou sa zhoduje, nepouzite prvky medzi nimi zahodi a pokracuje na zvysku. Priklad: domino [(2,5),(5,1),(4,3),(1,4),(2,2),(4,9),(1,3),(5,5)] ~> ----- ----- ----- ----- ~> [(2,5),(5,1),(1,4),(4,9)] *** Prikladom prehladnejsieho riesenia bez snahy minimalizovat pocet definicii pre jednotlive vzory je domino [] = [] domino [x] = [x] domino ((a,b):s) = (a,b) : domino (dropWhile ((/=b) . fst) s) Na prazdnom a jednoprvkovom zozname sa funkcia sprava ako identita. V opacnom pripade sa najde prva dvojica, ktora vyhovuje, vlozi sa do vysledku a pokracuje sa v hladani dalsej dvojice vo zvysku zoznamu. CVICENIE 3S ------------- Napiste funkciu vyuzivajucu datovy typ data Either a b = Left a | Right b, teda napr. Either Int Bool umoznuje ulozit Int (Left 3) alebo Bool (Right True). Funkcia sa bude volat mapEitherL a bude mat typ (a -> c) -> (b -> c) -> [Either a b] -> [c] Bude sa podobat na map a jej ulohou bude aplikovat na prvky zoznamu, kde budu hodnoty typu Either a b, bud funkciu z prveho alebo z druheho argumentu (to sa urci podla datoveho konstruktora Left/Right) a vrati zoznam vysledkov. Priklad: mapEitherL (\t -> 10) (+1) [Left False, Right 10, Left True, Right (-2)] ~> [10, 11, 10, -1] *** mapEitherL _ _ [] = [] mapEitherL f g (Left x : s) = f x : mapEitherL f g s mapEitherL f g (Right x : s) = g x : mapEitherL f g s Pripad prazdneho zoznamu je celkom jasny a nepotrebuje komentovat. V opacnom pripade, ak mame ako argument neprazdny zoznam, je potrebne este rozobrat jeho prvy prvok podla toho, ci je konstruovany pomocou datoveho konstruktora Left alebo Right, a na zaklade toho zvolime funkciu, ktoru aplikujeme. Potom zostava, podobne ako u klasickej funkcie map alebo foldr, aplikovat mapEitherL s takymi istymi argumentami na zvysny zoznam, cize mapEitherL f g s. Domaca bonusova uloha pre 3. cvicenie --------------------------------------- Uvazujte datovy typ Nat z cviceni. Zavedte na nom funkcie - plus - minus - times (nasobenie) - divide (celociselne delenie so zaokruhlovanim nadol) - modulo - power (umocnovanie) Specialne pripady: - ak x < y, minus x y vrati Zero - divide x 0, modulo x 0 vypise chybu pomocou error - power 0 0 vypise chybu pomocou error Mozete si definovat pomocne funkcie, ak ich budete potrebovat. Termin: do 06.04.2012 vratane DOPLNENIE 01.04.2012: Riesenie, kde si cisla najprv prevediete na Int, tam spravite operacie a nasledne prevediete spat na Nat, je trochu prilis lacny trik na to, aby som zan daval body. :) *** U niektorych funkcii som napisal dve mozne riesenia, ale v principe je to vzdy to iste. data Nat = Zero | Succ Nat deriving (Show, Eq) plus1 :: Nat -> Nat -> Nat plus2 :: Nat -> Nat -> Nat minus :: Nat -> Nat -> Nat times :: Nat -> Nat -> Nat power :: Nat -> Nat -> Nat divide1 :: Nat -> Nat -> Nat modulo1 :: Nat -> Nat -> Nat divide2 :: Nat -> Nat -> Nat modulo2 :: Nat -> Nat -> Nat div_mod :: Nat -> Nat -> (Nat, Nat) geq1 :: Nat -> Nat -> Bool geq2 :: Nat -> Nat -> Bool plus1 Zero y = y plus1 (Succ x) y = plus1 x (Succ y) plus2 Zero y = y plus2 (Succ x) y = Succ (plus2 x y) minus Zero _ = Zero minus x Zero = x minus (Succ x) (Succ y) = minus x y times Zero _ = Zero times (Succ x) y = plus1 y (times x y) power Zero Zero = error "zle" power _ Zero = Succ Zero power x (Succ y) = times x (power x y) divide1 _ Zero = error "zle" divide1 x y = if geq1 x y then Succ (divide1 (minus x y) y) else Zero modulo1 _ Zero = error "zle" modulo1 x y = if geq1 x y then modulo1 (minus x y) y else x divide2 x y = fst (div_mod x y) modulo2 x y = snd (div_mod x y) div_mod _ Zero = error "zle" div_mod x y = if geq1 x y then (Succ u, v) else (Zero, x) where (u, v) = div_mod (minus x y) y -- pomocna funkcia >= geq1 x y = minus y x == Zero geq2 _ Zero = True geq2 Zero _ = False geq2 (Succ x) (Succ y) = geq2 x y *** V zadaniach, ktore som dostal, ste castokrat definovali funkciu viacerymi klauzulami, ako bolo nutne. Nie je to sice chyba a hoci to moze byt efektivnejsie, v tomto pripade je menej definicii lepsich z matematickeho hladiska. Castokrat sa vyskytovala konstrukcia 'plus (Succ Zero) vyraz'. Netreba zabudat, ze pricitanie jednotky sa da uplne lahko realizovat cisto pouzitim konstruktora Succ a teda dostaneme ovela strucnejsie 'Succ vyraz'. Domaca bonusova uloha k 4. cviceniu ------------------------------------- Vypracujte samostatne do piatku 20.04.2012 vratane a riesenia mi posielajte mailom. Body mozete ziskat bud za spravne riesenie na prvykrat, pripadne raz opravovane. Silne odporucam skutocne si vyskusat, ci funkcia funguje pred tym, ako mi riesenie poslete. Pomocou intenzionalnej zoznamovej notacie zapiste funkciu, ktora dostane ako argument kladne cele cislo a funguje takto: zoznam 2 = [[1], [1,2], [1..], [2], [2..]] zoznam 5 = [[1], [1,2], [1,2,3], [1,2,3,4], [1,2,3,4,5], [1..], [2], [2,3], [2,3,4], [2,3,4,5], [2..], [3], [3,4], [3,4,5], [3..], ... [5], [5..]] Pomocka: V lavej casti [ | ] moze byt podmienka. Pocas tvorenia funkcie sa moze hodit vracat namiesto [k..] nieco vhodnejsie. *** Vhodne moze byt rozlozit si ulohu na mensie, teda najprv generovat len zoznam zodpovedajuci jednemu riadku: one m n = [[m..k] | k <- [m..n]] ++ [[m..]] Funkcia one m n generuje zoznam [[m], [m,m+1], ..., [m..n], [m..]]. Da sa este trochu vylepsit tym, ze pripade nekonecneho zoznamu zahrnieme do intenzionalnej notacie. Na to vygenerujeme pre k este jednu hodnotu, ktoru budeme detegovat a u nem vygenerujeme [m..]: one m n = [if k < n + 1 then [m..k] else [m..] | k <- [m..n] Ked uz mame definovanu funkciu one, vysledna funkcia zoznam moze vyzerat takto: zoznam n = concat [one m n | m <- [1..n]] A pretoze one m n je intenzionalny zoznam, mozeme ho prepisat a transoformovat: = concat [[if k < n + 1 then [m..k] else [m..] | k <- [m..n] | m <- 1..n]] = [if k < n + 1 then [m..k] else [m..] | m <- [1..n], k <- [m..n]] podla vztahu concat [[ expr | ... ] | m <- s] = [expr | m <- s, ...] takze vysledna podoba je zoznam n = [if k < n + 1 then [m..k] else [m..] | m <- [1..n], k <- [m..n]] Domaca bonusova uloha k 5. cviceniu ------------------------------------- Ako rozsirenie binarnych stromov mozeme definovat n-arne stromy, kedy sa podmienka, ze uzol ma prave dvoch potomkov, meni na uzol moze mat lubovolny (v podstate aj nekonecny) nezaporny pocet potomkov. Definicia datoveho typu n-arny strom vyzera nasledovne: data NTree a = NNode a [NTree a] Podobne ako u binarneho stromu je prvym argumentom typu a hodnota v uzle. Dalej nasleduje zoznam podstromov. Rozdielom oproti BinTree je to, ze nemame konstruktor Empty. Uzlu, ktory nema uz ziadnych potomkov zodpoveda NNode x []. Zaroven to znamena, ze nemozeme mat prazdny strom - kazdy takto definovany n-arny strom bude neprazdny. Definujte na NTree funkcie a) ntmap (1 bod) b) ntzipWith (1 bod) Mozete si najprv skusit definovat tieto funkcie na obycajnom binarnom strome. Organizacne: Opat ako u ostatnych uloh - skontrolujte si, ci sa vam skript s definiciami uspesne nacita a na jednoduchych prikladoch funguje spravne. Termin je do konca 04.05. Riesenia zase posielajte mailom, limit na pocet oprav nebude, ale snazte sa to spravit s maximalne 2-3 opravami. *** ntmap f (NNode x s) = NNode (f x) (map (ntmap f) s) ntzipWith f (NNode x s) (NNode y t) = NNode (f x y) (zipWith (ntzipWith f) s t) *** a) ntmap Mame jediny konstruktor NNode, takze sa pokusime spravit to na jednu definiciu. Rozoberieme si n-arny strom na hodnotu v uzle a podstromy: ntmap f (NNode x s) = NNode neco1 neco2 Vieme, ze vysledkom musi byt n-arny strom, takze to musi byt v takom tvare. Hodnota neco1 je celkom jasna, musime aplikovat f na x, takze neco1 = f x. Pokial ide o neco2, na tom mieste by mal byt zoznam podstromov, na ktore rekurzivne aplikujeme ntmap. Teda neco2 bude map (ntmap f) s. Cely vysledok je ntmap f (NNode x s) = NNode (f x) (map (ntmap f) s) Nie je tam potrebne osobitne riesit pripad (NNode x []), pretoze ak bude zoznam s prazdny, tak podla nasej definicie sa argument (ntmap f) funkcie map aj tak nikde neaplikuje (lebo map _ [] = []) a tym sa rekurzia ukonci sama. b) Podobne sa pokusime aj o ntzipWith: ntzipWith f (NNode x s) (NNode y t) = NNode neco1 neco2 Hodnota neco1 je zase vcelku jasna: f x y. Hodnota neco2 by mala vyzerat pre zoznamy s = [NNode 1 [], NNode 9 []], t = [NNode 3 [], NNode 11 []] takto: [NNode (f 1 3) [], NNode (f 9 11) []]. Toto zas pripomina zipWith a vhodna funkcia, ktoru zipWith-u dame ako argument bude robit to iste, ako povodne zadanie, teda zliepat podstromy pomocou funkcie f, cize ntzipWith f. Konecny vysledok bude ntzipWith f (NNode x s) (NNode y t) = NNode (f x y) (zipWith (ntzipWith f) s t) Takisto tu nie je nutne riesit problem zastavenia rekurzie osobitnym definovanim pripadov s prazdnymi zoznamami, pretoze ak je aspon jeden argument zipWith prazdny zoznam, tak funkcia u zipWith sa nepouzije a rekurzia sa tym ukonci. Domaca bonusova uloha k 6. cviceniu ------------------------------------- Bez do notacie (teda pomocou operatorov >>=, >> a funkcie return) zapiste funkciu actparts :: String -> (String -> IO ()) -> IO (), ktora ma ako argumenty retazec a nejaku akciu. Funguje tak, ze postupne vypisuje chvosty retazca a za kazdym vypisom chvostu zavola akciu na nom. T.j. na retazci "ab" vykona v tomto poradi: vypis "ab", zavola akciu na "ab", vypise "b", zavola akciu na "b", vypise "" a zavola akciu na "". Retazec vypise aj s interpre- tovanim kontrolnych znakov. (2 body) Ako zvycajne, riesenia posielajte mailom, do 18.05. EDIT 12.05.: Opravena chyba v priklade s "ab", pridana posledna veta.