Programovací jazyk F#, PRG049


Obsah semináře

Cílem semináře je zjistit, co to znamená programovat funkcionálně, jaké to přináší výhody a kdy se vyplatí to dělat. Nás konkrétně bude zajímat programovací jazyk F#, funkcionální jazyk z rodiny jazyků ML, který je součástí Visual Studia 2010 (ale lze ho použít i na Monu).

Seznámíme se s řadou technik funkcionálního programování, od základních až po pokročilé, a ukážeme si, jak nám mohou pomoci s vytvářením znovupoužitelného kódu nebo s s paralelním a asynchronním programováním.

Seminář nepožaduje žádné předchozí znalosti funkcionálního programování. Na druhou stranu je velmi dobré mít zkušenosti s programováním jako takovým.

Doba a místo konání

Seminář se koná v pondělí ve 12:20 na Malé Straně, v učebně SU1. První přednáška se koná až v pondělí 11. října.

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 F#

Překladač F# je součástí Visual Studia 2010, na které mají studenti MFF zdarma licenci (stačí zde vybrat "Log In" a použít přístupové údaje z CAS).

Případně je možné nainstalovat si z této stránky samotný F# 2.0. Pokud k němu chcete vývojové prostředí, ale nechcete celé Visual Studio, nainstalujte si ze stejné stránky nejprve Visual Studio 2010 Shell.

Mono

Překladač F# funguje výborně i s Mono. V tom případě vám stačí stáhnout si z této stránky F# 2.0 (zip) a rozbalit ho. Používám úspěšně Mono 2.4.3 a 2.6.7.

F# Powerpack

Tvůrci jazyka F# uvolnili i sadu dalších knihoven pro F# jako F# Powerpack. Z něj doporučuji hlavně fslex, fsyacc a fshtmldoc. Použité knihovny lze staticky zakompilovat do výsledných binárek, takže se nemusíte bát problémů s distribucí. Ve svých úkolech můžete tuto knihovnu používat.

Obsahy přednášek

Domácí úkoly (29. 06. 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
25. října 2010Úkoly můžete odevzdávat do 08. listopadu 2010, 12:20.
sum0.5Napište funkci sum : list<int> -> int, která sečte daný seznam intů a potřebuje k tomu jen konstantně prostoru na zásobníku.
rev1Napište funkci rev : list<'a> -> list<'a>, která vrátí daný seznam v opačném pořadí a potřebuje k tomu jen konstantně prostoru na zásobníku.
flatten1Napište funkci flatten : Tree<'a> -> list<'a>, která vrátí prvky daného stromu v pořadí od nejlevějšího po nejpravější.
25. října 2010Úkoly můžete odevzdávat do 22. listopadu 2010, 12:20.
2352.5Napište funkci seq235 : seq<bigint>, která vrátí sekvenci všech rostoucích čísel tvaru 2i3j5k. Pár prvních prvků je 1, 2, 3, 4, 5, 6, 8, ....
Plný počet bodů jenom za řešení, které potřebuje konstantní čas k nalezení dalšího prvku posloupnosti.
minfree2.5Napište funkci minfree :: list<uint> -> uint, která dostane seznam neopakujících se nezáporných čísel a vrátí nejmenší, které v tom seznamu není. Pokud chápete daný seznam jako nějaké použité identifikátory, minfree vrátí první nepoužitý.
Plný počet bodů jenom za řešení v lineárním čase bez použití pole, mutable či odkazů.
01. listopadu 2010Úkoly můžete odevzdávat do 15. listopadu 2010, 12:20.
fldrev0.5Napište funkci List.rev pomocí nějaké funkce z rodiny fold.
fldchs0.5Napište funkci List.choose pomocí nějaké funkce z rodiny fold.
fldcol0.5Napište funkci List.collect pomocí nějaké funkce z rodiny fold. Nepoužívejte jiné funkce z modulu List.
fld2fld1.5Napište funkci fold pomocí List.foldBack a naopak funkci foldBack pomocí List.fold. Nepoužívejte další funkce z modulu List ani Array. Můžete použít fun v definici funkce pro List.foldBack. Mělo by to vypadat jako let fold f z xs = List.foldBack (fun ...) .... Opravdu to jde :-)
01. listopadu 2010Úkoly můžete odevzdávat do 29. listopadu 2010, 12:20.
ssum2Napište funkci ssum : int -> list<int> -> option<list<int>>, která zjistí, ze v daném seznamu nachází souvislý úsek daného součtu. Pokud ano, vraťte ho. Plný počet bodů za složitost Ο(N log N).
clen1.5Vytvořte funkci clen : seq<int> -> int, která dostane nekonečnou sekvenci. Tato sekvence má následující vlastnost: pokud za prvkem a jednou následoval prvek b, za každým prvkem a následuje prvek b. Jinak řečeno, prvek je vždy jednoznačne určen předchozím.
Protože je sekvence nekonečná a int ne, musí být od nějaké doby periodická. Vaším úkolem je pomocí konstantní paměti spočítat délku této periody.
Příklad: délka periody sekvence {1; 2; 3; 4; 3; 4; 3; ... } je 2.
coll1Tuto úlohu můžete řešit až tehdy, když vyřešíte clen.
Vytvořte funkci coll : (int -> int) -> int * int, která dostane deterministickou funkci f, o které ví, že nekonečná posloupnost f(0), f(f(0)), f(f(f(0))),... neobsahuje nulu. (Tedy sekvence Seq.initInfinite f by splňovala podmínky zadání úlohy clen.)
Pomocí konstantní paměti vraťte dvě různé hodnoty x a y, že f(x) = f(y).
Varianta tohoto se někdy používá pro hledání kolizí hashovacích funkcí.
08. listopadu 2010Úkoly můžete odevzdávat do 22. listopadu 2010, 12:20.
mintree1Předpokládejme typ type tree<'a> = Leaf of 'a | Node of tree<'a> * tree<'a>. Napište funkci mintree : list<'a> -> tree<a'>, která dostane seznam prvků a vytvoří z nich strom obsahující dané prvky jako listy v pořadí zleva doprava, čili aby platilo xs = (xs |> mintree |> flatten). Tento strom navíc musí mít co nejmenší hloubku. Nepoužívejte při řešení žádná pole ani mutable. Plný počet bodů za řešení v Ο(N).
huff1.5Předpokládejme typ type tree<'a> = Leaf of 'a | Node of tree<'a> * tree<'a>. Napište funkci huff : list<tree<'a>> -> tree<'a>, která dostane seznam stromů a vytvoří z nich (spojováním pomocí Node) jeden strom (dané podstromy může obsahovat v libovolném pořadí). Tento strom musí mít minimální možnou hloubku. Plný počet bodů za složitost Ο(N log N + S), kde N je počet stromů na vstupu a S je součet prvků v těchto stromech.
Hint: Vždy chcete spojit přes Node dva stromy nejmenší hloubky.
bala1Napište funkci balanced : list<bool> -> list<bool>, která dostane seznam boolů a vrátí nejdelší souvislou podposloupnost, ve kterých je stejně hodnot true i false. Mělo by fungovat v lineárním čase.
Za řešení bez polí a mutable nabízím další bod.
08. listopadu 2010Úkoly můžete odevzdávat do 06. prosince 2010, 12:20.
lcs2.5Napište funkci lcs : list<'a> -> list<'a> -> list<'a>, která vrátí nejdelší společný (ne nutně souvislý) podseznam dvou daných seznamů. Složitost pro plný počet bodů je Ο(délka prvního seznamu * délka druhého seznamu). Používejte jenom seznamy, žádné mutable, odkazy ani pole.
t2min3Předpokládejme typ type tree<'a> = Leaf of 'a | Node of tree<'a> * tree<'a>. Napište funkci t2min : list<tree<'a>> -> tree<'a>, která dostane seznam stromů a vytvoří z nich (spojováním pomocí Node) jeden strom, který obsahuje dané podstromy v zadaném pořadí, čili aby platilo List.collect flatten xs = flatten (t2min xs). Tento strom navíc musí mít co nejmenší hloubku. Nepoužívejte při řešení žádná pole ani mutable.
Jen pro ty, co se nudí.
15. listopadu 2010Úkoly můžete odevzdávat do 29. listopadu 2010, 12:20.
saddle2Naprogramujte funkci saddle : (z : int) -> (f : int -> int -> int) -> list<int * int>. Funkce saddle dostane funkci f, která souřadnicím x:int a y:int přiřazuje nějakou hodnotu typu int a víte, že tato funkce je ostře rostoucí v obou souřadnicích, tj. x < X => f x y < f X y a také y < Y => f x y < f x Y. Kromě této funkce dostanete hodnotu z : int a máte vrátit seznam všech dvojic x, y, že x≥0, y≥0 a f x y = z.
maxpath2Mějme obecné stromy typu type tree<'a> = Nil | Node of 'a * list<tree<'a>>. Napište funkci maxpath : tree<'a> -> list<'a>, která dostane strom a vrátí jednu z nejdelších cest v tomto stromě. Cestu vraťte jako seznam hodnot typu 'a.
15. listopadu 2010Úkoly můžete odevzdávat do 13. prosince 2010, 12:20.
zs1-4Mě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.
15. listopadu 2010Úkoly můžete odevzdávat do 30. září 2011, 23:59.
diff8Napiš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 musí být Ο(počet řádek v obou souborech * velikost diffu), paměťová stačí Ο(velikost diffu na druhou), viz tento článek.
22. listopadu 2010Úkoly můžete odevzdávat do 06. prosince 2010, 12:20.
demorse2Napište funkci demorse : string -> option<string>, která dekóduje vstup v morseovce, pokud je korektní. 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ů za složitost lineární s velikostí vstupu, tj. každou tečku a čárku ze vstupu byste měli zpracovat jednou.
primes2.5Napište funkci primes : seq<int>, která vrací sekvenci všech prvočísel. Plný počet bodů za složitost Ο(N log log N) pro získání prvočísel mezi 1..N, což je shodou okolností složitost Eratosthenova síta :–) Jen na rozdíl od Eratosthenova síta nevíte předem hranici, do které budete chtít prvocísla najít.
Za řešení v čase Ο(N √N) je jeden bod.
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" = "". Nepoužívejte knihovní funkce (jako třeba String.IndexOf), mělo by to být o implementaci vyhledávacího automatu. Plný počet bodů za lineární řešení.
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.
22. listopadu 2010Úkoly můžete odevzdávat do 20. prosince 2010, 12:20.
maxima2.5Napište funkci maxima : int -> list<'a> -> list<'a> when 'a : comparable, která dostane na vstupu číslo k a seznam x1, x2, ..., xN. Vytvořte seznam délky N-k+1, jehož i-tý prvek je maximum z prvků xi, xi+1, ..., xi+k-1. Řečeno slovy, spočtěte maxima všech souvislých úseků délky k. Plný počet bodů za řešení v lineárním čase.
useky3Napište funkci useky : list<'a> -> list<list<'a>> when 'a : comparable, která dostane na vstupu seznam, který rozloží na co nejmenší počet ostře rostoucích (ne nutně souvislých) podseznamů. Jinak řečeno, rozdělte prvky vstupního seznamu na co nejméně skupin, aby prvky v každé skupině byly ostře rostoucí. Plný počet bodů za řešení v čase Ο(N log N).
Příklad: useky [1..4] = [[1..4]]; useky [4..1] = [[4]; [3]; [2]; [1]]; useky [1; 1; 1] = [[1]; [1]; [1]]
29. listopadu 2010Úkoly můžete odevzdávat do 13. prosince 2010, 12:20.
wild2Napište funkci wild : string -> string -> bool, která dostane na vstupu wildcard a text a odpoví, zda celý tento text danému wildcardu odpovídá. Wildcard může obsahovat znaky:
  • ? – odpovídá právě jednomu znaku
  • * – odpovídá libovolně mnoha znakům
  • cokoliv jiného – odpovídá právě tomuto znaku.
Tedy wildcardu a?b* odpovídá acb, aabbb, ale ne ab ani aaab. Plný počet bodů za řešení v čase Ο(délka wildcardu * délka textu).
29. listopadu 2010Úkoly můžete odevzdávat do 20. prosince 2010, 12:20.
calc11Napište funkci calc : string -> option<float>, která vyhodnotí dodaný aritmetický výraz a vrátí výsledek, pokud bylo vše v pořádku. Ve výrazu lze používat operátory + - * / ^ ( ) s běžnými prioritami, a desetinná čísla typu float. Mezerové znaky ignorujte. Plný počet bodů za řešení v lineárním čase.
calc21Tento úkol můžete řešit až po vyřešení calc1. Ve výrazu se mohou být i následující funkce: abs() sqrt() sin() cos() min() max(), přičemž funkce min a max mohou dostat libovolný nenulový počet argumentů, které jsou odděleny čárkami. Tedy například min(abs((0 - 3) ^ 5), sin(4.4), sqrt(123)).
calc31Tento úkol můžete řešit až po vyřešení calc2. Před výrazem k vyhodnocení může být ještě několik přiřazení, každé ukončené středníkem. Přiřazení vypadá jako proměnná = výraz;, přičemž v následujících výrazech můžete používat výraz proměnná. Funguje to tedy podobně jako let proměnná = výraz. Příklad: x = 3; x = x + 1; y = abs(x); z = x * y 3; x + y + z
calc41Tento úkol můžete řešit až po vyřešení calc3. Kromě proměnných můžete definovat i funkce, tj. přiřazení může vypadat jako funkce a1 a2 ... = výraz;. Tím definujete funkci s daným počtem argumentů a tedy výraz je může používat. Navíc následující výrazy mohou používat i funkci funkce se správným počtem argumentů. Chová se to tedy podobně jako let funkce a1 a2 ... = výraz. Příklad: x = 3; f y = x + y; g a b c = f(a) + f(b) + f(c); h x = g(x, f(x), f(f(x))); h 5
29. listopadu 2010Úkoly můžete odevzdávat do 03. ledna 2011, 12:20.
spacify2.5Napište funkci spacify : (maxlen : int) -> (isWord : seq<char> -> bool) -> list<char> -> list<list<char>>. Tato funkce dostane na vstupu text bez mezer a jejím úkolem je přidat do textu mezery, aby všechna takováto vzniklá slova byla smysluplná. Dostanete tedy ještě maximální délku slova maxlen a funkci isWord, která pro slovo (sekvenci znaků) určí, zda je to smysluplné slovo jazyka. Pokud je takových rozdělení na slova víc, najděte to, které používá co nejméně slov. Plný počet bodů za složitost Ο(délka textu * maximální délka slova * složitost isWord).
29. listopadu 2010Úkoly můžete odevzdávat do 30. září 2011, 23:59.
logo8Naimplementujte simulátor loga podle tohoto zadání, a to včetně všech rozšíření. Pokud chcete, můžete podporovat hodnoty typu float místo int, dává to větší smysl :–) Pro testování můžete použít tato testovací data, jsou rozdělena podle jednotlivých rozšíření, ale vám musí fungovat stejně všechno.
logosrv2Pokud jste vyřešili předchozí úlohu, naimplementujte k ní http rozhraní. Tedy naimplementujte malý standalone http server (nejspíš běžící na uživatelsky definovaném portu), který zobrazuje stránku, na které je možné zadat kód pro Krunimíra a počet tahů. Po odeslání zobrazte navíc i obrázek s Krunimírovy tahy (nikam ho neukládejte, generujte ho on-the-fly).
13. prosince 2010Úkoly můžete odevzdávat do 20. prosince 2010, 12:20.
cops1.5Ulice města si představte jako strom. Chcete každou ulici nechat hlídat policií. K tomu účelu na některé křižovatky (tj. vrcholy stromu) umístíte policisty. Ulice je hlídaná, když je policista umístěn na alespoň jednom konci této ulice. Protože je rozpočet policie tradičně mizerný, je třeba zaměstnat co nejméně policistů.
Napište metodu cops : tree<'a> -> list<'a>, která dostane strom města a vrátí nejmenší množinu vrcholů takovou, že pro každou ulici je v této množině alespoň jeden její konec. Strom je definován jako type tree<'a> = Node of 'a * list<tree<'a>>.
median2Napište funkci median : list<'a> -> 'a when 'a : comparison, která vrací medián dané posloupnosti. Za Ο(N) v nejhorším případě jsou dva body, za Ο(N) v průměru je bod.
Hint: http://mj.ucw.cz/vyuka/0607/ads1/ads.ps strana 14.
13. prosince 2010Úkoly můžete odevzdávat do 03. ledna 2011, 12:20.
tiso2Stromy jsou definované jako type BinTree<'a> = Nil | Node of BinTree<'a> * 'a * BinTree<'a>. Napište funkci, která dostane dva stromy, a zjistí, jestli jsou stejné, pokud nezáleží na pořadí synů. Tedy Node (Nil, 1, Node (Nil, 2, Nil)) je až na pořadí synů shodný s Node (Node (Nil, 2, Nil), 1, Nil). Plný počet bodů za řešení rychlejší než Ο(N2), kde N je počet vrcholů většího ze stromů.
blud2Na standardním vstupu dostanete bludiště. Všechny řádky standardního vstupu mají stejnou délku a obsahují znaky
  • . – volné pole
  • X – zeď
  • @ – hrdina, je v bludišti právě jeden
  • $ – poklad, je v bludišti právě jeden
Vaším úkolem je najít a zobrazit nejkratší cestu hrdiny k pokladu (vypište bludiště ve stejném formátu, a políčka na nejkratší cestě vypište jako *), nebo říct, že neexistuje. Plný počet bodů za řešení v lineárním čase.
krumpac1.5Tato úloha rozšiřuje úlohu předchozí. Na vstupu je bludiště zadané ve stejném formátu. Hrdina si ale do bludiště přinesl krumpáč a v případě nouze může prokopat libovolnou stěnu. To je ale velmi náročný úkol – najděte proto cestu od hrdiny k pokladu, na které je třeba rozbít krumpáčem co nejméně stěn. Ze všech takových cest najděte tu nejkratší. Vypište libovolnou takovou cestu, políčka na ní vypište jako * a rozbité zdi jako #. Plný počet bodů za řešení v lineárním čase.
13. prosince 2010Úkoly můžete odevzdávat do 30. září 2011, 23:59.
karel6Napište simulátor robota Karla. Na začátku stojí robot Karel na nějakém políčku šachovnice o rozměrech 10 x 10. Některá políčka šachovnice jsou volná, na jiných jsou zdi.
Napište program, který očekává na příkazové řádce jména dvou souborů – první obsahuje šachovnici, ta se skládá z deseti řádek, každá o deseti znacích, buď . (volné políčko), _ (volné políčko se značkou) nebo X (zeď). Na právě jednom políčku je robot Karel, jako znak >, <, v, ^, který určuje jeho orientaci. Druhý zadaný soubor obsahuje program pro Karla v této syntaxi. Pokud je vstup v pořádku, proveďte proceduru main, která musí být definována. Odsimulujte program pro Karla a na standardní výstup vypište šachovnici po ukončení procedury main. Pokud výpočet trvá moc dlouho (například milion kroků), ukončete ho a vypište o tom zprávu.
20. prosince 2010Úkoly můžete odevzdávat do 03. ledna 2011, 12:20.
zisk2Napište funkci zisk : list<int> -> list<int>, která dostane seznam celých čísel a najde nejdelší souvislý úsek, který má nezáporný součet (nejdelší období bez ztrát). Plný počet bodů za řešení v lineárním čase.
grep1.5Napište program grep, který dostane na standardním vstupu jako parametr regulérní výraz. Dále načítá standardní vstup a na výstup vypíše jenom řádky, které tomuto regulérnímu výrazu vyhovují. Pokud je parametru s regulérním výrazem předchází parametr -v, vypište naopak řádky, které danému výrazu nevyhovují.
Hint: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regex.aspx
20. prosince 2010Úkoly můžete odevzdávat do 30. září 2011, 23:59.
chats3Napište jednoduchý chat server. Server poslouchá na (na příkazové řádce) 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 jednoduchý konzolový chat klient. Klient se připojí na (na příkazové řádce) zadaný port. Jednotlivé zadané řádky se pošlou serveru. Kdykoliv přijde řádka od serveru, vypíše se "nad" rozepsanou editovanou řádku.
color61.5Napište funkci color6 : list<int>[] -> int[], která dostane rovinný graf a vrátí jeho obarvení šesti barvami (1..6). Graf na vstupu dostanete jako pole vrcholů, každý vrchol je reprezentován jako seznam jeho sousedů (čísluje se od nuly). Obarvení vraťte jako pole s prvky 1..6. Plný počet bodů za řešení v lineárním čase.
color52.5Napište funkci color5 : list<int>[] -> int[], která má stejný vstup jako color6, jenom počítá obarvení rovinného grafu pěti barvami. Plný počet bodů za složitost lepší než Ο(N2), za Ο(N2) je 1.5 bodu.
03. ledna 2011Úkoly můžete odevzdávat do 30. září 2011, 23:59.
withlog2.5Navrhněte výpočet, který si kromě výsledku pamatuje ještě log průběhu výpočtu:
  • vytvořte typ WithLog<'a>, který reprezentuje výpočet vracející typ 'a, zároveň s jeho logem,
  • vytvořte metodu res : WithLog<'a> -> 'a, která extrahuje výsledek výpočtu,
  • vytvořte metodu log : WithLog<'a> -> list<string>, která extrahuje log výpočtu (jednotlivé zprávy v pořadí, v jakém byly do logu přidány),
  • vytvořte withlog, která definuje computation expression pracující s typem WithLog<'a>, definujte Zero, Return a Bind,
  • vytvořte metodu write : string -> WithLog<unit>, která loguje daný řetězec. Používá se uvnitř computation expression jako do! write "message".
Mělo by tedy fungovat
                let compute = withlog {
                  do! write "a"
                  do! write "b"
                  return 5
                }
přičemž res compute = 5 a log compute = ["a"; "b"]. Pozor na to, že Bind by měl fungovat v konstantním čase a že s WithLog<'a> lze dál pracovat v několika pokračování, takže použít StringBuilder je špatně.
withenv2.5Navrhněte výpočet, který si udržuje environment (pro zjednodušení je environment mapování řetězce na řetězec):
  • vytvořte typ Env, který reprezentuje environment,
  • vytvořte typ WithEnv<'a>, který reprezentuje výpočet, který si udržuje environment. Pozor na to, že výpočet může environment i měnit,
  • vytvořte metodu run : seq<string*string> -> WithEnv<'a> -> 'a, která spustí výpočet s daným environmentem (zadaným jako posloupnost klíč-hodnota),
  • vytvořte withenv, která definuje computation expression pracující s typem WithEnv<'a>, definujte Zero, Return a Bind,
  • vytvořte metodu get : string -> WithEnv<string>, která vrátí z environmentu hodnotu s daným klíčem, nebo null, pokud neexistuje. Používá se uvnitř computation expression jako let! value = get "name",
  • vytvořte metodu set : string -> string -> WithEnv<unit>, která do environmentu zapíše pod daný klíč danou hodnotu (pokud už existuje, přepište ji). Používá se uvnitř computation expression jako do! set "name" "Petr".
Mělo by tedy fungovat
                let compute = withenv {
                  let! oldname = get "name"
                  do! set "name" "Jarda"
                  return oldname
                }
                printfn "%A" (run ["name", "Petr"] compute)
a po spuštění vypsat "Petr. Pozor na to, že s WithEnv<'a> lze dál pracovat v několika pokračování, které každé může jinak měnit Env.
stoppable2.5Navrhněte výpočet, který je možné v průběhu přerušit:
  • vytvořte typ Stoppable<'a>, který reprezentuje výpočet vracející typ 'a, který ale může být přerušen,
  • vytvořte metodu res : Stoppable<'a> -> option<'a>, která vrátí výsledek, pokud výpočet není přerušen,
  • vytvořte metodu step : Stoppable<'a> -> Stoppable<'a>, která pokud dostane přerušený výpočet, provádí ho do dalšího přerušení,
  • vytvořte stoppable, která definuje computation expression pracující s typem Stoppable<'a>, definujte Zero, Return a Bind,
  • vytvořte metodu stop : Stoppable<unit>, která přeruší probíhající výpočet. Používá se uvnitř computation expression jako do! stop
Mělo by tedy fungovat
                let compute = stoppable {
                  printfn "Pred"
                  do! stop
                  printfn "Po"
                  return 5
                }
                printfn "%A" (res compute)
                printfn "%A" (res (step compute))
a po spuštění vypsat
                Pred
                <null>
                Po
                Some 5
                
sudoku4Napište sudoku solver. Na standardním vstupu dostane popis sudoku – všímejte si jenom znaků . (tečka) a 0-9, ostatní ignorujte (včetně znaků nové řádky) – tím budete umět načíst skoro všechny používané formáty. Dané sudoku vyřešte a vypište vyřešené na standardní výstup. Plný počet bodů, pokud to na většinu sudoku bude fungovat v rozumném čase (v řádu vteřin).
10. ledna 2011Úkoly můžete odevzdávat do 30. září 2011, 23:59.
par2.5Navrhněte výpočet, který bude paralelně vyhodnocovat alternativní větve v různých vláknech:
  • vytvořte typ Par<'a>, který reprezentuje výpočet, který bude počítat výsledek typu 'a několika alternativními způsoby, a ty se budou provádět paralelně,
  • vytvořte metodu run : Par<'a> -> 'a, která spustí výpočet, alternativní způsoby budou prováděny paralelně,
  • vytvořte par, která definuje computation expression pracující s typem Par<'a>, definujte Zero, Return, Bind a Combine. Metoda Combine funguje tak, že dvě alternativy vyhodnocuje paralelně.
Mělo by tedy fungovat
                let twoalts = par {
                  return (List.length [1..1000000])
                  return (Seq.length <| Seq.collect (fun i -> {1..1000}) {1..1000})
                }
                let fouralts = par {
                  return! twoalts
                  return! twoalts
                }
                run fouralts
přičemž výpočet bude probíhat ve 4 vláknech a které nejdřív skončí, vrátí výsledek, a ostatní vlákna budou ukončena.

Stav (29. 09. 2011)

JménoOdevzdané úkolyBody
Jan Bímmintree(1), huff(1.5), clen(1.5), coll(1), saddle(2), maxpath(2), demorse(2), lcs(2.5), cenzor(2), zs(1), wild(2), maxima(2.5), median(1), cops(1.5), blud(2), grep(1.5), krumpac(2.5), color6(0.75)30.25
Michal Brabecsum(0.5), rev(1), flatten(1), fldrev(0.5), fldchs(0.5), fldcol(0.5), fld2fld(0.5)4.5
Jakub Břečkasum(0.5), rev(1), flatten(1), 235(2.5), ssum(2), fldchs(0.5), fldrev(0.5), fldcol(0.5), mintree(1), huff(0.75), minfree(2.5), clen(1.5), calc1(1), calc2(1), grep(1.5), chats(3), chatc(2), sudoku(4), karel(6)32.75
Filip Děchtěrenkosum(0.5), rev(1), minfree(1.5), fldrev(0.5), fldchs(0.5), 235(2.5), fldcol(0.5), flatten(1), fld2fld(1.5), mintree(1), ssum(1), bala(1), huff(1.5), saddle(2), zs(1), maxpath(2), demorse(2), primes(1), clen(1.5), coll(1), lcs(2.5), calc1(1), calc2(1), maxima(1)30
Tomáš Dvořáksum(0.5), rev(1), flatten(1), minfree(1.5), 235(1), fldrev(0.5), fldchs(0.5), fldcol(0.5), fld2fld(1.5), mintree(1), huff(0.75), bala(1), ssum(1), maxpath(1.5), saddle(1), lcs(2.5), t2min(2), primes(1), demorse(1), cenzor(1.25), maxima(1.5), useky(2), zs(1), calc1(1), median(2), cops(0.75)30.25
Ondřej Filipsum(0.5), rev(1), flatten(1), fldrev(0.5), fldcol(0.5), fldchs(0.5), 235(2.5), minfree(1.5), mintree(1), huff(1.5), bala(1), maxpath(2), saddle(2), ssum(1), demorse(2), primes(0.5), clen(1.5), coll(1), cenzor(2), lcs(2.5), calc1(1), calc2(1), calc3(1), calc4(1)30
Marek Fišersum(0.5), rev(1), flatten(1), minfree(2.5), 235(2.5), fldrev(0.5), fldchs(0.5), fldcol(0.5), clen(1.5), coll(1), fld2fld(1.5), ssum(2), calc1(1), calc2(1), calc3(1), logo(7), lsystémy(10)35
Lukáš Harvánekrev(1), sum(0.5), fldrev(0.5), fld2fld(0.5), lcs(0.5)3
Richard Jedličkasum(0.5), rev(1), flatten(1), fldrev(0.5), fldchs(0.5), fldcol(0.5), maxpath(1), demorse(1.5)6.5
Martin Koníčeksum(0.5), rev(1), flatten(1), 235(2.5), fldrev(0.5), fldchs(0.5), ssum(2), bala(1)9
Jindřich Libovickýsum(0.5), rev(1), flatten(1), minfree(2.5), fldrev(0.5), fldchs(0.5), fldcol(0.5), fld2fld(0.5), mintree(0.75), huff(1), ssum(2), clen(0.5), saddle(1), maxpath(1.5), zs(0.75), demorse(2), primes(1), cenzor(2.5), wild(0.5), maxima(1.5), useky(1.5), calc1(1), calc2(1), calc3(1), tiso(1), median(2), cops(0.75)30.25
Ondřej Majerechsum(0.5), rev(1), flatten(1), fldrev(0.5), fldchs(0.5), fldcol(0.5), fld2fld(0.75)4.75
Jiří Maršíkfldrev(0.5), fldchs(0.5), fldcol(0.5), fld2fld(1), 235(2.5), clen(2), maxpath(2), demorse(2), cenzor(2.5), calc1(1), calc2(1), calc3(1), cops(1.5), grep(1.5), withlog(2.5), withenv(2.5), stoppable(2.5), par(2.5), color6(0.75)30.25
Stanislav Nowakfldrev(0.5), fldchs(0.5), sum(0.5), rev(1), flatten(1), minfree(1.5), 235(2.5), fldcol(0.5), fld2fld(1.5), demorse(2), primes(0.5), cenzor(2.5), calc1(1), calc2(1), calc3(1), chats(3), chatc(1.5), zs(3), cops(1), maxima(1), tiso(1), median(2)30
Karel Polednasum(0.5), rev(1), flatten(1.5), fldrev(0.5), fld2fld(1.5), fldcol(0.5), fldchs(0.5), ssum(1.5), maxpath(2), saddle(2), demorse(2), cenzor(2.5), calc1(1), calc2(1), calc3(1), calc4(1), wild(2), body_za_haskell(8)30
Marián Škvareksum(0.5), rev(1), flatten(1), fldrev(0.5), fldchs(0.5), fldcol(0.5)4
Matúš "ziman" Tejiščáksum(0.5), rev(1), flatten(1), fldrev(0.5), fldchs(0.5), fldcol(0.5), fld2fld(1.5), mintree(1), huff(1.5), bala(2), minfree(2.5), 235(2), clen(1), ssum(2), lcs(2.5), demorse(2), cenzor(2.5), wild(2), stoppable(2.5), chats(2)31
Jan Tučeksum(0.5), rev(1), flatten(1), minfree(2.5), 235(2.5), fldrev(0.5), fldchs(0.5), fldcol(0.5), clen(1.5), ssum(2), fld2fld(1.5), coll(1), bala(2), lcs(2.5), huff(1.5), mintree(1), diff(8)30
Pavel Veselýsum(0.5), rev(1), flatten(1), fldrev(0.5), fldchs(0.5), fldcol(0.5), mintree(1), minfree(2.5), maxpath(1), clen(1.5), ssum(2), primes(2.5), lcs(2.5), zs(4), wild(2), cops(1.5), calc1(1), calc2(1), calc3(1), withlog(2.5)30
Martin Všetičkasum(0.5), rev(1), flatten(1), minfree(2.5), 235(2.5), fldrev(0.5), fldchs(0.5), ssum(2), fld2fld(1.5), fldcol(0.5), clen(1.5), coll(1), lcs(2.5), mintree(1), bala(1), huff(1.5), zs(1), cenzor(2.5), saddle(2), maxpath(2), demorse(2)30.5
Hujersum(0.5), rev(1), flatten(1), 235(2.5), minfree(2.5), fldrev(0.5), fldchs(0.5), fldcol(0.5), fld2fld(1.5), ssum(2), clen(1.5), coll(1), mintree(1), huff(1.5), bala(2), lcs(2.5), t2min(3), saddle(2), maxpath(2), zs(4), diff(8), demorse(2), primes(2.5), cenzor(2.5), maxima(2.5), useky(3), wild(2), calc1(1), calc2(1), calc3(1), calc4(1), spacify(2.5), logo(8), logosrv(2), cops(1.5), median(2), tiso(2), blud(2), krumpac(1.5), karel(6), zisk(2), grep(1.5), chats(3), chatc(2), color6(1.5), color5(2.5), withlog(2.5), withenv(2.5), stoppable(2.5), sudoku(4), par(2.5)113.5

Zpět