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

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í
IDBodyPopis
03. března 2009Úkoly můžete odevzdávat do 24. března 2009, 10:40.
wc2Napiš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-n2Napiš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 = ....
l2t2Napiš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.
perf1Vytvořte funkci, které zadáte mocninu dvojky n=2k a ona vytvoří úplný binární strom s k hladinami. V každém vrcholu je číslo 1. Optimalizujte na časovou složitost.
onepass2Napiš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.
show1Má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.
n2351.5Napište funkci, která vrací nekonečný seznam rostoucích čísel, která nemají jiné prvočíselné dělitele než 2, 3, 5, tj. čísel tvaru 2i * 3j * 5k. Složitost získání prvních K prvků musí být O(K).
lcs1.5Napiš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ů).
sumall1.5Napište funkci sumall, která dostane libovolný nezáporný počet Intů a vrátí jejich součet.
printf1.5Napiš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.
mulall1.5Navrhně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.
pyth1.5Napište funkci pyth::[(Int,Int,Int)], která bude vracet všechny pythagorejské trojice, tj. trojice kladných přirozených čísel, že a2+b2=c2. 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).
ls2Napište příkaz ls, který dostane na příkazové řádce několik adresářů, každý z nich rekurzivně projde a vypíše.
diff3Napiš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.
bala1-2Napiš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(N2) za bod, O(N) za dva a půl.
usek1-2.5Napiš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(N2) za bod, O(N) za dva a půl bodu.
demo3Napiš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.
mstop3Rozš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.
feq3Napiš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.
find2Napiš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.
coll2.5Vytvoř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)$.
tiso2.5Stromy 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ž Ο(N2), 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).
bfst2.5Napiš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í.
recon2.5Napiš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í.
cut2Napiš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.
calc3Napiš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.
blud3Na 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)).
primes3Napiš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.
plen2Napiš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.
stree3Na 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.
fft3Naprogramujte 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.
quad2Na vstupu je černobílý obrázek v rozlišení 2n x 2n 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 (k1k2k3k4), kde ki 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 90o. Na plný počet bodů musí být časová složitost lineární.
hangman3Napiš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.
rost3Napiš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(N2) jsou body dva.
acc3Napiš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.
chats4Napiš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".
chatc2Napiš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).
web4Napiš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.
logo8Implementujte 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,...
logo23Rozš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.
kruskal2.5Implementujte Kruskalův algoritmus v čase O(N log2 N).
dinic3.5Pomocí knihovny FGL implementujte Dinicův algoritmus na toky.

Stav (07. 09. 2009)

JménoOdevzdané úkolyBody
Vladimír Čunátl2t(2), perf(1), onepass(0.5), n235(1.5), lcs(1.5), pyth(1.5), diff(3), bala(2), usek(2.5), tiso(2), bfst(2.5), recon(2.5), primes(3), blud(3), plen(2), rost(3)33.5
Víťa Čížekhangman(5), chats(4), kruskal(2.5), rost(3), stree(3), cut(3), web(4), chatc(5), plen(0.5)30
Tomáš Humlperf(1), l2t(1.5), show(0.75), wc(2), cat-n(2), demo(2.5), bala(1.5), tiso(2), bfst(1.5), recon(2), primes(1.5), blud(3), plen(1.5), stree(2), rost(1), kruskal(4.25)30
Jindřich Ivánekwc(2), l2t(2), perf(1), onepass(1), n235(1), lcs(0.5), show(1), pyth(1.5), ls(2), diff(3), demo(3), cut(2), hangman(4), logo(8)32
Roman Smržwc(2), cat-n(2), l2t(2), perf(1), onepass(2), sumall(1.5), mulall(1.5), demo(3), bfst(2.5), cut(2), blud(3), quad(1.5), hangman(5), arrows(1)30
Peter Šufliarskyl2t(2), perf(1), wc(2), diff(4), ls(2), pyth(1), bala(1), demo(3), usek(1), find(3), recon(2), hangman(4), quad(1), rost(3)30
Hujerwc(2), cat-n(2), l2t(2), perf(1), onepass(2), show(1), n235(1.5), lcs(1.5), sumall(1.5), printf(1.5), maxall(), pyth(1.5), ls(2), diff(3), bala(2), usek(2.5), demo(3), mstop(3), feq(3), find(2), coll(2.5), tiso(2.5), bfst(2.5), recon(2.5), cut(2), calc(3), blud(3), primes(3), plen(2), stree(3), fft(3), rost(3), quad(2), hangman(3), acc(3), chats(4), chatc(4), web(4), logo(8), logo2(3), kruskal(2.5), dinic(3.5)107

Zpět