Neprocedurální programování – letní semestr 2013/2014

Cvičení, pondělí 15.40

Požadavky na zápočet

Zápočtový program na dohodnuté téma; nějaké nápady jsou například na stránkách doktora Hrice.
12 bodů za domácí úkoly a písemky, z toho alespoň 5 za každou část (logické, resp. funkcionální programování)

Na každém cvičení budou zadány domácí úkoly za alespoň 2 body, s výjimkou dvou, na nichž bude (spíše orientační) písemka, za kterou bude možné získat také alespoň 2 body.

Domácí úkoly

Odevzdávejte buď e-mailem na adresu roman.smrz@seznam.cz nebo papírově na cvičení. Deadline je vždy do začátku cvičení v příslušný den.

19. 5. 2014, deadline 30. 6. 2014 24.00

(11a)
Stejně jako (8a) – napište funkci singleCont :: (Eq a) => [a] -> [a], která vynechá po sobě následující opakované výskyty prvků (z každé posloupnosti sobě rovných prvků nechá jeden) –, ale bez použití vlastní rekurze, nýbrž pomocí některé z funkcí foldr, foldl, scanr či scanl.
```
> singleCont [1,1,2,2,1,1,1,3]
[1,2,1,3]
```
(1 bod)
(11b)
Stejně jako (8b) – napište funkci sortByLen :: [[a]] -> [[a]], která stabilně seřadí seznamy podle jejich délky od nejkratšího po nejdelší (seznamy se stejnou délkou zůstanou v původním pořadí), časová složitost by měla být O(N*log N+L), kde N je počet seznamů a L jejich celková délka – ale pro řazení použijte funkci sort, ne vlastní implementaci řazení, funkci sortBy apod.
```
> sortByLen ["bbb","cc","ccc","aaa","aaaa","b"]
["b","cc","bbb","ccc","aaa","aaaa"]
```
(1 bod)
(11c)
Pro typ Expr z úkolu (10a) napište instance pro typové třídy Num, Fractional a Floating, přičemž typ rozšířte o reprezentace funkcí (logaritmus, sinus, kosinus, …) tak, aby to bylo možné.
Napište funkci deriv :: Char -> Expr -> Expr, která předaný výraz zderivuje podle proměnné z prvního parametru, výsledek nemusíte nijak zjednodušovat.
(1 bod)

12. 5. 2014

Dnes byla na řadě druhá písemka.

5. 5. 2014, deadline 12. 5. 2014 15.40

(10a)
Navrhněte datovou strukturu Expr pro reprezentaci aritmetických výrazů, měla by být schopná vyjádřit čísla, proměnné (určené znakem – hodnotou typu Char) a operace sčítání, odečítání, násobení, dělení a umocňování; a k ní vyhodnocovací funkci
```
eval :: [(Char, Double)] -> Expr -> Maybe Double
```
Která dostane hodnoty proměnných zadané v seznamu (můžete předpokládat, že žádná se nevyskytuje vícekrát) a vlastní výraz; vrátí výsledek ve tvaru Just <hodnota>, popřípadě Nothing, pokud je ve výrazu proměnná, jejíž hodnota není definovaná v seznamu.
(1 bod)
(10b)
Pro reprezentaci stromu z úkolu (9b) napište funkci
```
treeIso :: Tree Int -> Tree Int -> Bool
```
která vrátí True, právě když jsou předané stromy stejné až na pořadí synů.
```
treeIso (Branch 1 (Branch 2 Nil Nil) Nil) (Branch 1 Nil (Branch 2 Nil Nil))
> True
treeIso (Branch 1 (Branch 2 Nil Nil) Nil) (Branch 2 Nil (Branch 1 Nil Nil))
> False
```
(1 bod)
Bonus: Až jeden další bod je za řešení rychlejší neš O(N²), kde N je velikost většího stromu; na celý bod stačí O(N log N).
Můžete odevzdávat i řešení úkolu (9b), včetně bonusového.

28. 4. 2014, deadline 5. 5. 2014 15.40

Pro inspiraci možné (ne příliš efektivní) řešení pro vygenerování seznamu prvočísel pro úkol z konce cvičení:

primes = sieve $ numbers 2
    where sieve (x:xs) = x : filter (\y -> y `mod` x /= 0) (sieve xs)
          numbers n = n : numbers (n+1)

(Pozn.: místo numbers 2 je možné použít výraz [2..], ale podle slidů budou tyto výrazy na přednášce až později; nicméně kdo je zná, při řešení úkolů je samozřejmě použít může.)

(9a)
Napište výraz, pojmenovaný třeba gen357, definující ostře rostoucí posloupnost právě všech čísel, která nejsou dělitelná jinými prvočísly než 3, 5 a 7, tj. čísel ve tvaru 3ⁱ5^j7^k pro 0 ≤ i,j,k ∈ N.
```
> take 6 gen357
[1, 3, 5, 7, 9, 15]
```
(1 bod)
Bonus: Další bod dostanete, pokud potrvá vygenerování prvních K čísel čas O(K).
(9b)
Mějme následující reprezentaci stromu:
```
data Tree a = Nil
            | Branch a (Tree a) (Tree a)
```
Napište funkci findComplete :: Int -> Tree a -> Maybe (Tree a), která se pokusí v předaném stromě najít jako podstrom (ve smyslu podgrafu, tj. nemusí to být celý podstrom pod nějakým vrcholem) úplný strom o hloubce dané prvním parametrem (úplný strom hloubky 0 je Nil, hloubky 1 je například Branch 0 Nil Nil, hloubky 2 např. Branch 0 (Branch 1 Nil Nil) (Branch 2 Nil Nil), atd., bez ohledu na obsah vrcholů). Pokud takový podstrom najde, vrátí jej (pokud je jich více, tak libovolný) ve formě Just <podstrom>, jinak vrátí Nothing. Funkce by měla fungovat v lineárním čase k velikosti vstupního stromu.
```
> findComplete 2 $ Branch 2 (Branch 3 (Branch 4 Nil Nil) (Branch 5 (Branch 6 Nil Nil) Nil)) Nil
Just (Branch 3 (Branch 4 Nil Nil) (Branch 5 Nil Nil))
> findComplete 3 $ Branch 2 (Branch 3 (Branch 4 Nil Nil) (Branch 5 (Branch 6 Nil Nil) Nil)) Nil
Nothing
```
(1 bod)
Bonus: Další bod dostanete, pokud funkce vrátí správný výsledek i na libovolném nekonečném stromě, který hledaný podstrom obsahuje. (Pozn: zůstává požadavek na linearitu řešení pro konečné vstupy.)

14. 4. 2014, deadline 28. 4. 2014 15.40

(8a)
Napište funkci singleCont :: (Eq a) => [a] -> [a], která vynechá po sobě následující opakované výskyty prvků (z každé posloupnosti sobě rovných prvků nechá jeden), pro určení rovnosti můžete používat operátory == a /=.
```
> singleCont [1,1,2,2,1,1,1,3]
[1,2,1,3]
```
(1 bod)
(8b)
Napište funkci sortByLen :: [[a]] -> [[a]], která stabilně seřadí seznamy podle jejich délky od nejkratšího po nejdelší (seznamy se stejnou délkou zůstanou v původním pořadí). Časová složitost by měla být O(N*log N+L), kde N je počet seznamů a L jejich celková délka (alespoň v průměrném případě, takže můžete použít quicksort).
```
> sortByLen ["bbb","cc","ccc","aaa","aaaa","b"]
["b","cc","bbb","ccc","aaa","aaaa"]
```
(1 bod)

7. 4. 2014, deadline 14. 4. 2014 15.40

(7a)
Napište funkci comp, která dostane dvě funkce a vrátí jejich složení (stačí ošetřit případ, kdy obě funkce dostávají jeden argument):
```
> (define (plusOne x) (+ x 1))
> (define (timesTwo x) (* x 2))
> ((comp timesTwo plusOne) 3)
8
```
(1 bod)
(7b)
Napište funkci filter která dostane predikát (funkci vracející logickou hodnotu) a seznam a vrátí seznam obsahující pouze ty prvky ze vstupního, pro které predikát platí.
```
> (define (odd x) (equal? 1 (modulo x 2)))
> (filter odd '(1 2 3 4 5))
'(1 3 5)
```
(1 bod)
Poznámka: Oproti tomu, co jsem říkal na cvičení, je ve Scheme prázdný seznam – '() – taky brán jako pravdivá hodnota; jediná nepravdivá je #f.

31. 3. 2014, deadline 7. 4. 2014 15.40

Dnes jsme cvičení věnovali úvodu do lambda kalkulu, na němž jsou založeny funkcionální programovací jazyky. V rámci cvičení jsme používali tuto reprezentaci logických hodnot:

true = λx. λy. x
false = λx. λy. y

A následující numerály pro reprezentaci přirozených čísel:

0 ≈ λf. λx. x
1 ≈ λf. λx. f x
2 ≈ λf. λx. f (f x)
...
n ≈ λf. λx. fⁿ x

(6a)
Napište lambda term (označený třeba is_zero), který se vyhodnotí jako true, je-li aplikován na numerál odpovídající nule, a jako false, pokud na nějaký odpovídající jinému přirozenému číslu.
(1 bod)
(6b)
Napište lambda termy (mul, resp. exp), které se aplikované postupně na dva numerály vyhodnotí jako jejich součin, respektive mocnina.
(1 bod)
(6c) (těžší)
Napište term (pred), který aplikovaný na numerál kladného přirozeného čísla vrátí jeho předchůdce. Kromě samotného termu pošlete i vysvětlení, jak a proč funguje.
(1 bod)

Lambda kalkul je matematický nástroj, takže na řešení příkladů může stačit tužka a papír, nicméně chcete-li zkoušet příklady na počítači a máte k dispozici Haskell, můžete si stáhnout pomocný skript a přidávat definice do něj; syntaxe víceméně odpovídá té matematické, jen se místo „λ“ používá „\“ a místo „.“ je „->“ (viz příklady uvnitř). Jelikož Haskell neumí přímo zobrazit lambda termy, jsou tam pomocné funkce showBool a showNum na zobrazení logické hodnoty, respektive numerálu, dále definice true, false a funkce num pro generování numerálu z předaného čísla. S nainstalovaným kompilátorem GHC můžete v Linuxu načíst skript následujícím příkazem (S Windows či MacOS bohužel nemám zkušenosti, leda sem můžu přidat instrukce, pokud by mi je někdo poslal):

ghci lambda.hs

A zadávat výrazy k vyhodnocení (výsledek je potřeba obalit příslušnou pomocnou funkcí):

> showBool (and true false)
False
> showNum (plus (num 10) (num 5))
15

Jen upozorňuji, že Haskell používá typovaný lambda kalkul, ve kterém nejsou povolené všechny výrazy netypovaného kalkulu, například (λx.xx)(λx.xx), ale řešení příkladů by fungovat mělo (Poznámka: alespoň pro 6a a 6b, dostal jsem jedno řesení 6c, které otypovat nejde).

24. 3. 2014, deadline 31. 3. 2014 15.40

(5a)
Napište predikát split_diff/2, který pro rozdílový seznam v prvním parametru vrátí ve druhém jemu odpovídající klasický seznam bez rozdílu vyznačeného za pomlčkou a to i v případě, že příslušný rozdíl není jen volná proměnná. Zároveň by nemělo dojít k unifikaci žádné proměnné na vstupu. Není-li vstupní parametr rozdílový seznam, měl by program odpovědět false. Časová složitost by měla být lineární s velikostí vstupu a po vrácení správné odpovědi by program neměl vracet další výsledek nebo se zacyklit.
```
?- split_diff([a,b,c|X]-X, L).
L = [a, b, c].
?- split_diff([a,b,c|X]-Y, L).
false.
?- split_diff([a,b,c,d,e]-[d,e], L).
L = [a, b, c].
?- split_diff([a,b,c,d,e]-[d,f], L).
false.
?- split_diff([a,b,c,d|E]-[d|F], L).
false.
```
(1 bod)
(5b)
Napište proceduru mocniny/2, která v prvním parametru dostane přirozené číslo N a ve druhém vrátí seznam všech přirozených čísel menších nebo rovných N, které jsou alespoň druhou mocninou nějakého přirozeného čísla (tzn. tvaru m² nebo m³ nebo m⁴ ... pro nějaké přirozené číslo m). Výsledný seznam by neměl žádné číslo obsahovat vícekrát a program by měl vrátit právě jeden výsledek a pak se nezacyklit. Nulu považovat za přiložené číslo můžete ale nemusíte.
```
?- mocniny(16, L).
L = [1, 4, 8, 9, 16].
```
(1 bod)
(5c)
Napište predikát je_strom/1, který rozhodne, zda graf zadaný seznamem hran je strom (nebo les, není-li souvislý). Hrany jsou neorientované a zadané ve tvaru U-V pro hranu mezi vrcholy U a V. Program by měl odpovědět true nejvýše jednou.
```
?- je_strom([a-b, b-c, a-d]).
true.
?- je_strom([a-b, b-c, a-c]).
false.
```
(1 bod)

17. 3. 2014

Dnes jsme psali písemku, domácí úkoly nejsou.

10. 3. 1014, deadline 17. 3. 2014 15.40

(4a)
Napište predikát is_diff/1, který rozhodne, zda je předaný parametr korektní rozdílový seznam s otevřeným koncem, to znamená výraz ve tvaru [a1,a2,....,an|X]-X, kde X je volná proměnná a a_i jsou libovolne výrazy. Predikát by měl odpovědět true nejvýše jednou. Např:
```
?- is_diff([a,B|X]-X).
true.
?- is_diff([a,B|X]-Y).
false.
?- is_diff([a,B,c]-[c]).
false.
?- is_diff([a,B,c|X]-[c,X]).
false.
```
(0.5 bodu)
Poznámka: Doporučuji pozornosti predikáty jako atom, ground, var, nonvar, ==, \==.
(4b)
Napište predikát clone_diff/2, který dostane jako první parametr rozdílový seznam (pro který by is_diff výše vrátilo true), udělá jeho kopii, která se bude lišit jen v proměnné ukazující na konec, a tu vrátí ve druhém parametru. Predikát by měl odpovědět true nejvýše jednou.
```
?- clone_diff([a,B,c|X]-X, L).
L = [a, B, c|Y]-Y.
```
Původní rozdílový seznam by měl zůstat nezměněný (s neunifikovanou volnou proměnnou), takže bude fungovat následující:
```
?- L=[a,b,c|X]-X, clone_diff(L,M), is_diff(L), is_diff(M).
L = [a, b, c|X]-X,
M = [a, b, c|Y]-Y.
```
(0.5 bodu)
(4c)
Napište predikát perf/2, který dostane seznam čísel a sestaví z něj perfektní vyhledávací strom – vrcholy stromu jsou právě prvky zadaného seznamu (můžete předpokládat, že se žádný neopakuje), pro každý vrchol platí, že prvky v levém podstorum jsou menší než hodnota vrcholu, prvky v pravém podstromu jsou větší než hodnota vrcholu a počet prvků v podstromech vrcholu se liší nejvýše o 1. Po vrácení stromu by program žádný další výsledek vrátit neměl a neměl by se zacyklit.
```
?- perf([6,3,4,9,5,7,1,2], T).
T = t(5, t(3, t(2, t(1, nil, nil), nil), t(4, nil, nil)), t(7, t(6, nil, nil), t(9, nil, nil))) ;
false.
```
(1 bod)
Bonus:
Další bod dostanete, pokud časová složitost bude lineární pro již seřazený vstupní seznam a O(N*log N) v nejhorším případě.

3. 3. 2014, deadline 10. 3. 2014 15.40

(3a)
Napište predikát preorder/2, který v prvním parametru dostane strom zadaný způsobem popsaným u úkolu 2b, a vrátí seznam vrcholů v pořadí, kterému se říká preorder – nejdříve je vypsaný vrchol, pak vrcholy levého podstromu a nakonec vrcholy pravého podstromu. Program by měl vrátit právě jednu odpověď. Například:
```
?- preorder(t(b, t(c, t(e,nil,nil), nil), t(a, t(f,nil,nil), t(d,nil,nil))), X).
X = [b, c, e, a, f, d].
```
(1 bod)
Poznámka: Prázdný strom (nil) je taky strom :-)
Bonus:
Další bod získáte, bude-li predikát preorder reversibilní – schopný zkonstruovat všechny stromy (každý právě jednou) odpovídající seznamu vrcholů předanému ve druhém parametru, například:
```
?- preorder(T, [a,b,c]).
T = t(a, nil, t(b, nil, t(c, nil, nil))) ;
T = t(a, nil, t(b, t(c, nil, nil), nil)) ;
T = t(a, t(b, nil, nil), t(c, nil, nil)) ;
T = t(a, t(b, nil, t(c, nil, nil)), nil) ;
T = t(a, t(b, t(c, nil, nil), nil), nil) ;
false.
```
(3b)
Napište predikát mergesort/2, který seřadí seznam předaný v prvním parametru pomocí algoritmu mergesort a ten vrátí ve druhém parametru. Po vrácení výsledku by mergesort už žádný další výsledek vrátit neměl, ani by se neměl zacyklit. K určení pořadí používejte porovnávací operátory <, >, =<, >=.
```
?- mergesort([1,6,5,2,8], X).
X = [8, 6, 5, 2, 1] ;
false.
```
(1 bod)

24. 2. 2014, deadline 3. 3. 2014 15.40

(2a)
Pro unární aritmetiku kódující čísla pomocí 0 a s/1 napište predikát vyhodnot/2, který vyhodnotí aritmetický výraz obsahující čísla (v unárním zápisu), + (součet), - (rozdíl), * (násobek) a ^ (mocnina) a výsledek vrátí ve druhém parametru. Takže například:
```
vyhodnot(s(s(0)) + (s(0) * s(s(0))) - (s(s(0)) * 0), X).
```
vrátí
```
X = s(s(s(s(0)))).
```
Můžete používat predikáty plus/3 a krat/3 ze cvičení; zároveň předpokládejte, že v žádném rozdílu ve výrazu není druhý operand větší než první.
(1 bod)
Nápověda:
Operátory zapisované infixově jsou až na pořadí zápisu stejné jako jiné funktory a unifikace funguje normálně, ať jsou operandy jakékoli:
```
?- (a + X) + Y = Z + b.
Y = b,
Z = a+X.
```
Takže pro ošetření sčítání v rámci vyhodnot stačí
```
vyhodnot(X+Y, V) :- ...
```
O případné uzávorkováni a priority operátorů ve vstupním výrazu se Prolog už postará sám, takže není potřeba řešit například variantu vyhodnot(X+Y+Z) nějak zvlášť.
(2b)
Jako termy lze v prologu zakódovat i stromy. Třeba tak, že nil značí prázdný strom a t(Vrchol, Levy, Pravy) vrchol stromu (případně by stačilo t/2, pokud by nás nezajímala hodnota ve vrcholu ale jen tvar stromu).
Například strom
```
     a
    / \
   b   c
  /   / \
 d   e   f
```
by byl kódovaný termem t(a, t(b, t(d,nil,nil), nil), t(c, t(e,nil,nil), t(f,nil,nil))).
Napište predikát pocet_listu(Strom, Pocet), který při zadání prvního parametru vrátí ve druhém počet listů. Po vrácení spráné odpovědi by program už žádnou další (ať už stejnou nebo jinou) odpověď vrátit neměl ani by se neměl zacyklit. Pro výše uvedený příklad stormu:
```
?- pocet_listu(t(a, t(b, t(d,nil,nil), nil), t(c, t(e,nil,nil), t(f,nil,nil))), X).
X = s(s(s(0))) ;
false.
```
(1 bod)
Bonus:
Další bod získáte, pokud dotaz pocet_listu(T, n), kde n je nějaké konrétní číslo v unárním zápise, bude postupně vracet všechny stromy s n listy.
Například:
```
?- pocet_listu(T, s(s(0))).
T = t(_G2116, t(_G2120, nil, nil), t(_G2124, nil, nil)) ;
T = t(_G2118, t(_G2122, t(_G2128, nil, nil), t(_G2132, nil, nil)), nil) ;
T = t(_G2118, nil, t(_G2122, t(_G2128, nil, nil), t(_G2132, nil, nil))) ;
T = t(_G2118, t(_G2122, t(_G2132, nil, nil), nil), t(_G2126, t(_G2140, nil, nil), nil)) ;
T = t(_G2118, t(_G2122, t(_G2132, nil, nil), nil), t(_G2126, nil, t(_G2140, nil, nil))) ;
...
```

17. 2. 2014, deadline 24. 2. 2014 15.40

Máte k dispozici databázi s predikáty ze cvičení rodic(Rodic,Potomek), manzele(Manzel,Manzelka), muz(Kdo) a zena(Kdo).

(1a) Napište predikát nevlastni_bratr(B,K), který je splněn, pokud B je nevlastním bratrem K – matka B má za muže otce K nebo obráceně a nejsou to vlastní sourozenci (mohou ale nemusí mít jednoho společného rodiče). (1 bod)
Doplnění: v tomto případě nevadí, pokud program vrátí nějakou odpověď vícekrát; nicméně zacyklit by se neměl.
(1b) Napište predikát dedic_trunu(Dedic,Kral), který postupně vrací dědice v následnickém pořadí. Nejprve je v pořadí nejstarší syn, po něm v odpovídajícím pořádí všichni jeho potomci, následuje další syn současného krále atd. Po všech mužských potomcích následují dcery a zase jejich potomci. Předpokládejte, že údaje o rodičovství v databázi jsou seřazeny chronologicky, takže záznam rodic(otec,prvorozeny_syn) se nachází před rodic(otec,druhorozeny_syn).
Příklad – máme-li náledující databázi:
```
rodic(borivoj, spytihnev).
rodic(borivoj, drahomira).
rodic(borivoj, mlada).
rodic(borivoj, vratislav).

rodic(spytihnev, vaclav).
rodic(spytihnev, kunhuta).

rodic(drahomira, jitka).
rodic(drahomira, boleslav).

zena(drahomira).
zena(mlada).
zena(kunhuta).
zena(jitka).
muz(borivoj).
muz(spytihnev).
muz(vratislav).
muz(vaclav).
muz(boleslav).
```
Dostaneme na dotaz dedic_trunu(X,borivoj) postupně výsledky:
```
X = spytihnev ;
X = vaclav ;
X = kunhuta ;
X = vratislav ;
X = drahomira ;
X = boleslav ;
X = jitka ;
X = mlada ;
false.
```
Za to, že přesně tento systém následnictví některá dynastie využívala, samozřejmě neručím. (1 bod)