Pokročilé techniky funkcionálního programování, PRG040

Obsah semináře

Budeme se zabývat technikami, které se používají ve funkcionálním programování, přičemž konkrétní implementace budou v Haskellu. Prozkoumáme typový systém s třídami a jeho rozšíření v podobě type families a víceparametrických tříd s funkcionálními závislostmi, monády a monadické transformery, arrows, continuation passing style, ...

Také si povíme o vhodných funkcionálních datových strukturách, jak programovat s grafy a naučíme se, jak programovat imperativní algoritmy používající pole.

Dál nás bude zajímat vícevláknové programování a způsoby synchronizace vláken.

Kromě technik se naučíme profilovat a ladit programy v Haskellu, používat výjimky, řekneme si o používaných optimalizacích a vysvětlíme si, jak se propojují programy v Haskellu s jinými jazyky a technologiemi.

Doba a místo konání

Seminář se koná ve středu 14:00 v S10. První přednáška je ve středu 23. února.

Zápočet

Pro získání zápočtu je třeba získat 30 bodů. Body je možno získat za domácí úkoly (těch bude vypsáno za alespoň 80 bodů), za referát (osobní domluva) nebo za zápočťák. Ten si můžete domluvit kdykoliv a podle obtížnosti je za něj možno získat jeden až třicet bodů.

Obsahy přednášek

1. přednáška: úvod do funkcionálního programování a opakování základů Haskellu: ptfp01.hs, ptfp01.ps, ptfp01.pdf.
2. přednáška: funkce, výrazy, polymorfní metody a kvantifikované signatury, moduly, priority operátorů, standartní Prelude: ptfp02.hs, ptfp02.ps, ptfp02.pdf, prelude.hs, prelude.ps, prelude.pdf.
3. přednáška: knihovní funkce pracující se seznamy, pole, úvod do monád: ptfp03.hs, ptfp03.ps, ptfp03.pdf.
4. přednáška: třídy Functor, Monad a MonadPlus, rozšiřování monády pro vyhodnocování výrazů: ptfp04.hs, ptfp04.ps, ptfp04.pdf.
5. přednáška: monáda IO, monáda ST, pole se striktními hodnotami, pole v monádě: ptfp05.hs, ptfp05.ps, ptfp05.pdf.
6. přednáška: parsování pomocí monád, CPS monáda, přednášel Zdeněk
7. přednáška: monáda se zastavováním, monáda pro Continuation Passing Style a callCC, rozšíření typových tříd do víceparametrických tříd s funkcionálními závislostmi, typové rodiny, dokazování tvrzení pomocí typového systému: ptfp07.hs, ptfp07.ps, ptfp07.pdf.
8. přednáška: paralelní vyhodnocování pomocí par a vyhodnocovacích strategiích, dynamické datové typy, výjimky, vícevláknové programování, synchronizační primitivum MVar, semafory a kanály, práce se sítí: ptfp08.hs, ptfp08.ps, ptfp08.pdf.
9. přednáška: λ-kalkulus (definice, α-konverze a β-konverze, Church-Rosser), CL (kombinátory, slabá redukce), konverze λ-termu na CL-term a naopak, pointfree programování v Haskellu: ptfp09.hs, ptfp09.ps, ptfp09.pdf.
10. přednáška: paralelní programování s transakční pamětí a monáda STM, metaprogramování v Template Haskellu: ptfp10.hs, ptfp10.ps, ptfp10.pdf.
11. přednáška: Template Haskell, Scrap your boiler plate a polymorfismus vyšších řádů: ptfp11.hs, ptfp11.ps, ptfp11.pdf.
12. přednáška: různé pomocné třídy, Monoid, rychlé stringy, Applicative a Alternative, knihovna Parsec, skládání monád čili monad transformers, arrows: ptfp12.{hs,ps,pdf}, mtl.{hs,ps,pdf}, arrow.{hs,ps,pdf}.
13. přednáška: datové struktury -- fronty, amortizované fronty, fronty s konstantními operacemi v nejhorším případě, varianty perzistentních polí, přednášel Zdeněk

Domácí úkoly (29. 04. 2011)

Prosím posílejte úkoly jako textové přílohy mailu, nezabalujte je. Lépe se mi opravují.

Zadání domácích úkolů se může lehce změnit oproti tomu, které jsem zadával na hodině (když udělám nějakou chybu). Platná verze je vždy ta uvedená zde.

U některých úkolů je uvedená časová složitost potřebná k získání plného počtu bodů. Můžete ale poslat libovolné řešení s polynomiální složitostí, nějaké body za něj budou vždy. Můžete klidně poslat nejprve pomalé řešení a později poslat vylepšenou verzi.

Datum
cvičení ID Body Popis
23. února 2011 Úkoly můžete odevzdávat do 23. března 2011, 14:00.
wc 1.5 Napište skript, který přečte standardní vstup a na výstup vypíše jednu řádku (podobně jako wc bez parametrů až na nemezerové znaky):
počet_řádek počet_slov počet_nemezerových_znaků
Je vhodné použít main = interact w, kde w::String->String.
cat-n 1 Napište skript, který se chová jako cat -n, tj. čte standardní vstup a každý řádek očísluje stylem printf("%6d\t%s, číslo_řádku, text_řádku).
Pro další tři úlohy ji zadefinujte binární strom, který má hodnoty typu a v každém vrcholu, tj. data BinTree a = ....
l2t 2 Napište funkci, která dostane setřídění seznam a vytvoří z něj v lineárním čase perfektní binární vyhledávací strom. Perfektní znamená, že v každém vrcholu je velikost podstromu levého syna rovna velikosti podstromu pravého syna až na plus minus 1.
perf 1 Vytvořte funkci, které zadáte mocninu dvojky n=2^k a ona vytvoří úplný binární strom s k hladinami. V každém vrcholu je číslo 1. Optimalizujte na časovou složitost.
onepass 1 Napište funkci, které dáte binární strom s Inty a ona vytvoří strom stejného tvaru, taktéž s Inty, který má v každém vrcholu uložený celočíselný průměr všech hodnot vrcholů původního stromu. Pozor, původní strom můžete projít jenom jednou a ten nový nemůžete procházet vůbec (jenom ho vytvořit)!
02. března 2011 Úkoly můžete odevzdávat do 03. dubna 2011, 23:59.
show 1 Máte dáno data Tree a = Empty | Tree a [Tree a]. Napište ručně instanci Show (Tree a), aby fungovala v lineárním čase.
layers 1.5 Máte dáno data Tree a = Empty | Tree a [Tree a]. Napište funkci layers :: Tree a -> [a], která vrátí prvky stromu v pořadí po vrstvách, tj. stejně, jako by je navštívilo prohledávání do šířky spuštěné z kořene. Plný počet bodů za řešení v lineárním čase.
lcs 2 Napište funkci, která pro dva dané seznamy najde délku jejich nejdelšího společného ne nutně souvislého podseznamu. Časová složitost by měla být nejvíc O(součin délek těchto seznamů).
bala 2 Napište funkci balanced::[Int]->[Int], která dostane seznam nul a jedniček a vrátí takovou nejdelší souvislou podposloupnost, ve které je stejně nul a jedniček. Plný počet bodů za Ο(N).
09. března 2011 Úkoly můžete odevzdávat do 10. dubna 2011, 23:59.
sumall 1.5 Napište funkci sumall, která dostane libovolný nezáporný počet Integerů a vrátí jejich součet. K řešení potřebujete typové třídy a to, že -> je mimo jiné datový konstruktor.
isrot 2 Napište metodu isrot :: Eq a => [a] -> Bool, která zjistí, jestli je daný seznam roven nějaké své netriviální rotaci. Plný počet bodů za řešení v lineárním čase.
primes 2.5 Napište funkci primes :: [Integer], která vrací všechna prvočísla. Plný počet bodů za složitost Ο(N log log N) pro získání všech prvočísel do N, což je přesně složitost Eratosthenova síta. Na rozdíl od síta ale musíte vracet potenciálně nekonečně prvočísel. Za řešení v Ο(N √N) jeden bod.
split 3 Napište metodu split :: String -> [String] -> Maybe [String]. Ta dostane text bez mezer, složený z malých písmen anglické abecedy, a seznam platných slov. Výsledkem je text rozdělený na slova tak, aby každé bylo v daném slovníku. Pokud je možností rozdělení více, vyberte libovolné s nejmenším počtem slov. Plný počet bodů za řešení se složitostí Ο(délka_textu * délka_nejdelšího_slova + součet_délek_slov_slovníku).
16. března 2011 Úkoly můžete odevzdávat do 13. dubna 2011, 14:00.
logger 3 Vytvořte monádu, která si pamatuje logy (ta, o které mluvil Zdeněk na konci hodiny). Definujte tedy datový typ data WithLog x = ..., dále vytvořte jeho instanci třídy Monad a funkce addLog :: String -> WithLog () a getLog :: WithLog x -> [String]. Nakonec by měl fungovat následující kód:
mapWithLog f [] = return [] mapWithLog f (x:xs) = do ys <- mapWithLog f xs addLog $ "Zpracovavam prvek " ++ show x return $ f x : ys main = print $ length $ getLog $ mapWithLog (+1) [1..30000]

usek 2 Napište funkci usek::[Int]->Int, která dostane posloupnost a vrátí délku její nejdelší souvislé podposloupnosti, která má nezáporný součet svých členů. Body dostanete podle časové složitosti, O(N²) za bod, O(N) za dva.
tiso 2 Stromy jsou definované jako BinTree a = N | V (BinTree a) a (BinTree a). Napište funkci, která dostane dva stromy, a zjistí, jestli jsou stejné až na pořadí synů. Tedy V N 1 (V N 2 N) je až na pořadí synů shodný s V (V N 2 N) 1 N. Plný počet bodů jenom za řešení rychlejší než Ο(N²), kde N je počet vrcholů většího ze stromů.
dom 2 Napište funkci dom :: Ord a => [a] -> [(a, Int)], která dostane seznam a vrátí jeho kopii, která má navíc u každého prvku uloženo, kolik je ve zbytku seznamu prvků větších než tento aktuální. Tedy dom "brekeke" = zip "brekeke" [6, 0, 2, 0, 1, 0, 0]. Plný počet bodů za řešení v Ο(N log N).
23. března 2011 Úkoly můžete odevzdávat do 20. dubna 2011, 14:00.
feq 2.5 Napište program, který dostane na příkazové řádce (viz getArgs) jméno adresáře a on roztřídí soubory v tomto adresáři (ne v podadresářích; viz getDirectoryContent a doesDirectoryExist) do skupin podle obsahu, tj. v jedné skupině jsou právě soubory stejného obsahu. Zkuste vymyslet nějaký chytřejší způsob než porovnávat soubory každý s každým.
find 2 Napište program, který dostane na příkazové řádce řetězec a případně adresář (pokud adresář chybí, použije se aktuální adresář, tj. adresář jménem .), najde rekurzivně všechny soubory a podadresáře obsahující daný řetězec a vypíše je, jeden na řádku.
plen 2 Napište funkci plen :: [Int] -> Integer, která dostane permutaci a vrátí kolikrát nejméněkrát (nula neplatí :–) je třeba tuto permutaci složit samu se sebou, aby vznikla identická permutace.
stree 3 Na vstupu dostanete graf, zadaný jako seznam sousedů. První řádka vstupu obsahuje číslo N a i-tá řádka z dalších N řádek obsahuje každá sousedy i-tého vrcholu. V lineárním čase najděte a vypište libovolnou kostru tohoto grafu.
06. dubna 2011 Úkoly můžete odevzdávat do 04. května 2011, 14:00.
quad 2 Na vstupu je černobílý obrázek v rozlišení 2ⁿ x 2ⁿ zadaný následujícím kódováním:

kód celého černého obrázku je 0,
kód celého bílého obrázku je 1,
není-li obrázek jednobarevnký, reprezentuje ho kód (k₁k₂k₃k₄), kde k_i jsou kódy čtvrtin obrázku v pořadí vlevo nahoře, vpravo nahoře, vlevo dole, vpravo dole.
Napište funkci rotate :: String -> String, která dostane kód obrázku a vrátí kód obrázku, který vznikne otočením doleva o 90°. Na plný počet bodů musí být časová složitost lineární.
Příklad: rotate "(01(1011)1)" = "(110(0111))".
cut 2 Napište program, který dostane na příkazové řádce dva parametry, první je seznam sloupců te formátu "3-6,1,2,7-10" a druhý nepovinný parametr je jediný znak, oddělovač. Program čte standardní vstup, každý řádek rozseká na sloupce podle oddělovače a vypíše pouze zadané sloupce, které na výstupu opět oddělí oddělovačem.
recon 2.5 Napište funkci recon :: [a] -> [a] -> BinTree a, která dostane vrcholy stromu v prefixovém uspořádání, vrcholy toho samého stromu v infixovém uspořádání a vrátí původní strom. Předpokládejte, že všechny vrcholy stromu mají jedinečné hodnoty. Plný počet bodů za lineární řešení.
hangman 2.5 Napište program, který s vámi hraje šibenici. Na začátku načte ze souboru words.txt seznam slov. Pak vždy jedno náhodně vybere a nechá vás postupně zadávat písmenka (žádné ne víckrát) a zobrazuje, která písmenka už jste uhodli. Po určitém počtu špatných pokusů skončíte a jste pověšeni. Když uhodnete, můžete pokračovat jiným slovem. Za asciiartové obrázky šibenice je bonus :–) BTW pokud máte chuť, můžete se podívat na knihovnu ansi-terminal, ale není to podmínka k získání bodů.
13. dubna 2011 Úkoly můžete odevzdávat do 11. května 2011, 14:00.
chats 4 Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul Network. Server by měl poslouchat na zadaném portu. Připojit se může libovolný počet lidí. Když se někdo připojí, tak na první řádce napíše svůj nickname. Každá dalšá řádka od něj se pošle všem ostatním připojeným (těm, kteří už poslali nickname) ve formátu "nickname: řádka".
chatc 2 Napište k serveru chatovací klient. Na příkazové řádce dostane adresu a port serveru a nickname uživatele. Zkusí se připojit a pak každou zadanou řádku pošle na server. Zprávy od serveru zobrazujte průběžně: když v půlce psaní přijde zpráva ze sítě, tak se odstraní rozepsaná zpráva, vypíše se místo ní přijatá a na další řádce se objeví rozepsaná a půjde dopsat (můžete použít například hSetBuffering stdin NoBuffering).
web 4 Napište jednoduchý webserver. Webserveru při spuštění dáte port a adresář, ze kterého má obsluhovat. Webserver pak sedí na daném portu. Když se ho někdo zeptá, obslouží ho, a obsluhovat zvládne libovolně lidí najednou. Implementujte HTTP 0.9, přičemž byste měli v adresách umět dekódovat "%xy", viz zde. Mělo by to fungovat natolik, aby se se serverem dokázaly mé prohlížeče (Opera, Firefox) bavit.
diff 3 Napište program, který se bude chovat jako diff -u. Tedy program dostane na příkazové řádce jména dvou souborů. Jméno jednoho z těchto souborů může být -, což znamená standardní vstup. Na standardní výstup vypište diff těchto souborů ve formátu unified diff. Stejně jako diff -u je velikost kontextu 3, ale pokud uživatel zadá na začátku příkazové řádky -U num, změní se velikost kontextu na num (tedy -U 3 je implicitní). Složitost maximálně kvadratická. Pokud bude časová složitost Ο(počet řádek v obou souborech * velikost diffu) a paměťová Ο(velikost diffu na druhou), viz tento článek, dostanete další 3 body.
20. dubna 2011 Úkoly můžete odevzdávat do 18. května 2011, 14:00.
func1 1 Naprogramujte funkci func1 x l = map (\y -> y * x) l bez použití pojmenovaných argumentů.
func3 1 Naprogramujte funkci func3 f l = l ++ map f l bez použití pojmenovaných argumentů.
func4 1 Naprogramujte funkci func4 l = map (\y -> y+2) (filter (\z -> z `elem` [1..10]) (5:l)) bez použití pojmenovaných argumentů.
func5 1 Naprogramujte funkci func5 f l = foldr (\x y -> f (y,x)) 0 l bez použití pojmenovaných argumentů.
dot 3 Naprogramujte funkci pro paralelní výpočet skalárního součinu. Funkce dot :: Array Int Int -> Array Int Int -> IO Int co nejrychleji vypočítá skalární součin daných polí, které obě musí mít stejné meze. Časová složitost by měla být ideálně Ο(N/P + log N), kde N je délka vektorů a P počet paralelně běžících vláken (pravděpodobně počet jader vašeho procesoru).
27. dubna 2011 Úkoly můžete odevzdávat do 25. května 2011, 14:00.
insert 2 Napište funkci insert :: String -> ExpQ pro Template Haskell. Když ji použijete jako $(insert "a.txt"), tak se při kompilaci najde soubor a.txt a jeho obsah se vloží jako řetězec do místa volání.
sqrt 3 Napište funkci odmocni :: Integer -> Int -> ExpQ pro Template Haskell, že $(odmocni 2 100) se nahradí za odmocninu ze dvou na sto desetinných míst. Musíte se tedy nahradit číslem typu Rational, jehož jmenovatel bude 10¹⁰⁰ a jehož čitatel bude takový, aby to byla požadovaná odmocnina.
psort 3 Napište funkci psort :: (Ord a) => Int -> [a] -> [a], která dostane k, posloupnost a setřídí ji, za předpokladu, že je tato posloupnost skoro setříděná – přesně můžete předpokládat, že každý prvek dané posloupnosti je nejvýš o k pozic mimo svojí pozici v setříděné posloupnosti. Optimalizujte časovou složitost, Ο(n log k) za tři body, Ο(nk) za jeden a půl, zbytek jako Ο(n log n) za půl bodu.

Datum cvičení	ID	Body	Popis
23. února 2011	Úkoly můžete odevzdávat do 23. března 2011, 14:00.
wc	1.5	Napište skript, který přečte standardní vstup a na výstup vypíše jednu řádku (podobně jako `wc` bez parametrů až na nemezerové znaky): `počet_řádek počet_slov počet_nemezerových_znaků` Je vhodné použít `main = interact w`, kde `w::String->String`.
cat-n	1	Napište skript, který se chová jako `cat -n`, tj. čte standardní vstup a každý řádek očísluje stylem `printf("%6d\t%s, číslo_řádku, text_řádku)`.
		Pro další tři úlohy ji zadefinujte binární strom, který má hodnoty typu `a` v každém vrcholu, tj. `data BinTree a = ...`.
l2t	2	Napište funkci, která dostane setřídění seznam a vytvoří z něj v lineárním čase perfektní binární vyhledávací strom. Perfektní znamená, že v každém vrcholu je velikost podstromu levého syna rovna velikosti podstromu pravého syna až na plus minus 1.
perf	1	Vytvořte funkci, které zadáte mocninu dvojky n=2^k a ona vytvoří úplný binární strom s k hladinami. V každém vrcholu je číslo 1. Optimalizujte na časovou složitost.
onepass	1	Napište funkci, které dáte binární strom s `Int`y a ona vytvoří strom stejného tvaru, taktéž s `Int`y, který má v každém vrcholu uložený celočíselný průměr všech hodnot vrcholů původního stromu. Pozor, původní strom můžete projít jenom jednou a ten nový nemůžete procházet vůbec (jenom ho vytvořit)!
02. března 2011	Úkoly můžete odevzdávat do 03. dubna 2011, 23:59.
show	1	Máte dáno `data Tree a = Empty \| Tree a [Tree a]`. Napište ručně instanci `Show (Tree a)`, aby fungovala v lineárním čase.
layers	1.5	Máte dáno `data Tree a = Empty \| Tree a [Tree a]`. Napište funkci `layers :: Tree a -> [a]`, která vrátí prvky stromu v pořadí po vrstvách, tj. stejně, jako by je navštívilo prohledávání do šířky spuštěné z kořene. Plný počet bodů za řešení v lineárním čase.
lcs	2	Napište funkci, která pro dva dané seznamy najde délku jejich nejdelšího společného ne nutně souvislého podseznamu. Časová složitost by měla být nejvíc O(součin délek těchto seznamů).
bala	2	Napište funkci `balanced::[Int]->[Int]`, která dostane seznam nul a jedniček a vrátí takovou nejdelší souvislou podposloupnost, ve které je stejně nul a jedniček. Plný počet bodů za Ο(N).
09. března 2011	Úkoly můžete odevzdávat do 10. dubna 2011, 23:59.
sumall	1.5	Napište funkci `sumall`, která dostane libovolný nezáporný počet `Integer`ů a vrátí jejich součet. K řešení potřebujete typové třídy a to, že `->` je mimo jiné datový konstruktor.
isrot	2	Napište metodu `isrot :: Eq a => [a] -> Bool`, která zjistí, jestli je daný seznam roven nějaké své netriviální rotaci. Plný počet bodů za řešení v lineárním čase.
primes	2.5	Napište funkci `primes :: [Integer]`, která vrací všechna prvočísla. Plný počet bodů za složitost Ο(N log log N) pro získání všech prvočísel do N, což je přesně složitost Eratosthenova síta. Na rozdíl od síta ale musíte vracet potenciálně nekonečně prvočísel. Za řešení v Ο(N √N) jeden bod.
split	3	Napište metodu `split :: String -> [String] -> Maybe [String]`. Ta dostane text bez mezer, složený z malých písmen anglické abecedy, a seznam platných slov. Výsledkem je text rozdělený na slova tak, aby každé bylo v daném slovníku. Pokud je možností rozdělení více, vyberte libovolné s nejmenším počtem slov. Plný počet bodů za řešení se složitostí Ο(délka_textu délka_nejdelšího_slova + součet_délek_slov_slovníku)*.
16. března 2011	Úkoly můžete odevzdávat do 13. dubna 2011, 14:00.
logger	3	Vytvořte monádu, která si pamatuje logy (ta, o které mluvil Zdeněk na konci hodiny). Definujte tedy datový typ `data WithLog x = ...`, dále vytvořte jeho instanci třídy `Monad` a funkce `addLog :: String -> WithLog ()` a `getLog :: WithLog x -> [String]`. Nakonec by měl fungovat následující kód: mapWithLog f [] = return [] mapWithLog f (x:xs) = do ys <- mapWithLog f xs addLog $ "Zpracovavam prvek " ++ show x return $ f x : ys main = print $ length $ getLog $ mapWithLog (+1) [1..30000]
usek	2	Napište funkci `usek::[Int]->Int`, která dostane posloupnost a vrátí délku její nejdelší souvislé podposloupnosti, která má nezáporný součet svých členů. Body dostanete podle časové složitosti, O(N²) za bod, O(N) za dva.
tiso	2	Stromy jsou definované jako `BinTree a = N \| V (BinTree a) a (BinTree a)`. Napište funkci, která dostane dva stromy, a zjistí, jestli jsou stejné až na pořadí synů. Tedy `V N 1 (V N 2 N)` je až na pořadí synů shodný s `V (V N 2 N) 1 N`. Plný počet bodů jenom za řešení rychlejší než Ο(N²), kde N je počet vrcholů většího ze stromů.
dom	2	Napište funkci `dom :: Ord a => [a] -> [(a, Int)]`, která dostane seznam a vrátí jeho kopii, která má navíc u každého prvku uloženo, kolik je ve zbytku seznamu prvků větších než tento aktuální. Tedy `dom "brekeke" = zip "brekeke" [6, 0, 2, 0, 1, 0, 0]`. Plný počet bodů za řešení v Ο(N log N).
23. března 2011	Úkoly můžete odevzdávat do 20. dubna 2011, 14:00.
feq	2.5	Napište program, který dostane na příkazové řádce (viz `getArgs`) jméno adresáře a on roztřídí soubory v tomto adresáři (ne v podadresářích; viz `getDirectoryContent` a `doesDirectoryExist`) do skupin podle obsahu, tj. v jedné skupině jsou právě soubory stejného obsahu. Zkuste vymyslet nějaký chytřejší způsob než porovnávat soubory každý s každým.
find	2	Napište program, který dostane na příkazové řádce řetězec a případně adresář (pokud adresář chybí, použije se aktuální adresář, tj. adresář jménem `.`), najde rekurzivně všechny soubory a podadresáře obsahující daný řetězec a vypíše je, jeden na řádku.
plen	2	Napište funkci `plen :: [Int] -> Integer`, která dostane permutaci a vrátí kolikrát nejméněkrát (nula neplatí :–) je třeba tuto permutaci složit samu se sebou, aby vznikla identická permutace.
stree	3	Na vstupu dostanete graf, zadaný jako seznam sousedů. První řádka vstupu obsahuje číslo N a i-tá řádka z dalších N řádek obsahuje každá sousedy i-tého vrcholu. V lineárním čase najděte a vypište libovolnou kostru tohoto grafu.
06. dubna 2011	Úkoly můžete odevzdávat do 04. května 2011, 14:00.
quad	2	Na vstupu je černobílý obrázek v rozlišení 2ⁿ x 2ⁿ zadaný následujícím kódováním: kód celého černého obrázku je `0`, kód celého bílého obrázku je `1`, není-li obrázek jednobarevnký, reprezentuje ho kód `(k₁k₂k₃k₄)`, kde `k_i` jsou kódy čtvrtin obrázku v pořadí vlevo nahoře, vpravo nahoře, vlevo dole, vpravo dole. Napište funkci `rotate :: String -> String`, která dostane kód obrázku a vrátí kód obrázku, který vznikne otočením doleva o 90°. Na plný počet bodů musí být časová složitost lineární. Příklad: `rotate "(01(1011)1)" = "(110(0111))"`.
cut	2	Napište program, který dostane na příkazové řádce dva parametry, první je seznam sloupců te formátu "3-6,1,2,7-10" a druhý nepovinný parametr je jediný znak, oddělovač. Program čte standardní vstup, každý řádek rozseká na sloupce podle oddělovače a vypíše pouze zadané sloupce, které na výstupu opět oddělí oddělovačem.
recon	2.5	Napište funkci `recon :: [a] -> [a] -> BinTree a`, která dostane vrcholy stromu v prefixovém uspořádání, vrcholy toho samého stromu v infixovém uspořádání a vrátí původní strom. Předpokládejte, že všechny vrcholy stromu mají jedinečné hodnoty. Plný počet bodů za lineární řešení.
hangman	2.5	Napište program, který s vámi hraje šibenici. Na začátku načte ze souboru `words.txt` seznam slov. Pak vždy jedno náhodně vybere a nechá vás postupně zadávat písmenka (žádné ne víckrát) a zobrazuje, která písmenka už jste uhodli. Po určitém počtu špatných pokusů skončíte a jste pověšeni. Když uhodnete, můžete pokračovat jiným slovem. Za asciiartové obrázky šibenice je bonus :–) BTW pokud máte chuť, můžete se podívat na knihovnu ansi-terminal, ale není to podmínka k získání bodů.
13. dubna 2011	Úkoly můžete odevzdávat do 11. května 2011, 14:00.
chats	4	Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul `Network`. Server by měl poslouchat na zadaném portu. Připojit se může libovolný počet lidí. Když se někdo připojí, tak na první řádce napíše svůj nickname. Každá dalšá řádka od něj se pošle všem ostatním připojeným (těm, kteří už poslali nickname) ve formátu "nickname: řádka".
chatc	2	Napište k serveru chatovací klient. Na příkazové řádce dostane adresu a port serveru a nickname uživatele. Zkusí se připojit a pak každou zadanou řádku pošle na server. Zprávy od serveru zobrazujte průběžně: když v půlce psaní přijde zpráva ze sítě, tak se odstraní rozepsaná zpráva, vypíše se místo ní přijatá a na další řádce se objeví rozepsaná a půjde dopsat (můžete použít například `hSetBuffering stdin NoBuffering`).
web	4	Napište jednoduchý webserver. Webserveru při spuštění dáte port a adresář, ze kterého má obsluhovat. Webserver pak sedí na daném portu. Když se ho někdo zeptá, obslouží ho, a obsluhovat zvládne libovolně lidí najednou. Implementujte HTTP 0.9, přičemž byste měli v adresách umět dekódovat "%xy", viz zde. Mělo by to fungovat natolik, aby se se serverem dokázaly mé prohlížeče (Opera, Firefox) bavit.
diff	3	Napište program, který se bude chovat jako `diff -u`. Tedy program dostane na příkazové řádce jména dvou souborů. Jméno jednoho z těchto souborů může být `-`, což znamená standardní vstup. Na standardní výstup vypište diff těchto souborů ve formátu unified diff. Stejně jako `diff -u` je velikost kontextu 3, ale pokud uživatel zadá na začátku příkazové řádky `-U num`, změní se velikost kontextu na `num` (tedy `-U 3` je implicitní). Složitost maximálně kvadratická. Pokud bude časová složitost Ο(počet řádek v obou souborech velikost diffu)* a paměťová Ο(velikost diffu na druhou), viz tento článek, dostanete další 3 body.
20. dubna 2011	Úkoly můžete odevzdávat do 18. května 2011, 14:00.
func1	1	Naprogramujte funkci `func1 x l = map (\y -> y * x) l` bez použití pojmenovaných argumentů.
func3	1	Naprogramujte funkci `func3 f l = l ++ map f l` bez použití pojmenovaných argumentů.
func4	1	Naprogramujte funkci func4 l = map (\y -> y+2) (filter (\z -> z `elem` [1..10]) (5:l)) bez použití pojmenovaných argumentů.
func5	1	Naprogramujte funkci `func5 f l = foldr (\x y -> f (y,x)) 0 l` bez použití pojmenovaných argumentů.
dot	3	Naprogramujte funkci pro paralelní výpočet skalárního součinu. Funkce `dot :: Array Int Int -> Array Int Int -> IO Int` co nejrychleji vypočítá skalární součin daných polí, které obě musí mít stejné meze. Časová složitost by měla být ideálně Ο(N/P + log N), kde N je délka vektorů a P počet paralelně běžících vláken (pravděpodobně počet jader vašeho procesoru).
27. dubna 2011	Úkoly můžete odevzdávat do 25. května 2011, 14:00.
insert	2	Napište funkci `insert :: String -> ExpQ` pro Template Haskell. Když ji použijete jako `$(insert "a.txt")`, tak se při kompilaci najde soubor `a.txt` a jeho obsah se vloží jako řetězec do místa volání.
sqrt	3	Napište funkci `odmocni :: Integer -> Int -> ExpQ` pro Template Haskell, že `$(odmocni 2 100)` se nahradí za odmocninu ze dvou na sto desetinných míst. Musíte se tedy nahradit číslem typu `Rational`, jehož jmenovatel bude 10¹⁰⁰ a jehož čitatel bude takový, aby to byla požadovaná odmocnina.
psort	3	Napište funkci `psort :: (Ord a) => Int -> [a] -> [a]`, která dostane k, posloupnost a setřídí ji, za předpokladu, že je tato posloupnost skoro setříděná – přesně můžete předpokládat, že každý prvek dané posloupnosti je nejvýš o k pozic mimo svojí pozici v setříděné posloupnosti. Optimalizujte časovou složitost, Ο(n log k) za tři body, Ο(nk) za jeden a půl, zbytek jako Ο(n log n) za půl bodu.

Stav (25. 05. 2018)

Jméno	Odevzdané úkoly	Body

Zpět