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

Doba a místo konání

Úterý 10:40, chodba před kanceláří 322.

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ů.

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.

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: datové typy, polymorfní metody a kvantifikované signatury, typové třídy, standartní Prelude ptfp02.hs, ptfp02.ps, ptfp02.pdf, prelude.hs, prelude.ps, prelude.pdf.
3. přednáška: moduly, striktní vyhodnocování a seq, funkce pracující se seznamy z Prelude, pole ptfp03.hs, ptfp03.ps, ptfp03.pdf.
4. přednáška: debugování a ladící výpisy, základy IO knihovny, monády ptfp04.hs, ptfp04.ps, ptfp04.pdf.
5. přednáška: typové třídy a instance pro konstruktor ->, IO funkce v Prelude a v modulu IO, pokročilejší monády, funktor ptfp05.hs, ptfp05.ps, ptfp05.pdf.
6. přednáška: definované instance monád pro Maybe a [], parser jako monáda, MonadPlus, parser nad danou monádou ptfp06.hs, ptfp06.ps, ptfp06.pdf.
7. přednáška: rozšíření typových tříd do víceparametrických tříd s funkcionálními závislostmi, typové rodiny; datové struktury musí být perzistentní, seznamy, pole, stromy; amortizovaná implementace front, která perzistentně nefunguje optimálně ptfp07.hs, ptfp07.ps, ptfp07.pdf.
8. přednáška: funkční amortizovaná perzistentní implementace front, worst-case perzistentní implementace front, IArray, UArray, rozdílová pole Diff[U]Array, pole v monádě IO, odkazy v monádě IO ptfp08.hs, ptfp08.ps, ptfp08.pdf.
9. přednáška: monáda ST, pole a odkazy uvnitř monády ST, polymorfismus vyšších řádů ptfp09.hs, ptfp09.ps, ptfp09.pdf.
10. přednáška: paralelismus pomocí par, strategie vyhodnocování, dynamické datové typy a přetypování na předka a potomka, hierarchie výjimek a práce s výjimkami, vícevláknové programování, MVary jako synchronizační primitiva ptfp10.hs, ptfp10.ps, ptfp10.pdf.
11. přednáška: active patterns alias views, funkcionální přístup ke grafům -- graf jako induktivní datový typ, arrows a jejich porovnání s monádami ptfp11.hs, ptfp11.ps, ptfp11.pdf.
12. přednáška: synchronizace pomocí STM, GADT - zobecněné algebraické datové typy, ByteString a přetížené řetězcové literály, regulární výrazy ptfp12.hs, ptfp12.ps, ptfp12.pdf.

Domácí úkoly (27. 08. 2009)

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

Všechny domácí úkoly by měly být spustitelné na hugsu i na ghci, pokud nebude u úkolu řečeno jinak, byť můžete používat vcelku libovolná rozšíření oproti Haskellu 98, která jsou v obou interpreterech.

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.

Datum
cvičení ID Body Popis
03. března 2009 Úkoly můžete odevzdávat do 24. března 2009, 10:40.
wc 2 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 2 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. BinTree a = ....
l2t 2 Napište funkci, která dostane setřídění seznam a vytvoří z něj 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 2 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)!
10. března 2009 Úkoly můžete odevzdávat do 31. března 2009, 10:40.
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.
n235 1.5 Napište funkci, která vrací nekonečný seznam rostoucích čísel, která nemají jiné prvočíselné dělitele než 2, 3, 5, tj. čísel tvaru 2ⁱ * 3^j * 5^k. Složitost získání prvních K prvků musí být O(K).
lcs 1.5 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ů).
sumall 1.5 Napište funkci sumall, která dostane libovolný nezáporný počet Intů a vrátí jejich součet.
printf 1.5 Napište funkci printf, která bude umět vypisovat dané argumenty podle formátovacího řetězce. Podporujte alespoň %c %d a %s. Funkce nemusí fungovat přesně tak, jako její céčková varianta, ale printf "Ahoj %d %s%c" (5::Int) "člověků" '!' by mělo fungovat.
mulall 1.5 Navrhněte funkci mulAll, které jako první parametr nějak zadáte počet a ona pak vynásobí tolik parametrů typu Integer. Takže typ mulAll "dva" musí být Integer->Integer->Integer. Tu "dvojku" nemůžete zadat číslem ani stringem, ale nějak jinak (klidně to může být unárně).
17. března 2009 Úkoly můžete odevzdávat do 07. dubna 2009, 10:40.
pyth 1.5 Napište funkci pyth::[(Int,Int,Int)], která bude vracet všechny pythagorejské trojice, tj. trojice kladných přirozených čísel, že a²+b²=c². Tato funkce by měla vracet všechny takové trojice a přitom každou právě jednou ((3,4,5) a (4,3,5) jsou stejné trojice).
ls 2 Napište příkaz ls, který dostane na příkazové řádce několik adresářů, každý z nich rekurzivně projde a vypíše.
diff 3 Napište příkaz diff, který dostane na příkazové řádce dva soubory (pokud jeden chybí, tak je to standardní vstup) a najde diff, tj. nejmenší počet řádek, které je třeba odstranit či přidat, aby se z prvního souboru stal druhý. Na výstup (jako diff -u) vypište nezměněné řádky s mezerou na začátku, odstraněné s - na začátku a přidané s + na začátku.
24. března 2009 Úkoly můžete odevzdávat do 14. dubna 2009, 10:40.
bala 1-2 Napište funkci balanced::[Int]->Int, která dostane seznam nul a jedniček a vrátí délku nejdelší souvislé podposloupnosti, ve které je stejně nul a jedniček. Body dostanete podle časové složitosti, O(N²) za bod, O(N) za dva a půl.
usek 1-2.5 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 a půl bodu.
demo 3 Napište funkce demorse::String->String, která dekóduje vstup v morseovce. Tečka je tečka, čárka je pomlčka, oddělovač znaků je svislítko a oddělovač slov jsou dvě svislítka. Ostatní znaky ignorujte. Plný počet bodů jenom za složitost lineární s velikostí vstupu plus s velikostí abecedy.
mstop 3 Rozšiřte monádu z Eval3.hs tak, aby podporovala funkci stop :: Vypocet (). Této funkci předáte string. Tato funkce přeruší výpočet v monádě a vrátí (uvnitř té monády samozřejmě) onen string a zbytek výpočtu. Uživatel může zbytek výpočtu kdykoliv spustit.
31. března 2009 Úkoly můžete odevzdávat do 21. dubna 2009, 10:40.
feq 3 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ář), najde rekurzivně všechny soubory a podadresáře obsahující daný řetězec a vypíše je, jeden na řádku.
coll 2.5 Vytvořte funkci collision::(Integer->Integer)->(Integer,Integer), která dostane funkci f, o které ví, že nekonečná posloupnost $f(0), f(f(0)), f(f(f(0))),...$ neobsahuje nulu a skládá se pouze z konečného počtu různých čísel (čili je od nějaké doby periodická). Najděte $co nejrychleji a s pomocí co nejméně paměti dvě různé hodnoty x,y, aby f(x)=f(y)$.
tiso 2.5 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ů.
07. dubna 2009 Úkoly můžete odevzdávat do 28. dubna 2009, 10:40.
Mějme binární stromy BinTree a = N | V (BinTree a) a (BinTree a).
bfst 2.5 Napište funkci bfst :: BinTree a -> BinTree Int, která dostane binární strom a vrátí binární strom stejného tvaru, který má vrcholy očíslované po vrstvách zleva doprava, tj. vrcholy jsou očíslované v pořadí, v jakém byste je navštívili při prohledávání do šířky. Plný počet bodů za lineární řešení.
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í.
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.
calc 3 Napište jednoduchou kalkulačku pro čísla s libovolnou přesností. Čtěte standardní vstup, každá řádka je jeden výraz, spočtěte ho a výsledek vypište. Výraz je klasický aritmetický výraz s operacemi + - * / % (mínus jenom binární), závorkami, čísly a speciální proměnnou "last", ve které je uložen výsledek předchozího výrazu (a nula, pokud jde o první výraz nebo se minulý výraz nepovedlo naparsovat nebo vyhodnotit). Na parsování výrazu si napište parser typu toho z přednášky (výsledky parseru ukládejte do Maybe monády). Vše počítejte v Integerech. Složitost by měla být lineární s velikostí vstupu.
14. dubna 2009 Úkoly můžete odevzdávat do 05. května 2009, 10:40.
blud 3 Na vstupu dostanete bludiště: dostanete čísla N,M a dále M řádek, každá obsahuje N nemezerových znaků. Velké X je zeď, tečka je volno, M je matfyzák, který je v bludišti právě jeden, a m je matfyzačka, která je v bludišti také právě jedna. Najděte a zobrazte nejkratší cestu mezi matfyzačkou a matfyzákem. Vypište bludiště ve stejném formátu, jenom zavináčem označte políčka, která leží na nejkratší cestě. Chci Ο(MN) nebo Ο(MN log(MN)).
primes 3 Napište funkci primes :: [Integer], která vrací všechna prvočísla. Tato funkce musí fungovat velmi rychle, se 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.
21. dubna 2009 Úkoly můžete odevzdávat do 12. května 2009, 10:40.
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.
fft 3 Naprogramujte v Haskellu funkci fft::Int->[Float]->[Complex Float]. Tato funkce použitá jako fft n seznam_2n_floatů provede FFT, tj. rychlou Fourierovu transformaci na daných hodnotách. Složitost algoritmu musí být Ο(N log N).
28. dubna 2009 Úkoly můžete odevzdávat do 19. května 2009, 10:40.
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, která dostane kód obrázku a vrátí kód obrázku, který vznikne otočením doleva o 90^o. Na plný počet bodů musí být časová složitost lineární.
hangman 3 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ů.
05. května 2009 Úkoly můžete odevzdávat do 30. září 2009.
rost 3 Napište funkci rost :: Ord a => [a] -> [a], která vrátí nejdelší rostoucí podposloupnost (nemusí být souvislá) zadané posloupnosti. Plný počet bodů jenom za O(N log N), za O(N²) jsou body dva.
acc 3 Napište funkci acc :: (a->a->a) -> [a] -> IO a. Pokud spustíte acc f [x1,...,xn], je vaším úkolem vrátit hodotu x1 `f` x2 `f` ... `f` xn. Funkce f je asociativní. Výpočet co nejvíce zparalelizujte – měl by doběhnout v čase Ο(n)+log n*Ο(čas vyhodnocení f), pokud máte k dispozici n procesorů. Nespoléhejte se na par.
chats 4 Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul Network. Jak v GHC tak v Hugsu byste ho měli mít nainstalovaný, dokumentace je tady. 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 nějak průběžně (nemusíte je zobrazovat když zrovna uživatel píše zprávu). Pokud to bude fungovat tak, že budete moct psát zprávu a 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, dostanete plus dva body (použít můžete 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.
logo 8 Implementujte jednoduchou variantu Loga v Haskellu. Vaše implementace musí být jeden modul, který definuje abstraktní typ Program, a dále exportuje primitiva forward::Int->Program (posune želvičku o daný počet kroků/pixelů), left::Int->Program (otočí želvičku doleva o daný počet stupňů), pen::Bool->Program (zda odteď želvička kreslí nebo ne) a color::Color->Program (barva pera, typ Color si navrhněte jak chcete).
Dále musíte umět tato primitiva nejak spojovat. Osobně vám doporučuji, abyste si vytvořili modádu ProgramM a a pak zadefinovali type Program=ProgramM (). Pak můžete psát programy pro želvičku jako
spirala delka uhel = do forward delka left uhel when (delka<100) $ spirala (delka+2) uhel
Nakonec exportujte z modulu funkci runLogo::Int->Program->IO (), která dostane uživatelem definovaný program a ten spustí (otevře okno, provede ho a nechá okno otevřené než ho uživatel zavře). Obrázek zobrazujte průběžně. První parametr funkce je počet ms, jak dlouho se čeká po provedení left, forward, pen, color. Pro grafiku můžete použít co se vám zlíbí, třeba HGL, gtk2hs, wxHaskell, Glut+OpenGL, GLFW+OpenGL, SDL,...
logo2 3 Rozšiřte předchozí úlohu o funkci run2Logos::Int->Program->Program->IO (), která dostane program dvou želviček a bude je provádět paralelně (provádí jeden program, poté, co on zavolá jednu z funkcí forward,left,pen,color počká daný počet ms (první parametr), pak tento program přeruší a provádí druhý program,...).
12. května 2009 Úkoly můžete odevzdávat do 30. září 2009.
kruskal 2.5 Implementujte Kruskalův algoritmus v čase O(N log² N).
dinic 3.5 Pomocí knihovny FGL implementujte Dinicův algoritmus na toky.

Datum cvičení	ID	Body	Popis
03. března 2009	Úkoly můžete odevzdávat do 24. března 2009, 10:40.
wc	2	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	2	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. `BinTree a = ...`.
l2t	2	Napište funkci, která dostane setřídění seznam a vytvoří z něj 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	2	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)!
10. března 2009	Úkoly můžete odevzdávat do 31. března 2009, 10:40.
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.
n235	1.5	Napište funkci, která vrací nekonečný seznam rostoucích čísel, která nemají jiné prvočíselné dělitele než 2, 3, 5, tj. čísel tvaru 2ⁱ 3^j * 5^k. Složitost získání prvních K prvků musí být O(K)*.
lcs	1.5	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ů).
sumall	1.5	Napište funkci `sumall`, která dostane libovolný nezáporný počet `Int`ů a vrátí jejich součet.
printf	1.5	Napište funkci `printf`, která bude umět vypisovat dané argumenty podle formátovacího řetězce. Podporujte alespoň `%c` `%d` a `%s`. Funkce nemusí fungovat přesně tak, jako její céčková varianta, ale `printf "Ahoj %d %s%c" (5::Int) "člověků" '!'` by mělo fungovat.
mulall	1.5	Navrhněte funkci `mulAll`, které jako první parametr nějak zadáte počet a ona pak vynásobí tolik parametrů typu `Integer`. Takže typ `mulAll "dva"` musí být `Integer->Integer->Integer`. Tu "dvojku" nemůžete zadat číslem ani stringem, ale nějak jinak (klidně to může být unárně).
17. března 2009	Úkoly můžete odevzdávat do 07. dubna 2009, 10:40.
pyth	1.5	Napište funkci `pyth::[(Int,Int,Int)]`, která bude vracet všechny pythagorejské trojice, tj. trojice kladných přirozených čísel, že a²+b²=c². Tato funkce by měla vracet všechny takové trojice a přitom každou právě jednou ((3,4,5) a (4,3,5) jsou stejné trojice).
ls	2	Napište příkaz `ls`, který dostane na příkazové řádce několik adresářů, každý z nich rekurzivně projde a vypíše.
diff	3	Napište příkaz `diff`, který dostane na příkazové řádce dva soubory (pokud jeden chybí, tak je to standardní vstup) a najde diff, tj. nejmenší počet řádek, které je třeba odstranit či přidat, aby se z prvního souboru stal druhý. Na výstup (jako `diff -u`) vypište nezměněné řádky s mezerou na začátku, odstraněné s - na začátku a přidané s + na začátku.
24. března 2009	Úkoly můžete odevzdávat do 14. dubna 2009, 10:40.
bala	1-2	Napište funkci `balanced::[Int]->Int`, která dostane seznam nul a jedniček a vrátí délku nejdelší souvislé podposloupnosti, ve které je stejně nul a jedniček. Body dostanete podle časové složitosti, O(N²) za bod, O(N) za dva a půl.
usek	1-2.5	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 a půl bodu.
demo	3	Napište funkce `demorse::String->String`, která dekóduje vstup v morseovce. Tečka je tečka, čárka je pomlčka, oddělovač znaků je svislítko a oddělovač slov jsou dvě svislítka. Ostatní znaky ignorujte. Plný počet bodů jenom za složitost lineární s velikostí vstupu plus s velikostí abecedy.
mstop	3	Rozšiřte monádu z `Eval3.hs` tak, aby podporovala funkci `stop :: Vypocet ()`. Této funkci předáte string. Tato funkce přeruší výpočet v monádě a vrátí (uvnitř té monády samozřejmě) onen string a zbytek výpočtu. Uživatel může zbytek výpočtu kdykoliv spustit.
31. března 2009	Úkoly můžete odevzdávat do 21. dubna 2009, 10:40.
feq	3	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ář), najde rekurzivně všechny soubory a podadresáře obsahující daný řetězec a vypíše je, jeden na řádku.
coll	2.5	Vytvořte funkci `collision::(Integer->Integer)->(Integer,Integer)`, která dostane funkci f, o které ví, že nekonečná posloupnost $f(0), f(f(0)), f(f(f(0))),...$ neobsahuje nulu a skládá se pouze z konečného počtu různých čísel (čili je od nějaké doby periodická). Najděte $co nejrychleji a s pomocí co nejméně paměti dvě různé hodnoty x,y, aby f(x)=f(y)$.
tiso	2.5	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ů.
07. dubna 2009	Úkoly můžete odevzdávat do 28. dubna 2009, 10:40.
		Mějme binární stromy `BinTree a = N \| V (BinTree a) a (BinTree a)`.
bfst	2.5	Napište funkci `bfst :: BinTree a -> BinTree Int`, která dostane binární strom a vrátí binární strom stejného tvaru, který má vrcholy očíslované po vrstvách zleva doprava, tj. vrcholy jsou očíslované v pořadí, v jakém byste je navštívili při prohledávání do šířky. Plný počet bodů za lineární řešení.
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í.
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.
calc	3	Napište jednoduchou kalkulačku pro čísla s libovolnou přesností. Čtěte standardní vstup, každá řádka je jeden výraz, spočtěte ho a výsledek vypište. Výraz je klasický aritmetický výraz s operacemi `+ - * / %` (mínus jenom binární), závorkami, čísly a speciální proměnnou "last", ve které je uložen výsledek předchozího výrazu (a nula, pokud jde o první výraz nebo se minulý výraz nepovedlo naparsovat nebo vyhodnotit). Na parsování výrazu si napište parser typu toho z přednášky (výsledky parseru ukládejte do `Maybe` monády). Vše počítejte v `Integer`ech. Složitost by měla být lineární s velikostí vstupu.
14. dubna 2009	Úkoly můžete odevzdávat do 05. května 2009, 10:40.
blud	3	Na vstupu dostanete bludiště: dostanete čísla N,M a dále M řádek, každá obsahuje N nemezerových znaků. Velké `X` je zeď, tečka je volno, `M` je matfyzák, který je v bludišti právě jeden, a `m` je matfyzačka, která je v bludišti také právě jedna. Najděte a zobrazte nejkratší cestu mezi matfyzačkou a matfyzákem. Vypište bludiště ve stejném formátu, jenom zavináčem označte políčka, která leží na nejkratší cestě. Chci Ο(MN) nebo Ο(MN log(MN)).
primes	3	Napište funkci `primes :: [Integer]`, která vrací všechna prvočísla. Tato funkce musí fungovat velmi rychle, se 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.
21. dubna 2009	Úkoly můžete odevzdávat do 12. května 2009, 10:40.
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.
fft	3	Naprogramujte v Haskellu funkci `fft::Int->[Float]->[Complex Float]`. Tato funkce použitá jako `fft n seznam_2n_floatů` provede FFT, tj. rychlou Fourierovu transformaci na daných hodnotách. Složitost algoritmu musí být Ο(N log N).
28. dubna 2009	Úkoly můžete odevzdávat do 19. května 2009, 10:40.
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, která dostane kód obrázku a vrátí kód obrázku, který vznikne otočením doleva o 90^o. Na plný počet bodů musí být časová složitost lineární.
hangman	3	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ů.
05. května 2009	Úkoly můžete odevzdávat do 30. září 2009.
rost	3	Napište funkci `rost :: Ord a => [a] -> [a]`, která vrátí nejdelší rostoucí podposloupnost (nemusí být souvislá) zadané posloupnosti. Plný počet bodů jenom za O(N log N), za O(N²) jsou body dva.
acc	3	Napište funkci `acc :: (a->a->a) -> [a] -> IO a`. Pokud spustíte `acc f [x1,...,xn]`, je vaším úkolem vrátit hodotu x1 `f` x2 `f` ... `f` xn. Funkce `f` je asociativní. Výpočet co nejvíce zparalelizujte – měl by doběhnout v čase Ο(n)+log nΟ(čas vyhodnocení f)*, pokud máte k dispozici n procesorů. Nespoléhejte se na `par`.
chats	4	Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul `Network`. Jak v GHC tak v Hugsu byste ho měli mít nainstalovaný, dokumentace je tady. 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 nějak průběžně (nemusíte je zobrazovat když zrovna uživatel píše zprávu). Pokud to bude fungovat tak, že budete moct psát zprávu a 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, dostanete plus dva body (použít můžete 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.
logo	8	Implementujte jednoduchou variantu Loga v Haskellu. Vaše implementace musí být jeden modul, který definuje abstraktní typ `Program`, a dále exportuje primitiva `forward::Int->Program` (posune želvičku o daný počet kroků/pixelů), `left::Int->Program` (otočí želvičku doleva o daný počet stupňů), `pen::Bool->Program` (zda odteď želvička kreslí nebo ne) a `color::Color->Program` (barva pera, typ `Color` si navrhněte jak chcete). Dále musíte umět tato primitiva nejak spojovat. Osobně vám doporučuji, abyste si vytvořili modádu `ProgramM a` a pak zadefinovali `type Program=ProgramM ()`. Pak můžete psát programy pro želvičku jako spirala delka uhel = do forward delka left uhel when (delka<100) $ spirala (delka+2) uhel Nakonec exportujte z modulu funkci `runLogo::Int->Program->IO ()`, která dostane uživatelem definovaný program a ten spustí (otevře okno, provede ho a nechá okno otevřené než ho uživatel zavře). Obrázek zobrazujte průběžně. První parametr funkce je počet ms, jak dlouho se čeká po provedení `left, forward, pen, color`. Pro grafiku můžete použít co se vám zlíbí, třeba HGL, gtk2hs, wxHaskell, Glut+OpenGL, GLFW+OpenGL, SDL,...
logo2	3	Rozšiřte předchozí úlohu o funkci `run2Logos::Int->Program->Program->IO ()`, která dostane program dvou želviček a bude je provádět paralelně (provádí jeden program, poté, co on zavolá jednu z funkcí `forward,left,pen,color` počká daný počet ms (první parametr), pak tento program přeruší a provádí druhý program,...).
12. května 2009	Úkoly můžete odevzdávat do 30. září 2009.
kruskal	2.5	Implementujte Kruskalův algoritmus v čase O(N log² N).
dinic	3.5	Pomocí knihovny FGL implementujte Dinicův algoritmus na toky.

Stav (25. 05. 2018)

Jméno	Odevzdané úkoly	Body

Zpět