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


Obsah semináře

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

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

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

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

Doba a místo konání

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

Zápočet

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

Obsahy přednášek

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

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

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

U některých úkolů je uvedená časová složitost potřebná k získání plného počtu bodů. Můžete ale poslat libovolné řešení s polynomiální složitostí, nějaké body za něj budou vždy. Můžete klidně poslat nejprve pomalé řešení a později poslat vylepšenou verzi.
Datum
cvičení
IDBodyPopis
23. února 2011Úkoly můžete odevzdávat do 23. března 2011, 14:00.
wc1.5Napiš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-n1Napište skript, který se chová jako cat -n, tj. čte standardní vstup a každý řádek očísluje stylem printf("%6d\t%s, číslo_řádku, text_řádku).
  Pro další tři úlohy ji zadefinujte binární strom, který má hodnoty typu a v každém vrcholu, tj. data BinTree a = ....
l2t2Napište funkci, která dostane setřídění seznam a vytvoří z něj v lineárním čase perfektní binární vyhledávací strom. Perfektní znamená, že v každém vrcholu je velikost podstromu levého syna rovna velikosti podstromu pravého syna až na plus minus 1.
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.
onepass1Napište funkci, které dáte binární strom s Inty a ona vytvoří strom stejného tvaru, taktéž s Inty, který má v každém vrcholu uložený celočíselný průměr všech hodnot vrcholů původního stromu. Pozor, původní strom můžete projít jenom jednou a ten nový nemůžete procházet vůbec (jenom ho vytvořit)!
02. března 2011Úkoly můžete odevzdávat do 03. dubna 2011, 23:59.
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.
layers1.5Máte dáno data Tree a = Empty | Tree a [Tree a]. Napište funkci layers :: Tree a -> [a], která vrátí prvky stromu v pořadí po vrstvách, tj. stejně, jako by je navštívilo prohledávání do šířky spuštěné z kořene. Plný počet bodů za řešení v lineárním čase.
lcs2Napiš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ů).
bala2Napište funkci balanced::[Int]->[Int], která dostane seznam nul a jedniček a vrátí takovou nejdelší souvislou podposloupnost, ve které je stejně nul a jedniček. Plný počet bodů za Ο(N).
09. března 2011Úkoly můžete odevzdávat do 10. dubna 2011, 23:59.
sumall1.5Napište funkci sumall, která dostane libovolný nezáporný počet Integerů a vrátí jejich součet. K řešení potřebujete typové třídy a to, že -> je mimo jiné datový konstruktor.
isrot2Napište metodu isrot :: Eq a => [a] -> Bool, která zjistí, jestli je daný seznam roven nějaké své netriviální rotaci. Plný počet bodů za řešení v lineárním čase.
primes2.5Napište funkci primes :: [Integer], která vrací všechna prvočísla. Plný počet bodů za složitost Ο(N log log N) pro získání všech prvočísel do N, což je přesně složitost Eratosthenova síta. Na rozdíl od síta ale musíte vracet potenciálně nekonečně prvočísel. Za řešení v Ο(N √N) jeden bod.
split3Napište metodu split :: String -> [String] -> Maybe [String]. Ta dostane text bez mezer, složený z malých písmen anglické abecedy, a seznam platných slov. Výsledkem je text rozdělený na slova tak, aby každé bylo v daném slovníku. Pokud je možností rozdělení více, vyberte libovolné s nejmenším počtem slov. Plný počet bodů za řešení se složitostí Ο(délka_textu * délka_nejdelšího_slova + součet_délek_slov_slovníku).
16. března 2011Úkoly můžete odevzdávat do 13. dubna 2011, 14:00.
logger3Vytvořte monádu, která si pamatuje logy (ta, o které mluvil Zdeněk na konci hodiny). Definujte tedy datový typ data WithLog x = ..., dále vytvořte jeho instanci třídy Monad a funkce addLog :: String -> WithLog () a getLog :: WithLog x -> [String]. Nakonec by měl fungovat následující kód:
 mapWithLog f []     = return []
 mapWithLog f (x:xs) = do ys <- mapWithLog f xs
                          addLog $ "Zpracovavam prvek " ++ show x
                          return $ f x : ys
 main = print $ length $ getLog $ mapWithLog (+1) [1..30000]
usek2Napiš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.
tiso2Stromy 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ů.
dom2Napište funkci dom :: Ord a => [a] -> [(a, Int)], která dostane seznam a vrátí jeho kopii, která má navíc u každého prvku uloženo, kolik je ve zbytku seznamu prvků větších než tento aktuální. Tedy dom "brekeke" = zip "brekeke" [6, 0, 2, 0, 1, 0, 0]. Plný počet bodů za řešení v Ο(N log N).
23. března 2011Úkoly můžete odevzdávat do 20. dubna 2011, 14:00.
feq2.5Napiš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ář, tj. adresář jménem .), najde rekurzivně všechny soubory a podadresáře obsahující daný řetězec a vypíše je, jeden na řádku.
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.
06. dubna 2011Úkoly můžete odevzdávat do 04. května 2011, 14:00.
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 rotate :: String -> String, která dostane kód obrázku a vrátí kód obrázku, který vznikne otočením doleva o 90°. Na plný počet bodů musí být časová složitost lineární.
Příklad: rotate "(01(1011)1)" = "(110(0111))".
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.
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í.
hangman2.5Napište program, který s vámi hraje šibenici. Na začátku načte ze souboru words.txt seznam slov. Pak vždy jedno náhodně vybere a nechá vás postupně zadávat písmenka (žádné ne víckrát) a zobrazuje, která písmenka už jste uhodli. Po určitém počtu špatných pokusů skončíte a jste pověšeni. Když uhodnete, můžete pokračovat jiným slovem. Za asciiartové obrázky šibenice je bonus :–) BTW pokud máte chuť, můžete se podívat na knihovnu ansi-terminal, ale není to podmínka k získání bodů.
13. dubna 2011Úkoly můžete odevzdávat do 11. května 2011, 14:00.
chats4Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul Network. Server by měl poslouchat na zadaném portu. Připojit se může libovolný počet lidí. Když se někdo připojí, tak na první řádce napíše svůj nickname. Každá dalšá řádka od něj se pošle všem ostatním připojeným (těm, kteří už poslali nickname) ve formátu "nickname: řádka".
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 průběžně: když v půlce psaní přijde zpráva ze sítě, tak se odstraní rozepsaná zpráva, vypíše se místo ní přijatá a na další řádce se objeví rozepsaná a půjde dopsat (můžete použít například hSetBuffering stdin NoBuffering).
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.
diff3Napište program, který se bude chovat jako diff -u. Tedy program dostane na příkazové řádce jména dvou souborů. Jméno jednoho z těchto souborů může být -, což znamená standardní vstup. Na standardní výstup vypište diff těchto souborů ve formátu unified diff. Stejně jako diff -u je velikost kontextu 3, ale pokud uživatel zadá na začátku příkazové řádky -U num, změní se velikost kontextu na num (tedy -U 3 je implicitní). Složitost maximálně kvadratická. Pokud bude časová složitost Ο(počet řádek v obou souborech * velikost diffu) a paměťová Ο(velikost diffu na druhou), viz tento článek, dostanete další 3 body.
20. dubna 2011Úkoly můžete odevzdávat do 18. května 2011, 14:00.
func11Naprogramujte funkci func1 x l = map (\y -> y * x) l bez použití pojmenovaných argumentů.
func31Naprogramujte funkci func3 f l = l ++ map f l bez použití pojmenovaných argumentů.
func41Naprogramujte funkci func4 l = map (\y -> y+2) (filter (\z -> z `elem` [1..10]) (5:l)) bez použití pojmenovaných argumentů.
func51Naprogramujte funkci func5 f l = foldr (\x y -> f (y,x)) 0 l bez použití pojmenovaných argumentů.
dot3Naprogramujte funkci pro paralelní výpočet skalárního součinu. Funkce dot :: Array Int Int -> Array Int Int -> IO Int co nejrychleji vypočítá skalární součin daných polí, které obě musí mít stejné meze. Časová složitost by měla být ideálně Ο(N/P + log N), kde N je délka vektorů a P počet paralelně běžících vláken (pravděpodobně počet jader vašeho procesoru).
27. dubna 2011Úkoly můžete odevzdávat do 25. května 2011, 14:00.
insert2Napište funkci insert :: String -> ExpQ pro Template Haskell. Když ji použijete jako $(insert "a.txt"), tak se při kompilaci najde soubor a.txt a jeho obsah se vloží jako řetězec do místa volání.
sqrt3Napište funkci odmocni :: Integer -> Int -> ExpQ pro Template Haskell, že $(odmocni 2 100) se nahradí za odmocninu ze dvou na sto desetinných míst. Musíte se tedy nahradit číslem typu Rational, jehož jmenovatel bude 10100 a jehož čitatel bude takový, aby to byla požadovaná odmocnina.
psort3Napište funkci psort :: (Ord a) => Int -> [a] -> [a], která dostane k, posloupnost a setřídí ji, za předpokladu, že je tato posloupnost skoro setříděná – přesně můžete předpokládat, že každý prvek dané posloupnosti je nejvýš o k pozic mimo svojí pozici v setříděné posloupnosti. Optimalizujte časovou složitost, Ο(n log k) za tři body, Ο(nk) za jeden a půl, zbytek jako Ο(n log n) za půl bodu.

Stav (25. 05. 2011)

JménoOdevzdané úkolyBody
Vojtěch Bardiovskýwc(1.5), cat-n(0.5), perf(1), l2t(2), show(1), layers(0.75), lcs(2), bala(2), primes(1.5), isrot(1), usek(1), dom(1), logger(3), split(2), plen(1.5), hangman(2.5), quad(2), cut(2), psort(3)31.25
Tomáš Dvořákwc(1.5), layers(0.75), perf(1), l2t(2.5), cat-n(1), lcs(2), bala(1), show(1.5), isrot(1), primes(1), split(1.5), tiso(2), logger(3), dom(1), usek(1), plen(1), func1(1), func5(1), func4(1), func3(1), recon(2.5), quad(1.5)30.75
Tomáš Kučabala(2), cat-n(1), l2t(2.5), layers(1.5), lcs(2), perf(1), show(2), wc(1.5), isrot(1), sumall(1.5)16
Jitka Novotnácat-n(1), l2t(2), perf(1), wc(1.5), layers(1.5), show(1), onepass(1), lcs(2), bala(2), isrot(2), split(3), usek(1), tiso(1), dom(1), logger(3), find(2), plen(2), stree(3)31
Karel Polednawc(1.5), cat-n(1), l2t(2), perf(1), onepass(1), layers(1.5), show(1), lcs(2), bala(2), sumall(1.5), primes(3.5), split(3), logger(3), tiso(3), stree(3), func1(1), func3(1), func4(1), func5(1), insert(2), sqrt(3)39
Hujerwc(1.5), cat-n(1), l2t(2), perf(1), onepass(1), show(1), layers(1.5), lcs(2), bala(2), sumall(1.5), isrot(2), split(3), primes(2.5), logger(3), usek(2), tiso(2), dom(2), feq(2.5), find(2), plen(2), stree(3), quad(2), cut(2), recon(2.5), hangman(2.5), chats(4), chatc(2), web(4), diff(6), func1(1), func3(1), func4(1), func5(1), dot(3), insert(2), sqrt(3), psort(3)80.5

Zpět