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

Doba a místo konání

Konají se dvě paralelky, jedna v úterý v 15:40 v S8, druhá hned potom v úterý v 17:20 taktéž v S8 (nenechte se zmást SISem). Můžete je libovolně mixovat, na obou se bude probírat to samé.

Zápočet

Zápočet je možné získat za zápočtový program nebo za alespoň 30 bodů z domácích úkolů, úkolů bude vypsáno za alespoň 100 bodů. Úkoly odevzdávejte na můj mail a to pouze do následující přednášky (u některých úkolů budu ukazovat řešení; později se objeví nejspíš i dlouhodobější úkoly). A prosím neopisujte. Možná bude možné si místo zápočťáku ke konci semestru připravit referát, ale uvidíme, jak to naše dvě paralelky zvládnou (nic neslibuji:)

Obsahy přednášek

1. přednáška 26. února: opakování základů Haskellu; ptfp01(hs, ps, pdf), prelude(ps, pdf).
2. přednáška 4. března: líné vyhodnocování, typové třídy, standardní knihovna: ptfp02(hs, ps, pdf).
3. přednáška 11. března: monády: ptfp03(hs, ps, pdf) (s díky Zdeňkovi Dvořákovi); přehled všech standardních funkcí v IO monádě: io(ps, pdf).
4. přednáška 18. března: pravidla odvozování instancí, další nášup monád: ptfp04(hs, ps, pdf).
5. přednáška 25. března: různé typy polí v Haskellu, existenciální typy, polymorfismus vyšších řádů: ptfp05(hs, ps, pdf).
6. přednáška 1. dubna: výjimky a concurrence v Haskellu: ptfp06(hs, ps, pdf).
7. přednáška 8. dubna: STM monáda, sekvenční a paralelní strategie výpočtu, Template Haskell: ptfp07(hs, ps, pdf).
8. přednáška 15. dubna: funkcionální datové struktury, líná amortizace, fronty a jejich varianty: ptfp08(hs, ps, pdf).
9. přednáška 22. dubna: arrows: ptfp09(hs, ps, pdf).

Budoucí přednášky:

10. přednáška 29. dubna: překvapení :)
11. přednáška 06. května: referáty o QuickCheck (testování) a Haskore (hudba)
12. přednáška 13. května: referát o Funkcionálním reaktivním programování (programování reaktivních systémů, například robotů)
13. přednáška 20. května: referáty o Pan (funkcionální obrázky) a HRay (raytracing)

Referáty

6. května	QuickCheck - Peter Bašista - 45m
6. května	Haskore - Tomáš Kraut - 45m
13. května	Functional reactive programming - Tomáš Petříček - 90m
20. května	Pan - Jiří Kunčar - 45m
20. května	HRay - Čestmír Houška - 45m

Referáty je třeba říct v obou paralelkách. Budete na ně mít projektor, ale notebook si prosím doneste sami. Můžu zkusit sehnat i fakultní, ale nezaručuji se za jeho hardwarový ani softwarový stav :) Odměnou za referát vám budiž zápočet bez potřeby dělání dalších domácích úkolů.

Domácí úkoly (28. 06. 2010)

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, 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
26. února 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)!
4. března show 1 Máte dáno data Tree a = Empty | Tree a [Tree a]. Napište ručně instanci instance Show (Tree a), aby fungovala v lineárním čase.
n235 1.5 Napište funkci, která bude vracet nekonečný seznam rostoucích čísel, která nemají jiné prvočíselné dělitele než dvojku, trojku a pětku, 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 zadané seznamy spočítá délku jejich nejdelšího společného souvislého podseznamu (za nesouvislý je bonus). Časová složitost by měla být nejvíc O(součin délek těchto seznamů).
deriv 2 Napište jednoduché derivovátko::String->String, derivuje se podle x. Musí umět alespoň + * ^ sin cos log x a čísla. Operátory musí jít zadávat infixově a musí funovat priority + * ^, takže 3 + 4 * 5 ^ 2 je 3 + (4 * (5^2)). Snažte si co nejvíc ulehčit práci pomocí třídy Read.Třída Read bohužel neumí parsovat operátory podle asociativity a ještě je ohavně pomalá, ale pro získání bodů z tohoto úkolu stačí, tj. nemusíte umět naparsovat 5 + 5 + 5. Lepší parsery se naučíme používat / psát časem :–)
Na následující úložky smíte použít -fglasgow-exts (v Hugsu -98). Uvědomte si, že (->) je typový konstruktor.
Za první odevzdanou z následujících třech úloh dostanete dva body, za druhou a třetí odevzdanou jeden bod (jsou si navzájem docela podobné).
sumall 1-2 Napište funkci sumall, která dostane libovolný nezáporný počet Intů a vrátí jejich součet.
maxall 1-2 Napište funkci maxall, která dostane libovolný kladný počet porovnatelných prvků a vrátí jejich maximum. Všechny parametry musí být stejného typu, ale ten typ je libovolný porovnatelný.
mulall 1-2 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ě).
11. března 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.
mstop 2 Rozšiřte monádu z Eval2.hs tak, aby podporovala funkci stop. 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. Proveďte to tak, že přidáte třídu MonadStop, která obsahuje funkci stop::String->m (). Samozřejmě je třeba upravit typ Result a její monádové instance (Monad i MonadStop).
wrap 2 Vytvořte funkci wrap::f->IO () která dostane libovolnou funkci. Všechny potřebné parametry funkce f načte wrap ze standardního vstupu (každý parametr na jedné řádce) a výstup funkce f vypíše wrap na standardní výstup. Načítat a vypisovat musíte umět Int, [Int] (na jedné řádce oddělené mezerami) a String (celá řádka i s mezerami).
18. března 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^2) za bod, O(N) za dva.
usek 1-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^2) za bod, O(N) za dva body.
demo 2 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.
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.
Následuje úložka pro monadické šílence.
mstep 4 Napište (nebo zkopírujte z minulých úloh) parser, který načítá aritmetický výraz s + - * / % ^, závorkami a čísly typu Integer. Výraz si uložte ve stromové struktuře, ale zatím nevyhodnocujte. Implementujte monádu, která umožní vyhodnotit výraz, přičemž smí spotřebovat nanejvýš zadaný počet kroků. Na vyhodnocení + - je třeba 1 krok, na vyhodnocení * / % je třeba 7 kroků, na vyhodnocení ^ je třeba 13 kroků (vyhodnocení čísla a závorky je zdarma). Pokud lze výpočet provést v zadaném počtu kroků, vrátí se výsledek, pokud ne, vrátí se zbývající výpočet (co ještě nebylo uděláno). Také napište instanci MonadPlus, která umožní provádět dva výpočty paralelně, tj. vrátí výsledek toho, který skončí v menším počtu kroků. Detaily, které zde nejsou, si můžete domyslet. Složitost musí být libovolná polynomiálním, plný počet za řešení, které se mi nebude hnusit (a bonusy za řešení, které se mi budou líbit).
25. března blud 2 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 O(MN) nebo O(MN log(MN)).
coll 2 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).
subw 2.5 Dostanete řetězec délky N a dále celé číslo K. Vaším úkolem je nalézt nejčastější souvislý podřetězec délky K. Plný počet jenom za řešení v čase O(NK) a lepší.
ppow 2.5 Vytvořte funkci perfpowers::[Integer], která vrací setříděný seznam všech perfektních mocnin. Perfektní mocnina je číslo větší než jedna tvaru prvočíslo na itou. Prvních pár členů tedy je [2,3,4,5,7,8,9,11,...]. Časová složitost získání prvních N členů musí být nejvýše O(N log²N) na plný počet bodů, ale každé polynomiální řešení dostane alespoň nějaké body.
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ž O(N²), kde N je počet vrcholů většího ze stromů.
Úložka pro monadické šílence zůstala z minula.
mstep 4 Napište (nebo zkopírujte z minulých úloh) parser, který načítá aritmetický výraz s + - * / % ^, závorkami a čísly typu Integer. Výraz si uložte ve stromové struktuře, ale zatím nevyhodnocujte. Implementujte monádu, která umožní vyhodnotit výraz, přičemž smí spotřebovat nanejvýš zadaný počet kroků. Na vyhodnocení + - je třeba 1 krok, na vyhodnocení * / % je třeba 7 kroků, na vyhodnocení ^ je třeba 13 kroků (vyhodnocení čísla a závorky je zdarma). Pokud lze výpočet provést v zadaném počtu kroků, vrátí se výsledek, pokud ne, vrátí se zbývající výpočet (co ještě nebylo uděláno). Také napište instanci MonadPlus, která umožní provádět dva výpočty paralelně, tj. vrátí výsledek toho, který skončí v menším počtu kroků. Detaily, které zde nejsou, si můžete domyslet. Složitost musí být libovolná polynomiálním, plný počet za řešení, které se mi nebude hnusit (a bonusy za řešení, které se mi budou líbit).
1. dubna acc 3 Napište funkci acc::(a->a->a)->[a]->a nebo acc::(a->a->a)->[a]->IO a. Pokud spustíte acc f [x₁,...,x_n], je vaším úkolem vrátit hodotu x₁ `f` x₂ `f` ... `f` x_n. Funkce f je asociativní a komutativní, takže je jedno v jakém pořadí ji budete aplikovat. Předpokládejte, že máte n procesorů, takže výpočet co nejvíce zparalelizujte - měl by doběhnout v čase O(n)+log n*O(čas vyhodnocení f) (pokud mátě oněch n procesorů).
rost 3 Napište funkci rost::(Ord a)=>[a]->[a], která vrátí nejdelší rostoucí podposloupnost (souvislou nebo nesouvislou) zadané posloupnosti. Plný počet bodů jenom za O(N log N), za O(N²) jsou body dva.
fft 2 Naprogramujte v Haskellu funkci FFT::Int->[Float]->[Complex Float]. Tato funkce použitá jako FFT n seznam_2ⁿ_floatů provede FFT na daných hodnotách. Složitost algoritmu musí být O(N log N).
Následuje bušící úložka, která je spíše technická než náročná. Bude na ní čas dva týdny místo jednoho.
chats 4 Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul Network. Pokud ho nemáte nainstalovaný, najdete ho 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). Za použití readline a možnosti přijímat zprávy od ostatních i při psaní zprávy můžete dostat až dvoubodový bonus.
8. dubna Z minula:
rost 3 Napište funkci rost::(Ord a)=>[a]->[a], která vrátí nejdelší rostoucí podposloupnost (souvislou nebo nesouvislou) zadané posloupnosti. Plný počet bodů jenom za O(N log N), za O(N²) jsou body dva.
chats 4 Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul Network. Pokud ho nemáte nainstalovaný, najdete ho 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). Za použití readline a možnosti přijímat zprávy od ostatních i při psaní zprávy můžete dostat až dvoubodový bonus.
Nové:
inst 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 ten se jako řetězec vloží tam, kde bylo insert zavoláno.
2tup 1 Napište funkci totup::Int->ExpQ pro Template Haskell, že když $(totup 5) dostane neprázdný seznam, vrátí jako pětici jeho prvních 5 prvků. Pokud jich seznam měl méně, tak je opakujte. Tj. $(totup 5) [1,2] vrátí (1,2,1,2,1).
sqrt 3 Napište funkci odmocni::Int->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^100 a jehož čitatel bude takový, aby to byla požadovaná odmocnina. Časová složitost $(odmocni k n) musí být nejvýš O(n*(násobení čísel o (n+log k) bitech)).
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.
15. dubna Z minula:
inst 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 ten se jako řetězec vloží tam, kde bylo insert zavoláno.
2tup 1 Napište funkci totup::Int->ExpQ pro Template Haskell, že když $(totup 5) dostane neprázdný seznam, vrátí jako pětici jeho prvních 5 prvků. Pokud jich seznam měl méně, tak je opakujte. Tj. $(totup 5) [1,2] vrátí (1,2,1,2,1).
sqrt 3 Napište funkci odmocni::Int->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^100 a jehož čitatel bude takový, aby to byla požadovaná odmocnina. Časová složitost $(odmocni k n) musí být nejvýš O(n*(násobení čísel o (n+log k) bitech)).
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.
psrt 3.5 Napište funkci psort::(Ord a)=>[a]->[a], která setřídí danou posloupnost. Předpokládejte, že posloupnost je skoro setříděná v tom smyslu, že každý prvek je nejvýš o k pozic mimo (tedy pro každý prvek je rozdíl jeho indexů v zadané a setříděné posloupnosti nejvýš k). Optimalizujte časovou složitost, tj. O(n log k) za tři a půl bodu, O(nk) za dva a zbytek jako O(n log n) a horší za jeden.
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,...).
zkouškové Tyto úkoly je možné odevzdávat do konce školního roku, tj. do konce září.
sqrt 3 Napište funkci odmocni::Int->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^100 a jehož čitatel bude takový, aby to byla požadovaná odmocnina. Časová složitost $(odmocni k n) musí být nejvýš O(n*(násobení čísel o (n+log k) bitech)).
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.
psrt 3.5 Napište funkci psort::(Ord a)=>[a]->[a], která setřídí danou posloupnost. Předpokládejte, že posloupnost je skoro setříděná v tom smyslu, že každý prvek je nejvýš o k pozic mimo (tedy pro každý prvek je rozdíl jeho indexů v zadané a setříděné posloupnosti nejvýš k). Optimalizujte časovou složitost, tj. O(n log k) za tři a půl bodu, O(nk) za dva a zbytek jako O(n log n) a horší za jeden.
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,...).
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 2k₁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í.
abcd 4 Abeceda ztraceného národa Atlantiďanů se skládala z nějaké podmnožiny Unicode znaků. Bohužel už není známo uspořádání těchto znaků, ale víte, že bylo lineární. Získali jste kus slovníku, tedy několik slov, které jsou lexikograficky setříděné. Předpokládejte, že písmena těchto slov jsou celá atlantidská abeceda. Vaším úkolem je nalézt lineární uspořádání písmen v abecedě, případně říct, že ho z daných slov nejde stanovit.
Napište tedy funkci abcd::[String]->Maybe [Char], která dostane lexikograficky setříděná slova a pokud je možné určit jednoznačné lineární uspořádání všech písmen v těchto slovech, vrátí ho, jinak vrátí Nothing. Můžete předpokládat, že data jsou konzistentní.

Datum cvičení	ID	Body	Popis
26. února	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)!
4. března	show	1	Máte dáno `data Tree a = Empty \| Tree a [Tree a]`. Napište ručně instanci `instance Show (Tree a)`, aby fungovala v lineárním čase.
n235	1.5	Napište funkci, která bude vracet nekonečný seznam rostoucích čísel, která nemají jiné prvočíselné dělitele než dvojku, trojku a pětku, 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 zadané seznamy spočítá délku jejich nejdelšího společného souvislého podseznamu (za nesouvislý je bonus). Časová složitost by měla být nejvíc O(součin délek těchto seznamů).
deriv	2	Napište jednoduché derivovátko`::String->String`, derivuje se podle `x`. Musí umět alespoň `+ * ^ sin cos log x` a čísla. Operátory musí jít zadávat infixově a musí funovat priority `+ * ^`, takže `3 + 4 * 5 ^ 2` je `3 + (4 * (5^2))`. Snažte si co nejvíc ulehčit práci pomocí třídy `Read`.Třída `Read` bohužel neumí parsovat operátory podle asociativity a ještě je ohavně pomalá, ale pro získání bodů z tohoto úkolu stačí, tj. nemusíte umět naparsovat 5 + 5 + 5. Lepší parsery se naučíme používat / psát časem :–)
		Na následující úložky smíte použít `-fglasgow-exts` (v Hugsu `-98`). Uvědomte si, že `(->)` je typový konstruktor. Za první odevzdanou z následujících třech úloh dostanete dva body, za druhou a třetí odevzdanou jeden bod (jsou si navzájem docela podobné).
sumall	1-2	Napište funkci `sumall`, která dostane libovolný nezáporný počet `Int`ů a vrátí jejich součet.
maxall	1-2	Napište funkci `maxall`, která dostane libovolný kladný počet porovnatelných prvků a vrátí jejich maximum. Všechny parametry musí být stejného typu, ale ten typ je libovolný porovnatelný.
mulall	1-2	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ě).
11. března	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.
mstop	2	Rozšiřte monádu z `Eval2.hs` tak, aby podporovala funkci `stop`. 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. Proveďte to tak, že přidáte třídu `MonadStop`, která obsahuje funkci `stop::String->m ()`. Samozřejmě je třeba upravit typ `Result` a její monádové instance (`Monad` i `MonadStop`).
wrap	2	Vytvořte funkci `wrap::f->IO ()` která dostane libovolnou funkci. Všechny potřebné parametry funkce `f` načte `wrap` ze standardního vstupu (každý parametr na jedné řádce) a výstup funkce `f` vypíše `wrap` na standardní výstup. Načítat a vypisovat musíte umět `Int`, `[Int]` (na jedné řádce oddělené mezerami) a `String` (celá řádka i s mezerami).
18. března	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^2) za bod, O(N) za dva.
usek	1-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^2) za bod, O(N) za dva body.
demo	2	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.
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.
		Následuje úložka pro monadické šílence.
mstep	4	Napište (nebo zkopírujte z minulých úloh) parser, který načítá aritmetický výraz s `+ - * / % ^`, závorkami a čísly typu `Integer`. Výraz si uložte ve stromové struktuře, ale zatím nevyhodnocujte. Implementujte monádu, která umožní vyhodnotit výraz, přičemž smí spotřebovat nanejvýš zadaný počet kroků. Na vyhodnocení `+ -` je třeba 1 krok, na vyhodnocení `* / %` je třeba 7 kroků, na vyhodnocení `^` je třeba 13 kroků (vyhodnocení čísla a závorky je zdarma). Pokud lze výpočet provést v zadaném počtu kroků, vrátí se výsledek, pokud ne, vrátí se zbývající výpočet (co ještě nebylo uděláno). Také napište instanci MonadPlus, která umožní provádět dva výpočty paralelně, tj. vrátí výsledek toho, který skončí v menším počtu kroků. Detaily, které zde nejsou, si můžete domyslet. Složitost musí být libovolná polynomiálním, plný počet za řešení, které se mi nebude hnusit (a bonusy za řešení, které se mi budou líbit).
25. března	blud	2	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 O(MN) nebo O(MN log(MN)).
coll	2	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).
subw	2.5	Dostanete řetězec délky N a dále celé číslo K. Vaším úkolem je nalézt nejčastější souvislý podřetězec délky K. Plný počet jenom za řešení v čase O(NK) a lepší.
ppow	2.5	Vytvořte funkci `perfpowers::[Integer]`, která vrací setříděný seznam všech perfektních mocnin. Perfektní mocnina je číslo větší než jedna tvaru prvočíslo na itou. Prvních pár členů tedy je `[2,3,4,5,7,8,9,11,...]`. Časová složitost získání prvních N členů musí být nejvýše O(N log²N) na plný počet bodů, ale každé polynomiální řešení dostane alespoň nějaké body.
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ž O(N²), kde N je počet vrcholů většího ze stromů.
		Úložka pro monadické šílence zůstala z minula.
mstep	4	Napište (nebo zkopírujte z minulých úloh) parser, který načítá aritmetický výraz s `+ - * / % ^`, závorkami a čísly typu `Integer`. Výraz si uložte ve stromové struktuře, ale zatím nevyhodnocujte. Implementujte monádu, která umožní vyhodnotit výraz, přičemž smí spotřebovat nanejvýš zadaný počet kroků. Na vyhodnocení `+ -` je třeba 1 krok, na vyhodnocení `* / %` je třeba 7 kroků, na vyhodnocení `^` je třeba 13 kroků (vyhodnocení čísla a závorky je zdarma). Pokud lze výpočet provést v zadaném počtu kroků, vrátí se výsledek, pokud ne, vrátí se zbývající výpočet (co ještě nebylo uděláno). Také napište instanci MonadPlus, která umožní provádět dva výpočty paralelně, tj. vrátí výsledek toho, který skončí v menším počtu kroků. Detaily, které zde nejsou, si můžete domyslet. Složitost musí být libovolná polynomiálním, plný počet za řešení, které se mi nebude hnusit (a bonusy za řešení, které se mi budou líbit).
1. dubna	acc	3	Napište funkci `acc::(a->a->a)->[a]->a` nebo `acc::(a->a->a)->[a]->IO a`. Pokud spustíte `acc f [x₁,...,x_n]`, je vaším úkolem vrátit hodotu x₁ `f` x₂ `f` ... `f` x_n. Funkce f je asociativní a komutativní, takže je jedno v jakém pořadí ji budete aplikovat. Předpokládejte, že máte n procesorů, takže výpočet co nejvíce zparalelizujte - měl by doběhnout v čase O(n)+log nO(čas vyhodnocení f)* (pokud mátě oněch n procesorů).
rost	3	Napište funkci `rost::(Ord a)=>[a]->[a]`, která vrátí nejdelší rostoucí podposloupnost (souvislou nebo nesouvislou) zadané posloupnosti. Plný počet bodů jenom za O(N log N), za O(N²) jsou body dva.
fft	2	Naprogramujte v Haskellu funkci `FFT::Int->[Float]->[Complex Float]`. Tato funkce použitá jako `FFT n seznam_2ⁿ_floatů` provede FFT na daných hodnotách. Složitost algoritmu musí být O(N log N).
		Následuje bušící úložka, která je spíše technická než náročná. Bude na ní čas dva týdny místo jednoho.
chats	4	Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul `Network`. Pokud ho nemáte nainstalovaný, najdete ho 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). Za použití readline a možnosti přijímat zprávy od ostatních i při psaní zprávy můžete dostat až dvoubodový bonus.
8. dubna			Z minula:
rost	3	Napište funkci `rost::(Ord a)=>[a]->[a]`, která vrátí nejdelší rostoucí podposloupnost (souvislou nebo nesouvislou) zadané posloupnosti. Plný počet bodů jenom za O(N log N), za O(N²) jsou body dva.
chats	4	Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul `Network`. Pokud ho nemáte nainstalovaný, najdete ho 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). Za použití readline a možnosti přijímat zprávy od ostatních i při psaní zprávy můžete dostat až dvoubodový bonus.
		Nové:
inst	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 ten se jako řetězec vloží tam, kde bylo `insert` zavoláno.
2tup	1	Napište funkci `totup::Int->ExpQ` pro Template Haskell, že když `$(totup 5)` dostane neprázdný seznam, vrátí jako pětici jeho prvních 5 prvků. Pokud jich seznam měl méně, tak je opakujte. Tj. `$(totup 5) [1,2]` vrátí `(1,2,1,2,1)`.
sqrt	3	Napište funkci `odmocni::Int->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^100` a jehož čitatel bude takový, aby to byla požadovaná odmocnina. Časová složitost `$(odmocni k n)` musí být nejvýš O(n(násobení čísel o (n+log k) bitech))*.
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.
15. dubna			Z minula:
inst	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 ten se jako řetězec vloží tam, kde bylo `insert` zavoláno.
2tup	1	Napište funkci `totup::Int->ExpQ` pro Template Haskell, že když `$(totup 5)` dostane neprázdný seznam, vrátí jako pětici jeho prvních 5 prvků. Pokud jich seznam měl méně, tak je opakujte. Tj. `$(totup 5) [1,2]` vrátí `(1,2,1,2,1)`.
sqrt	3	Napište funkci `odmocni::Int->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^100` a jehož čitatel bude takový, aby to byla požadovaná odmocnina. Časová složitost `$(odmocni k n)` musí být nejvýš O(n(násobení čísel o (n+log k) bitech))*.
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.
psrt	3.5	Napište funkci `psort::(Ord a)=>[a]->[a]`, která setřídí danou posloupnost. Předpokládejte, že posloupnost je skoro setříděná v tom smyslu, že každý prvek je nejvýš o k pozic mimo (tedy pro každý prvek je rozdíl jeho indexů v zadané a setříděné posloupnosti nejvýš k). Optimalizujte časovou složitost, tj. O(n log k) za tři a půl bodu, O(nk) za dva a zbytek jako O(n log n) a horší za jeden.
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,...).
zkouškové			Tyto úkoly je možné odevzdávat do konce školního roku, tj. do konce září.
sqrt	3	Napište funkci `odmocni::Int->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^100` a jehož čitatel bude takový, aby to byla požadovaná odmocnina. Časová složitost `$(odmocni k n)` musí být nejvýš O(n(násobení čísel o (n+log k) bitech))*.
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.
psrt	3.5	Napište funkci `psort::(Ord a)=>[a]->[a]`, která setřídí danou posloupnost. Předpokládejte, že posloupnost je skoro setříděná v tom smyslu, že každý prvek je nejvýš o k pozic mimo (tedy pro každý prvek je rozdíl jeho indexů v zadané a setříděné posloupnosti nejvýš k). Optimalizujte časovou složitost, tj. O(n log k) za tři a půl bodu, O(nk) za dva a zbytek jako O(n log n) a horší za jeden.
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,...).
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 2k₁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í.
abcd	4	Abeceda ztraceného národa Atlantiďanů se skládala z nějaké podmnožiny Unicode znaků. Bohužel už není známo uspořádání těchto znaků, ale víte, že bylo lineární. Získali jste kus slovníku, tedy několik slov, které jsou lexikograficky setříděné. Předpokládejte, že písmena těchto slov jsou celá atlantidská abeceda. Vaším úkolem je nalézt lineární uspořádání písmen v abecedě, případně říct, že ho z daných slov nejde stanovit. Napište tedy funkci `abcd::[String]->Maybe [Char]`, která dostane lexikograficky setříděná slova a pokud je možné určit jednoznačné lineární uspořádání všech písmen v těchto slovech, vrátí ho, jinak vrátí `Nothing`. Můžete předpokládat, že data jsou konzistentní.

Stav (25. 05. 2018)

Jméno	Odevzdané úkoly	Body

Zpět