Programovací jazyky OCaml a F#, PRG049


Obsah semináře

Budeme se zaobírat funkcionálním programováním v jazycích z rodiny ML, především v jazycích OCaml a F#. Tyto jazyky mohou být užitečné v praxi, protože nejsou čistě funkcionální (můžete říct co se vyhodnocuje striktně a co líně, můžete používat imperativní konstrukce a funkce se side-efekty), přesto je možné v nich elegantně funkcionálně programovat. A nakonec nejdůležitější poznámka: v OCaml-u nejsou monády :)

Doba a místo konání

Seminář se koná ve středu v 15:40 na Malé Straně v SW1.

Zápočet

Pro získání zápočtu je třeba získat 30 bodů. Body je možné získávat za domácí úkoly (těch bude vypsáno alespoň za 80 bodů), za referáty (předpokládám tak jeden dva) a za zápočtový program (je možné se domluvit na obtížnosti 1 až 30 bodů, pro zájemce i více :). Body se sčítají.

Kde sehnat OCaml a F#

OCaml je možné stáhnout zde, přičemž zde je dokumentace.

F# je možné stáhnout zde, najděte odkaz 'Download the F# CTP'. Kromě překladače F# budete potřebovat .NET verze alespoň 2.0. Zde je popis jazyka a seznam funkcí.

Můžete použít .NET od MS, pak si stáhněte rovnou Microsoft Visual Studio Shell 2008 (integrated mode), tím získáte i IDE. VS Shell je zdarma. V tomto případě si vyberte .msi variantu překladače F#.

Dále můžete použít Mono 2.0. Mono doporučuji verze alespoň 2.0.1. Na widlich funguje bez problémů, na Linuxu ve fsi nefungují šipky a konzole vypisuje korektně až od druhého řádku. Začněte tedy zmáčknutím 'středník středník enter'. V tomto případě si vyberte .zip variantu překladače F#.

Nástroje pro parsování pro OCaml a F#

K tokenizování můžete použít ocamllex, což je generátor tokenizátorů. Dokumentace je zde. S kompilátorem F# je dodáván reimplementace tohoto nástroje jménem fslex, který má stejný formát vstupu. Další informace o něm si přečtěte tady.

Nad tokenizovátkem je možné postavit parser. Ke generování parserů lze použít ocamlyacc, jehož dokumentace je tady. Stejně jako předtím je v F# reimplementován jako fsyacc, o němž si můžete přečíst zde.

Obsahy přednášek

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

Prosím posílejte úkoly jako textové přílohy mailu, nezabalujte je. Lépe se mi opravují. Pokud není řečeno jinak, můžete si vybrat, jestli chcete dělat domácí úkoly F# i v OCamlu.

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
08. října 2008Úkoly můžete odevzdávat do 05. listopadu 2008, 15:30.
pow1Napište operátor mocnění typu int -> int -> int. Umocnění na n-tou by mělo použít Ο(log n) násobení. Zvolte vhodné jméno aby měl operátor správnou prioritu :)
bitsum1Napište funkci typu int -> int, která v 31-bitovém intu posčítá bity, tj. vrátí počet jedničkových bitů v daném 31-bitovém intu. Implementace, která použije řádově Ο(log b) operací pro číslo o b bitech (v našem případě je b=31), dostane drobný bonus, a implementace, která použije řádově Ο(log log b) operací, dostane ještě něco navíc.
15. října 2008Úkoly můžete odevzdávat do 12. listopadu 2008, 15:30.
sort2.5Napište libovolné třídění čísel s průměrnou složitostí Ο(N log N), přičemž se snažte, abyste potřebovali zásobník o řádové velikosti nejvýš log N (pokud potřebujete zásobník o velikosti Ω(N), strhnu vám bod).
  Pro následující úložku předpokládejte type 'a tree = Nil | Node of 'a * ('a tree) * ('a tree).
opti3.5Napište funkci typu ('a * int) list -> 'a tree, která se seznamu (ai, ci) vytvoří optimální vyhledávací strom vzhledem k ai. To je takový binární vyhledávací strom, že pokud se na prvek ai ptáte ci-krát, celkový čas strávený procházením stromu je minimální.
Plný počet bodů jenom za řešení v Ο(N2), za Ο(N3) je 2.5 bodů, za horší alespoň 1.5 bodu.
22. října 2008Úkoly můžete odevzdávat do 19. listopadu 2008, 15:30.
ssrt3Napište funkci ssort : string array -> unit, která dostane na vstupu N řetězců o celkovém počtu P písmen, a setřídí je v čase Ο(P + A), kde A je velikost abecedy (tj. 256 pro nás teď není konstanta). Složitost Ο(P * A) dostane dva body, horší bod.
rost2.5Napište funkci rost : 'a list -> 'a list, která pro danou posloupnost najde nejdelší rostoucí podposloupnost (ne nutně souvislou) a tu vrátí. Plný počet bodů za Ο(N log N) řešení, za Ο(N2) 1.5 bodu a za ostatní polynomiální řešení bod.
Hint: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
maxis2.5Mějme obecné stromy typu type 'a tree = Node of 'a * 'a tree list. Napište funkci maxis : 'a tree -> 'a list, která najde libovolnou největší možnou množinu vrcholů takovou, že mezi těmito vrcholy nevede žádná hrana, a vrátí hodnoty v těchto vrcholech.
rsam2Napište funkci rsamodules : int -> int list, která vrátí daný počet nejmenších RSA modulů. Číslo je RSA modul, pokud je to součin dvou prvočísel. Plný počet bodů jenom za lepší řešení než Ο((N log N)1.5), za pěkné nebo velmi rychlé řešení může být bonus.
29. října 2008Úkoly můžete odevzdávat do 26. listopadu 2008, 15:30.
cenzor2.5Napište funkci cenzor : string -> string -> string, která ze druhého zadaného slova vymaže všechny výskyty prvního slova. Pozor na to, že smazáním jednoho slova může vzniknout další zakázané slovo, třeba cenzor "bug" "bububuggg".
Hint: KMP (http://mj.ucw.cz/vyuka/0708/ads2/ads2.ps strana 26) a po smazání slov se "vrátit" o dost zpět.
median2.5Napište funkci median : int list -> int, která spočítá medián dané nesetříděné posloupnosti. Za lineární složitost dostanete plný počet bodů, za průměrně lineární složitost dostanete 1.5 bodu a za horší složitost bod.
Hint: http://mj.ucw.cz/vyuka/0607/ads1/ads.ps strana 14.
med22Napište funkci med2 : int array -> int array -> int, která dostane dvě setříděná pole a vrátí medián jejich sjednocení. Body dostanete podle složitosti, ale za lineární složitost jich určitě moc nebude.
Hint: Binární vyhledávání :)
psrt3Napište funkci psrt : int list -> int list, která setřídí danou posloupnost. Předpokládejte, že daná 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. Ο(n log k) za tři body, Ο(nk) za dva a zbytek za jeden. Hodnotu k přirozeně neznáte.
Hint: Ο(nk) je bubblesort, na Ο(n log k) stačí použít třídění haldou omezené velikosti. Velikost haldy zkoušet 2, 4, 16, 256, tj. 22i, dokud se to nepovede.
05. listopadu 2008Úkoly můžete odevzdávat do 03. prosince 2008, 15:30.
rmq2.5Napište funkci, která dostane pole čísel A a vyrobí z něj vhodným předzpracováním nějakou datovou strukturu, která bude umět odpovídat na dotazy "jaké je maximum z hodnot A[i .. j] pro dané i a j". Předzpracování musíte zvládnout v lineárním čase, na dotazy musíte umět odpovídat alespoň v Ο(log n). Za Ο(1) na dotaz je nemalý bonus, ale pozor, je to docela těžké a pracné.
Hint: Nad polem si vyrobte vhodný vyvážený binární strom a v každém vrcholu si poznamenejte maximum ze všech jeho synů. Daný interval pak rozložte tak, aby stačilo šáhnout o řádově log N vrcholů v tomto stromě.
mul2.5Napište funkci mul : int array -> int array -> int array, která násobí dvě daná dlouhá čísla. Dlouhá čísla si reprezentujte jak chcete, jenom typ této reprezentace musí být int array. Triviální řešení v Ο(N2) za bod, lepší než kvadratické za dva a půl (a šílená řešení mohou dostat i bodů víc :–).
Hint: http://en.wikipedia.org/wiki/Karatsuba_algorithm
maxpath2Mějme obecné stromy typu type 'a tree = Node of 'a * 'a tree list. Napište funkci maxt : 'a tree -> 'a list, která dostane strom a vrátí jednu z nejdelších cest v tomto stromě. Cestu vraťte jako seznam hodnot typu 'a.
Hint: Jedno procházení do hloubky, v každém vrcholu si spočtěte dvě nejdelší cesty z něj dolů do listů. Nakonec si vyberte vrchol, ve kterém je součet těchto dvou cest maximální.
perm2.5Napište funkce rank : int array -> int a unrank : int -> int -> int array. Funkce rank dostane permutaci a vrátí její pořadové číslo, funkce unrank dostane délku permutace, její pořadové číslo a vrátí tuto permutaci. Samozřejmě jsou rank a unrank inverzní, ale jinak může být očíslování permutací libovolné (nemusí být například lexikografické). Předpokládejte, že se pořadové číslo permutace vejde do intu. Plný počet bodů jenom za lineární složitost obou funkcí.
Hint: http://citeseer.ist.psu.edu/myrvold00ranking.html
12. listopadu 2008Úkoly můžete odevzdávat do 10. prosince 2008, 15:30.
short012Napište funkci short01 : int -> byte list, která dostane číslo N a najde takové nenulové přirozené číslo, které má v desítkovém zápisu jenom nuly a jedničky, je dělitelné číslem N a jeho desítkový zápis je nejkratší možný. Toto číslo vraťte po cifrách v seznamu, v pořadí od nejméně důležité cifry (od jednotek). Body podle složitosti.
Hint: Prohledávání do šířky. Vrcholy jsou zbytek po dělení N (na začátku jsem ve vrcholu s hodnotou 1), hrany jsou přidání nuly nebo jedničky na konec čísla. Hledám nejkratší cestu do nuly.
min12Napište funkci min1 : int -> byte list, která dostane číslo N a najde takové nenulové přirozené číslo, které má v desítkovém zápisu jenom nuly a jedničky, je dělitelné číslem N a jeho desítkový zápis obsahuje nejmenší možný počet jedniček. Toto číslo vraťte po cifrách v seznamu, v pořadí od nejméně důležité cifry (od jednotek). Body podle složitosti.
Hint: Jako minulá úloha, jenom musíme chytřeji provádět prohledávání grafu (hrany odpovídající přidání nuly jsou zadarmo).
zs4Pouze F# Mějme čísla x1, x2, ..., xN a definujme hodnoty zi jako součin všech xj kromě xi, takže zi = Πj<>i xj. Vaším úkolem bude spočítat všechny zi, přičemž nesmíte používat žádné jiné operace než násobení (speciálně ne dělení). Napište tedy funkci zs : int [] -> seq<int>. Tato funkce dostane na vstupu hodnoty xi a vytvoří sekvenci, která vrátí postupně hodnoty z1, z2, ..., zN. Vaším úkolem je co nejvíce šetřit časem a pamětí, přičemž uvažujeme časovou a paměťovou složitost pro spočtení všech zi.
Čas Ο(N) a paměť Ο(N): +1 bod
Čas Ο(N) a paměť Ο(√N): +1 bod
Čas Ο(N log N) a paměť Ο(log N): +2 body
Řešení můžete poslat několik a body se sčítají podle toho, co splníte. Všimněte si, že pokud splníte druhou variantu, splnili jste automaticky i první variantu.
Hint: Předpočítáním si pro každé i součin xixi+1...xN od konce dostanu první variantu. Pokud si z těchto hodnot pamatuji pouze každou N-tou, dostanu N bloků. Každý vyřeším tak, že si hodnoty v něm spočtu z oné jedné zapamatované hodnoty do pomocné paměti o velikosti N. Variantu s log N pamětí neporadím :)
19. listopadu 2008Úkoly můžete odevzdávat do 17. prosince 2008, 15:30.
grep1.5Napište program, který jako parametr dostane regulární výraz, zpracovává standardní vstup a vypisuje ty řádky, které tomuto výrazu odpovídají. Umožněte ještě, aby bylo možno před regulárním výrazem zadat swištík -v, který způsobí, že se budou vypisovat řádky, které nevyhovují.
Hint: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regex_members.aspx
hist2Napište program, který načte řádky ze standardního vstupu a vypíše jejich histogram (tj. informace řádka vstupu a její četnost) setříděný od nejčastějších řádek. Takže program dělá přibližně to, co sort | uniq -c | sort -nr.
Hint: Hešování nebo stromečky :–)
sed2.5Pouze F# Napište program, který jako první parametr dostane v jazyce F# zdrojový kód nějaké funkce typu string -> string. Program pak načítá řádky standardního vstupu, na každý spustí tuto funkci a pokud vrátí neprázdný řetězec, vypíše ho na standardní výstup. Tahle úloha je dost technická, ale pokud by vás bavila, můžete začít třeba zde http://msdn.microsoft.com/en-us/library/system.codedom.compiler.codedomprovider_members.aspx nebo přímo v FSharp.Compiler.CodeDom.dll nebo FSharp.Compiler.dll.
dehash3Mějme nějakou funkci f : int -> int, přičemž víme, že posloupnost 0, f(0), f(f(0)), ..., je periodická, takže nějaké fN(0) je rovno nějaké předchozí hodnotě. Vaším cílem je, když dostanete libovolnou takovou funkci f, provést nějaké předzpracování a pak umět odpovídat na otázky "když dostanu x, pro jaké y je f(y) = x"? Přičemž pro x, které jsou v posloupnosti 0, f(0), f(f(0)), ..., musíte odpovědět vždy správně, a pro x, která nejsou, řekněte, že nevíte.
Napište tedy funkci typu dehash : (int -> int) -> (int -> int option). Pro plný počet bodů musí předzpracování trvat Ο(N), musí si vystačit s ostře méně než Ο(N) paměti a odpovídat na otázky musíte umět také ostře lépe než v čase Ο(N).
Hint: Hodnoty funkce f tvoří ocásek a pak cyklus. Na ocásku i cyklu si pamatujte každou odmotnintou hodnotu a u každé si pamatujte, jaká odmocnintá hodnota je před ní. Když poté hledáte vzor x, jděte z x pořád dál, než narazíte na uloženou hodnotu, skočte na jejího předchůdce a jděte směrem k x.
26. listopadu 2008Úkoly můžete odevzdávat do 07. ledna 2009, 15:30.
upword2Napište funkci upword : string -> string -> string, která dostane a a b a vrátí co nejkratší slovo, jehož jsou a i b (ne nutně souvislá) podslova.
Hint: http://en.wikipedia.org/wiki/Shortest_common_supersequence_problem
decrypt2.5Máme zprávu, která se skládá ze znaků 'a'..'z', které si očíslujeme 0..25. Posun písmene i o k je písmeno (i+k) mod 26 a posun celé zprávy o k je posun všech jejích písmen o k.
Napište funkci decrypt : string -> string -> string, která dostane zprávu posunutou o neznámou hodnotu k. Dále dostane nějaký text v jazyce, ve kterém je zašifrovaná zpráva. Cílem je vrátit jeden z posunů dané zašifrované zprávy, a to ten nepravděpodobnější. Pravděpodobnost nějaké zprávy můžete měřit například frekvencí jednotlivých znaků ('e' je v češtině nejpravděpodobnější, 'w' velmi málo pravděpodobné atd.).
Hint: http://en.wikipedia.org/wiki/Frequency_analysis
cmprs5Napište konzolové programy cmprs a uncmprs. Tyto programy dostanou na příkazové řádce právě jedno jméno souboru, který zabalí/rozbalí. Kompresní metoda by měla být jedna z následujících: Huffmanovo kódování nebo aritmetické kódování (případně i s BWT za dva bonusové body) či nějaká varianta LZ*. Koncovku zabaleného souboru si vyberte sami. Mělo by to být celé v F#, rozumně efektivní a na plný počet bodů byste měli i testovat integritu rozbaleného souboru (spočítat si nějaké CRC při zabalování a to po rozbalení zkontrolovat).
03. prosince 2008Úkoly můžete odevzdávat do 14. ledna 2009, 15:30.
abcd3Abeceda 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 tvoří kompletní atlantidskou abecedu. 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 list -> char list option|, 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í None. Můžete předpokládat, že data jsou konzistentní.
diff4Napište konzolový program 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. Program musí fungovat se složitostí Ο(délka_delšího_souboru * velikost_diffu), za nic jiného body nejsou (složitost Ο(délka_jednoho * délka_druhého) je totiž pro velké soubory s malým počtem změn nepoužitelná).
10. prosince 2008Úkoly můžete odevzdávat do 22. února 2009, 23:59.
volume4.5Obdélkík, jehož strany jsou rovnoběžné s osamy, můžeme reprezentovat souřadnicemi dvou protilehlých rohů jako float * float * float * float. Napište funkci volume : (float * float * float * float) list -> float, která dostane několik obdélníku, jejichž strany jsou rovnoběžné s osami, a spočte obsah jejich sjednocení. Za kvadratické řešení je 2.5 bodu, za Ο(N log N) je plný počet 4.5 bodu.
eval3Napište funkci eval : string -> float, která dostane na vstupu řetězec obsahující výraz a vrátí jeho hodnotu. Musíte umět celá a desetinná čísla, binární operátory +, -, *, /, ^ včetně priorit, funkce exp a log a závorky. Daný výraz může obsahovat libovolné počty mezer.
Hint: Můžete použít parsování z hodiny, ale také libovolné jiné.
deriv1.5Pokud vyřešíte úlohu eval, napište funkci diff : string -> string, která zderivuje daný výraz. Oba výrazy jsou v již popsaném formátu, jenom smí obsahovat ještě proměnnou x. Výsledný výraz nemusí být nijak zjednodušen, ale je možné za to přidělit body navíc.
vareval1.5Pokud vyřešíte úlohu eval, napište funkci vareval : string -> float. Výraz na vstupu je v popsaném formátu, jenom může obsahovat konstrukci let prom = a in b, kde prom je řetězec malých písmen, a a b jsou výrazy a ve výrazu b se může objevit proměnná prom, která bude mít hodnotu výrazu a. Oba výrazy a a b mohou uvnitř samozřejmě obsahovat další lety, například jako 1 + let a = 3 * let b = 3 in 1+b in a^2. Výraz za in parsujte nejdelší možný (takže je ukončen jenom jiným in nebo pravou závorkou).
17. prosince 2008Úkoly můžete odevzdávat do 22. února 2009, 23:59.
crawler4Napište webový crawler. To je konzolový program, který dostane seznam dvojic (url, regexp) a číslo S. Crawler stáhne všechny stránky na seznamu. Z každé stránky vyextrahuje odkazy a ty, které matchují danému regexpu, opět stáhne, a odkazy na nich, které matchují danému regexpu, opět rekurzivně stáhne... V jednom časovém okamžiku stahujte najednou S stránek a jedno konkrétní url stahujte nanejvýš jednou.
web3Napiš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.
chat3Napište jednoduchý chatovací server. 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".

Stav (09. 03. 2009)

JménoOdevzdané úkolyBody
Jan Ambrožsort(2.5), cenzor(1), median(2.5), perm(2.5), mul(2.5), zs(1), short01(1.5), min1(1), abcd(3), eval(3), deriv(2.5), vareval(1.5), web(3), chat(3)30.5
Adam Abonyipow(0.5), bitsum(1), sort(1.5), rost(0.5), rost(2.5), ssrt(2), psrt(2), median(1), cenzor(1.5), mul(1), perm(2.5), zs(1), grep(1.5), hist(2), dehash(2), abcd(3), eval(3), deriv(1.5)30
Daniel Balašpow(1), bitsum(1), sort(1.5), median(2.5), rost(2.5), ssrt(3), rsam(2), cenzor(1.5), psrt(3), mul(2.5), zs(2.5), grep(1.5), hist(2), dehash(3), eval(3)32.5
Ondra Bílkapow(1), bitsum(1.5), sort(1.5)4
Tomáš Caithamlpow(1), sort(1.5), rost(2.5), maxis(2.5), opti(3.5), median(2.5), maxpath(2), perm(2.5), short01(2), grep(1.5), hist(2), cmprs(5.5), volume(2.5)31.5
Miroslav Cickopow(1), bitsum(1), sort(1.5), opti(2.5), ssrt(2), cenzor(2.5), med2(3), rmq(2.5), mul(2.5), maxpath(3), perm(2.5), web(3), crawler(4), chat(3)34
Tomáš Gavenčiaksort(2.5)2.5
Tomáš Krautpow(1), bitsum(1), sort(1.5), med2(1.5), perm(2.5)7.5
Michal Pavelčíkpow(1), bitsum(2), sort(2.5), ssrt(3), rost(2.5), maxis(2.5), opti(3.5), median(2.5), rsam(2), cenzor(2.5), med2(1.5), maxpath(2), zs(4), mul(3.5), psrt(3), short01(2), grep(1.5), sed(2.5)44
Josef Piherapow(1), bitsum(2), sort(2.5), ssrt(3), rost(2.5), maxis(2.5), opti(3.5), median(2.5), rsam(2), cenzor(2.5), med2(2.5), maxpath(2), zs(4), psrt(3), rmq(5)40.5
Roman Smržpow(1), bitsum(1.5), sort(2.5), cenzor(2.5), rmq(2.5), med2(2), maxpath(2), zs(4), short01(2), min1(2), upword(2), eval(3), vareval(1.5), deriv(1.5)30
Martin Suchanpow(1), bitsum(1), sort(1.5), rost(2), rsam(1.5), median(1.5), psrt(2), med2(1), cenzor(1), perm(2.5), mul(2.5), short01(2.5), zs(1.5), zápočťák(9)30.5
Matúš Tejiščákpow(1), bitsum(1), median(1.5), psrt(3), sort(1.5), mul(3.5), short01(2), eval(3), deriv(3), vareval(1.5)21
Hujerpow(1), bitsum(2), sort(2.5), opti(3.5), ssrt(3), rost(2.5), maxis(2.5), rsam(2), cenzor(2.5), median(2.5), med2(2), psrt(3), rmq(2.5), mul(2.5), maxpath(2), perm(2.5), short01(2), min1(2), zs(4), grep(1.5), hist(2), sed(2.5), dehash(3), upword(2), decrypt(2.5), cmprs(5), abcd(3), diff(4), volume(4.5), eval(3), deriv(1.5), vareval(1.5), crawler(4), web(3), chat(3)92.5

Zpět