Neprocedurální programování, cvičení

• Domů
• O cvičení
• Zápočty
• Poznámky ze cvičení
• Domácí úkoly
• Přihlášení studenti

1. cvičení 2.3.2011

• O cvičení...
• O Prologu (miniopakování z přednášky)
• Syntaxe: jednoduché a složené termy, proměnné, atomy, čísla, řetězce, struktury, seznam
• Program v Prologu: klauzule, fakta, pravidla, procedury, komentáře
• Práce s interpretem Prologu: načtení souboru do paměti pomocí consult('mujprogram.pl'), halt (konec práce), ?- (prompt), listing,...
• Mechanismus kladení dotazů, operátory ',' a ';'
• Anonymní proměnná, "vstupní"/"výstupní" argumenty
• ?-ma_rad(medved,med). % Má medvěd rád med? (oba argumenty jsou vstupní)
  ?-ma_rad(medved,X). % Co/koho má rád medvěd? (první argument je vstupní, druhý výstupní)
  ?-ma_rad(X,med). % Kdo má rád med? (první argument je výstupní, druhý vstupní)
  ?-ma_rad(X,Y). % Vypiš všechny dvojice X,Y tak že X má rád Y (oba argumenty jsou výstupní)
• Backtracking: jak se vyhodnocují dotazy (na příkladech)
• Jednoduché predikáty o rodinných vztazích
• popis databáze rodinných vztahů pomoci predikátů rodic(Rodic,Dite), muz(On), zena(Ona)
• rodice(Rodic1,Rodic2) - různé varianty a možné problémy (cyklení odpovědi, nekonečný výpočet,...) :
• rodice(Otec,Matka):-muz(Otec),zena(Matka),rodic(Otec,Dite),rodic(Matka,Dite).
• rodice(Rodic1,Rodic2) symetricky (finta, aby se odpověď necyklila)
• další predikáty o rodinných vztazích - např. bratr(Bratr,Koho), teta(Teta,Koho),...
• Na rozmyšlenou: tchan(Tchan,Koho), snacha(Snacha,Koho), prastryc(Prastryc,Koho), dedecekzotcovystrany(Dedecek,Pravnouce) a podobně
• Obarveni mapy čtyřmi barvami
• je dána následující mapa (na cvičení byla trochu jiná mapa):
  
• pro tuto mapu jsme definovali predikát obarvi(A,B,C,D,E), kde A,...,E jsou barvy (cervena, modra, zluta, zelena) a sousedni staty nesmi byt obarveny stejně
• dvě různá řešení (jde to i bez negace)
• Modelování aritmetiky
• reprezentace přirozených čísel pomocí termů 0, s(0), s(s(0)),...
  nat(0). % nula je přirozené číslo
  nat(s(X)) :- nat(X). % n+1 je přirozené číslo, je-li n přirozené číslo
  
• lze použít pro test, zda je term přirozené číslo:
  ?-nat(s(medved)).
  false.
  ?-nat(s(s(0))).
  true.
• lze použít i pro generování přirozených číel:
  ?-nat(X).
  X = 0;
  X = s(0);
  X = s(s(0));
  ...
  
• even(X), odd(X) - X je sudé/liché přirozené číslo, různá řešení
• leq(X,Y) - přirozené číslo X je menší nebo rovno přirozenému číslu Y, různá řešení
• Na rozmyšlenou: Je možné modifikovat leq/2 tak, aby volání leq(-X,-Y) vrátilo v konečném počtu kroků libovolnou dvojici přirozených čísel menších než n?
• lt(X,Y) - přirozené číslo X je menší než přirozené číslo Y, různá řešení
• add(X,Y,Z) - Z je součet přirozených čísel X a Y, různá řešení. Některé varianty add, které jsme vymysleli na cvičení, se mohou při výpočtu zacyklit.
• Na rozmyšlenou: jaké budou odpovědi na různé dotazy pro leq, add?
• ?- leq(-X,+Y).
  ?- leq(-X,-Y).
  ?- add(+X,-Y,+Z).
  ?- add(-X,+Y,+Z).
  ?- add(-X,-Y,+Z).
  

2. cvičení 9.3.2011

• Řešení úloh z domácího úkolu a úloh z dněšního testíku
• Modelování přirozených čísel pomocí termů 0, s(0), s(s(0)),...
• mul(+X,+Y,?Z), pow(+X,+Y,?Z), mod(+X,+Y,?Z), fib(+X,?F)
• Varianty mul a mod které se nezacyklí při libovolném dotazu.
• Efektivní řešení fib za pomoci akumulátorů: fib(X,Y):-fib(X,0,s(0),Y).
• Na rozmyšlenou: Efektivní řešení fact(X,F) za pomoci akumulátoru, např.: fact(X,Y):-fact(X,s(0),Y).
• Řešení leq/2 tak, že volání leq(-X,-Y) vrátí v konečném počtu kroků libovolnou dvojici přirozených čísel menších než libovolné n.
• Na rozmyšlenou: predikát pro celočíselné dělení div(+X,+Y,?Z)
• Procedurální a deklarativní význam programu, mechanismus vyhodnocení dotazu - záleží na pořadí termů i na pořadí proměnných (i z hlediska efektivity)
• Procvičení na variantách procedury leq/2, mul/3, add/3.
• Cesta v orientovaném acyklickém grafu
• Popis grafu fakty hrana(Od,Do).
• Rekurzivni predikát cesta(Od,Do) - různé varianty procedury vhodné pro různé typy dotazů a nebezpečí zacyklení
• Unifikační algoritmus - zopakování
• Hrátky s unifikací
• Uvažujeme následující program:
  g(t(A,_),t(A,_)).
  f(h(X,_),X).
  
• Jaké budou odpovědi interpretu Prologu na následující dotazy?
  ?- g(X,Y).
  X = t(_023,_024) , Y = t(_023,_025)
  
  ?- g(t(X,Y),Z).
  X = _ , Y = _ , Z = t(X,_026)
  
  ?- g(t(a,b),Z).
  Z = t(a,_027)
  
  ?- f(X,Y).
  X = h(Y,_028) , Y = _
  
  ?- f(X,c).
  X = h(c,_029)
  
  ?- f(X,X).
  Error 7, System Stack Full, Trying vars/2
  
• Jednoduché procedury pro práci se seznamy:
• prvek(X,S), je_seznam(S)
• sudy(S), lichy(S) - uspěje, je-li S seznam sudé délky / liché délky
• pridejnazacatek(Seznam,Prvek,VyslednySeznam), pridejnakonec(Seznam,Prvek,VyslednySeznam), smazprvni(Seznam,VyslednySeznam), smazposledni(Seznam,VyslednySeznam)
• prefix(Seznam,Prefix), suffix(Seznam,Suffix)
• Na rozmyšlenou: prefixy(Seznam,SeznamPrefixů), suffixy(Seznam,SeznamSuffixů)
• usek(Seznam, Usek) - pomoci prefixu a suffixu
• podseznam(+S,?PodS) - seznam PodS je podseznamem seznamu S (ve smyslu podmnožiny). Predikát postupně generuje všechny podseznamy seznamu. Například pro S=[a,b,c,d] generuje podseznamy [a,b,c,d], [b,c,d], [c,d], [d],[], [a,c,d], [a,d] atd.
• Složitost jednotlivých procedur.

3. cvičení 16.3.2011

• Řešení úloh z domácího úkolu a úloh z dněšního testíku
• Rodina - bratri/2, mladsisestra/2, starsibratr/2, nejmladsisestra/2, nejstarsibratr/2 - různá řešení
• Cesta v orientovaném acyklickém grafu (rozšíření příkladu z minule) - cesta(+Od,+Do,-Cesta)
• suffixy(+Seznam,-SeznamSuffixů)
• Další procedury pro práci se seznamy
• odstran(Seznam,Prvek,VyslSeznam) - smaže první výskyt prvku v seznamu, různé varianty (uspět/selhat, pokud prvek v seznamu není)
• odstranVsechny(+Seznam,+Prvek,VyslSeznam) - smaže všechny výskyty prvku v seznamu
• Na rozmyšlenou: odstranVsechny(Seznam,Prvek,VyslSeznam), který dá false, pokud prvek v seznamu není
• spolecne(Seznam1,Seznam2,Spolecne) - společné prvky dvou seznamů, různé varianty (pomocí predikátu odstran)
• permutace(Seznam1,Seznam2) - pomocí procedury spolecne
• prostredni(S,X) - X je prostředním prvkem seznamu S.
• Řešení v kvadratickém čase (pomocí predikátu smazposledni)
• Řešení trikem v lineárním čase:
  prostredni(+S,-X):- prostredni(+S,+S,-X).
  prostredni([_],[X|_],X).
  prostredni([_,_],[X|_],X).
  prostredni([_,_|T1],[_|T2],X):- prostredni(T1,T2,X).
• Na rozmyšlenou: napoloviny(+S,-S1,-S2), natretiny(+S,-S1,-S2,-S3)
• spoj(S1,S2,S) - seznam S je konkatenací seznamů S1 a S2
• reversespoj(S1,S2,S) - seznam S je konkatenací obráceného seznamu S1 a seznamu S2. Řešení pomocí akumulátoru.
• reverse(?S,?OS) - seznam OS vznikne otočením seznamu S. Různá řešení - elegantně pomocí reversespoj.
• palindrom(S) - slovo reprezentované jako seznam S, které se čte stejně popředu i pozpátku. Pomocí reverse.
• levarotace(+S,?LR), pravarotace(+S,?PR) - rotace seznamu o jeden prvek. Například, je-li S=[a,b,c,d], bude LR = [b,c,d,a] a PR = [d,a,b,c]. Různá řešení - elegantně pomocí reverse/2
• Matice
• Matice reprezentujeme jako seznamy řádků, prázdná matice.
• prvekMatice(+M,?X) - X je prvkem matice M.
• ctvercova(+M) - matice M je čtvercová.
• obdelnikova(+M) - matice M je čtvercová.
• Na rozmyšlenou: matice(+M) - M je matice.
• transpozice(+M,-TM)- převod matice na transponovanou matici. Řešení pomocí urezsloupec(+Matice,-PrvniSloupec,-Zbytek). Na rozmyšlenou zbylo jiné řešení pomocí pridejsloupec(+Matice,+PrvniSloupec,-NovaMatice)
• diagonala(+M,-D) - D je hlavní diagonála matice M. Pouze myšlenka, zbylo na rozmyšlenou.
• rotaceR(+M,-OM), rotaceL(+M,-OM) - Otočení matice M doprava a doleva. Pouze myšlenka, zbylo na rozmyšlenou.

4. cvičení 23.3.2011

• Řešení úloh z domácího úkolu a úloh z dněšního testíku
• napoloviny/3, natretiny/4, polovinymuzu/3, tretinymuzu/4
• rozbal(+M,-S) - Bylo za domácí úkol. Do seznamu S vkládá prvky matice M tak, jak leží na spirále. Různá řešení - 4 predikáty, pomocí otočení o 90 stupňů,...
• rotaceR/2, rotace180/2, rotaceL/2, diagonala/2
• sloupec1/3 - připojí k matici první sloupec
• Problém s cyklením u procedur s maticemi a jeho řešení
• Aritmetika v Prologu
• Úvod do aritmetiky - operátor is, relační operátory, výrazy
• Rozdíl mezi =, ==, =:=, \=, \==, =\=
• min(+X,+Y,?Min) - Min je minimum čísel X a Y
• minseznam(+S,?Min) - Min je minimální prvek seznamu S. Různá řešení - rekurzivně / iterativně za využití akumulátoru.
• minsort(+T,-ST) - T je seznam, ST je setříděný seznam T metodou přímého výběru minima. Řešení pomocí minseznam/2 a vhodného delete/3.
• vyber(+S1,+N,-S) - Vybere ze seznamu (kladných čísel) S1 prvky se součtem N do seznamu S. Funguje opakovaně díky backtrackingu. Našli jsme různá řešení.
• kombinace(+S1,+K,-S) - Postupně backtrackingem ze seznamu S1 generuje všechny K-prvkové kombinace (podmnožiny) prvků. Nestihli jsme, jen zadání.
• variace(+S1,+K,-S) - Postupně ze seznamu S1 generuje všechny K-prvkové variace prvků. Nestihli jsme, jen zadání.
• Některé standardní predikáty
• atom(X). X je atom
  atomic(X). X je atom nebo číslo
  compound(X). X je struktura
  number(X). X je číslo
  integer(X). float(X). X je přirozené / reálné číslo
  var(X). X je nekonkretizovaná proměnná
  nonvar(X).
  
• Sčítání, kde libovolný argument může být proměnná
  scit(A, B, C) :- number(A), number(B), C is A + B.
  scit(A, B, C) :- number(A), var(B), number(C), B is C - A.
  scit(A, B, C) :- var(A), number(B), number(C), A is C - B.

5. cvičení 30.3.2011

• Řešení úloh z domácího úkolu
• multijoin(+S,-RS) - různá řešení, ilustrace použití predikátu řezu nebo \=
• rozvin(+S,-RS) - různá řešení, ilustrace použití predikátu řezu nebo testu number(X)
• Aritmetika v Prologu - dokončení
• kombinace(+S1,+K,-S) - Postupně backtrackingem ze seznamu S1 generuje všechny K-prvkové kombinace (podmnožiny) prvků.
• variace(+S1,+K,-S) - Postupně ze seznamu S1 generuje všechny K-prvkové variace prvků.
• Matice - hrátky se spirálou:
• rozbal(+M,-S) - Bylo za minulý domácí úkol. Do seznamu S vkládá prvky matice M tak, jak leží na spirále.
• zabal(+M,+N,+S,-Mat) - Inverzni predikat k predikatu rozbal/2. Prvky seznamu S posklada po spirale do matice Mat tvaru MxN. Řešení přímo nebo pomocí inverzní operace.
  zabal(+M,+N,+Vektor,-Matice):-generujMatici(M,N,MP), rozbal(MP,VP), Vektor=VP, Matice=MP.
• generujVektor(+M,-Vektor) - Procedura vygeneruje seznam volných proměnných.
• generujMatici(+M,+N,-Vektor) - Procedura vygeneruje matici volných proměnných. Pouze myšlenka řešení, na rozmyšlenou.
• Operátor řezu !, \=, \+, not
• Máme program p(1). p(2):-!. p(3). Jak bude vypadat odpověř programu na následující dotazy?
  ?-p(X).
  ?-p(X),p(Y).
  ?-p(X),!,p(Y).
  ?-p(X),p(Y),!.
  
  ?-p(X).
  X=1;X=2
  
  ?-p(X),p(Y).
  X=Y=1;
  X=1,Y=2;
  X=2,Y=1;
  X=Y=2
  
  ?-p(X),!,p(Y).
  X=Y=1;
  X=1,Y=2
  
  ?-p(X),p(Y),!.
  X=Y=1
  
  
• Negace v Prologu pomocí operátoru řezu:
  ruzne(X,Y):- X = Y,!,fail.
  ruzne(_,_).
  
  not(X):- call(X),!,fail.
  not(X).
  
  
• Na rozmyšlenou: V čem spočívá problém s negací v Prologu?
• Další příklady na použití řezu - kategorie, neproceduralni, jazyk
• Modelování if-then-else v Prologu pomocí operátoru řezu (if b then c else d) na příkladu multijoin:
  a(X):-b(X),!,d(X).
  a(X):-c(X).
  
• Další užitečné predikáty pro práci se seznamy
• substituce(+X,+S,+Y,-T) - Za každý prvek X v seznamu S substituuj prvek Y. Výsledek je seznam T. Různá řešení - využití operátoru řezu.
• Unární aritmetika
• [] reprezentuje 0, [1] reprezentuje 1, [1,1,1,1,1] reprezentuje 5, atd.
• soucet(+X,+Y,-S) - Sčítání v unární aritmetice pomocí konkatenace seznamů.
• soucin(+X,+Y,-S) - Násobení v unární aritmetice. Různá řešení. Hezký trik:
  nasob(A,B,C):-substituce(1,A,B,S),multijoin2(S,C).
• Na rozmyšlenou: predikáty pro odčítání a dělení v unární aritmetice.
• Definice operátorů v Prologu
• Součtové seznamy
• Pro jaké operace se tato datová struktura hodí?
• Základní operace nad součtovými seznamy: přidej prvek na začátek, přidej prvek na konec, smazání prvku ze začátku, smazání prvku z konce, otočení, převod mezi obyčejným a součtovým seznamem
• Rozdílové seznamy
• Popis. Pro jaké operace se tato datová struktura hodí?
• append(A-B,B-C,A-C) - vysvětlení, jak to vlastně funguje.
• quicksort(+Seznam,-RozdilovySeznam) - další využití rozdílového seznamu pro snížení časové složitosti.
• Permutace
• Různé reprezentace, myšlenka řešení domácích úloh - lexikograficky následující permutace, generování k-té permutace v čase O(kn) (k-krát nextPerm) a v čase O(n^2).

6. cvičení 6.4.2011

• Řešení úloh z domácího úkolu zde
• Povídání o zápočtových programech
• Podmínky, termíny.
• Návrhy témat.
• Další zdroje možných témat: Hric, Barták..
.
• Operátor =..,
• Přístup k parametrům struktury, konstrukce struktury z parametrů.
• Term =.. Seznam % Seznam = [Funktor|Argumenty]
• maplist(+Predikát,+Seznam,-Výsledek) Aplikuje Predikát/2 na každý prvek seznamu Seznam. Výsledek je výsledný seznam. Aplikace maplist - první a poslední prvek matice.
• substituce(+Term, +Co, +Cim, -VyslTerm) Provede v termu Term substituci všech podtermů Co za termy Cim. Výsledný term je VyslTerm.
• Procedura name, řetězce v Prologu
• name(?Atom,?Seznam) Převod atomu na řetězec a nebo zpět. Řetězec v Prologu je reprezentován jako seznam ASCII kódů písmen.
• spoj_termy(+T1, +T2, -T) Spojení termů a(a1,...,aN), b(b1,...,bM) -> ab(a1,...aN,b1,...,bM).
• Lexikografické třídění termů pomocí operátorů @<, @>, @=<, @>=. Standardní predikáty sort, msort.
• Operátory, které sesbírají všechny termy s nějakou vlastností
• bagof(+Term,+Cíl,-Seznam) Seznam je seznam všech instancí Termu, které splňují Cíl.
• setof(+Term,+Cíl,-Seznam) Totéž, ale Seznam je uspořádaný, bez duplicit.
• findall(+Term,+Cíl,-Seznam) Shromáždí všechna řešení bez ohledu na volné proměnné,vždy uspěje.
  
  hrana(a,b).
  hrana(a,c).
  hrana(a,d).
  hrana(b,c).
  
  ?-bagof(X,trida(X,c),S). % odkud vede hrana do c?
  X=_,S=[a,b].
  
  ?- bagof(op(c,X),hrana(X,c),S). % mohu vytvářet strukturu
  X=_,S = [op(c,a),op(c,b)]
  
  ?- bagof(X,hrana(X,a),S). % Nesplnění cíle - neúspěch.
  no
  
  ?-bagof(X,hrana(X,Y),S). % odkud vede hrana?
  X = _ , Y = b ,S = [a] ;
  X = _ , Y = c ,S = [a,b] ;
  X = _ , Y = d , S = [a] ;
  
  ?- findall(X,hrana(X,Y),S). % odkud vede hrana?
  X = _ , Y = _ , S = [a,a,b,a]
  
  
• Práce se vstupem a výstupem
• Interakce programu s uživatelem.
• Konečný a nekonečný cyklus.
• Na rozmyšlenou: Zkuste v Prologu modelovat forcyklus...
• Stromy
• Různé reprezentace. Binární stromy (z přednášky). Binární vyhledávací stromy - byly na přednášce.
• Reprezentace obecného stromu pomocí binárního.
• Vrstevnatý výpis stromu.
• Příklad: dopln( +Seznam čísel,+Hodnota, - Seznam). Doplní do seznamu závorky, '+', '-', '*', aby byla hodnota "výrazu" rovna Hodnotě.
• vyraz(+Seznam, -Vyraz). Vyrobí ze seznamu čísel term = výraz.
• vypis(+Vyraz, -Seznam). Vypíše výraz ( = strom) do seznamu (včetně závorek).
• Zbylo na rozmyšlenou.

7. cvičení 13.4.2011

• Řešení úloh z domácího úkolu
• vyhodnot, splnitelna,...
• halda,...
• Stromy v Prologu - pokračování
• Dokončení příkladu z minule.
• Na rozmyšlenou: Výpis stromu (definovaného pomocí binárních operátorů) do seznamu. Různá řešení, využití akumulátoru místo zřetězení.
• Dokonale vyvážený binarní vyhledávací strom.
• postav(+RostSez,-Strom) - různá řešení
• postav(+RostSez,-Strom) - efektivně bez dělení seznamů s využitím akumulátoru - postav(+N,+RostSez,-Strom,-Zbytek)
• Lisp - SCHEME
• Syntaxe LISPu. Základní formy ve SCHEME. Definice funkcí.
• Definovali jsme jednoduché funkce:
• Výpočet faktroriálu.
• Výpočet n-tého fibonacciho čísla. Více variant.
• Výpočet délky seznamu.
• Konkatenace dvou seznamů.
• Na rozmyšlenou: Otočení seznamu pomocí akumulátoru.
• Užitečné funkce pro práci se seznamy:
• Definovali jsme funkci (map f s), která má jako parametry funkci f (f je funkce s jedním parametrem) a seznam s. Funkce map aplikuje funkci f na každý prvek seznamu s a vrátí výsledný seznam.
  ( define (map f s) ( if (null? s) '() ( cons (f ( car s)) (map f (cdr s)))))
• Definovali jsme funkci (foldr f p s), která má jako parametry seznam s, prvek p a funkci f (f je funkce se dvěma parametry). Funkce foldr vrátí p pro prázdný seznam s a hodnotu funkce f rekurzivně na další prvek seznamu a zbytek ("to, co přišlo z rekurze"). Například pro seznam (list 1 2) funkce foldr spočte ( f 1 (f 2 p)), pro seznam (list 1 2 3 4) funkce app spočte ( f 1 ( f 2 ( f 3 (f 4 p)))).
  (define (foldr f p s) (if (null? s) p (f (car s) (foldr f p (cdr s)))))
• Inkrementace všech prvků seznamu pomocí funkce map.
• Výpočet délky seznamu, minimálního prvku seznamu, append dvou seznamů pomocí funkce foldr.
• Otočení seznamu pomocí funkce foldl.
• Závěsný prostorový mobil - za domácí úkol.

8. cvičení 20.4.2011

• Řešení úloh z domácího úkolu a z testíků
• Mobily - ekvivalelntni - řešení s kvadratickou složitostí + finta s @<
• Vrstevnatý výpis stromu - možné řešení
• Grafy v prologu
• Různé reprezentace grafu
• Průchod grafem do šířky a do hloubky
• Prohledávání stavového prostroru
• Farmář, vlk, koza, zelí
• Různé reprezentace stavů a hran + samotné prohledávání
• Dynamické predikáty: assert, retract
• Adventure hry
• Vajíčka, slepice, liška
• Interaktivní programy v Prologu
• HASKELL - úvod, interpretery

9. cvičení 27.4.2011

• Rozbor řešení úloh z domácího úkolu a testíku
• nádoby, lidojedi - reprezentace stavu
• prohledávání grafu do šířky
• cyklus v grafu
• HASKELL - úvod
• Definice funkcí (včetně typové signatury), funkce více proměnných, curryfikace, lambda funkce a anonymní proměnné. Základní definované typy.
• Jednoduché funkce - součet pětkrát jinak. Výpočet faktoriálu.
• Funkce vs. operátory. Prefixový a infixový zápis. Základní definované aritmetické a relační operátory. Booleovské operace. Definice vlastního operátoru na příkladu (&&).
• Základní vzory (patterns) na jednoduchých příkladech - stráže, let, where, if, case, @, chybové hlášky (definice vlastních)
• Jednoduché funkce - signum třikrát jinak, výpočet největšího společného dělitele, krácení čísel, bmi Index...
• Seznamy vs. ntice. Standardně definovné funkce pro práci se seznamy: ++, !!, head, tail, null, length, fst, snd...
• HASKELL - příklady na seznamy
• Definovali či využili jsme některé standardní funkce nad seznamy - head, tail, length, take (vezme prvních n prvků seznamu), drop, map, lshift, takeMap.
• Definovali jsme standartní funkci takeWhile, která je obdobou while cyklu (dokud prvky splňují podmínku, dávej je do výsledného seznamu).
  takeWhile :: (a -> Bool) -> [a] -> [a]
• Pomocí takeWhile jsme definovali funkci kladny, která vrátí kladný prefix seznamu.
  kladny :: [Int] -> [Int]
  kladny = takeWhile (>0)
  
• Definovali jsme standartní funkci filter, která vloží do výsledného seznamu jen ty prvky původního seznamu, které splňují podmínku.
  filter :: (a -> Bool) -> [a] -> [a]
• Pomocí filter jsme definovali funkci kladny1, která vrátí všechny kladné prvky seznamu.
  kladny1 :: [Int] -> [Int]
  kladny1 = filter (>0)
  

10. cvičení 4.5.2011

• Rozbor řešení úloh z testíku a domácích úkolů
• Definice typů - co nejobecnější
• standardní funkce foldl :: (a -> b -> a) -> a -> [b] -> a
  standardní funkce foldr :: (a -> b -> b) -> b -> [a] -> b
• Seznamy - pokračování
• Standardní funkce nad seznamy v souboru standard.pre (Prelude.hs): head, tail, null, length, ++, !!, take, map, drop, filter, takeWhile (viz. minule)
• Definovali jsme standartní funkci zip, která má na vstupu dva seznamy a vloží do výsledného seznamu dvojice prvků (zbytek delšího ze seznamů zahodí).
  zip :: [a] -> [b] -> [(a,b)]
• Definovali jsme standartní a celkem užitečnou funkci zipWith, která funguje jako zip, ale aplikuje funkci na výslednou dvojici.
  zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
• Pomocí zipWith jsme definovali funkci soucetVektoru, která sečte dva celočíselné seznamy.
  soucetVektoru :: [Integer] -> [Integer] -> [Integer]
  soucetVektoru = zipWith (+)
• Definovali jsme standartní funkci flip, která prohodí parametry funkce.
  flip :: (a -> b -> c) -> b -> a -> c
  flip f y x = f x y
  > zipWith (flip' div) [2,2..] [10,8,6,4,2]
  [5,4,3,2,1]
• Pomocí funkcí foldl/foldr jsme definovali funkce pro součet a součin prvků seznamu, skalární součin prvků seznamu a otočení seznamu.
• Hornerovo schéma pomocí foldl.
  horner :: Num a => [a] -> a -> a
• Na rozmyšlenou: Eratosthenovo síto pro generování prvočísel ("na jeden řádek").
• Rozsahy, generování (nekonečných) seznamů.
• Nekonečné seznamy - nekonečný seznam nul, nekoněčný seznam přirozených čísel pětkrát jinak, mocniny,...
• Kartézský součin seznamů - rozdíl mezi [(x,y) | (x,y) <- zip s t ] a [(x,y) | x <-s, y <-t ]
• Kartézský součin přirozených čísel - různé způsoby, na rozmyšlenou: generování po diagonálách
• Pomocí zip a zipWith jsme definovali Fibonacciho posloupnost.
  fibon :: [Integer]
  fibon = 0:1: [x+y | (x,y) <- zip fibon (tail fibon) ]
• Matice jako seznamy seznamů
• Definovali jsme funkci unitMat, která vytvoří jednotkovou matici jako nekonečnou datovou strukturu.
  unitMat :: [[Int]]
• Definovali jsme funkci digMat, která vytvoří nekonečnou matici s danou diagonálou.
  digMat :: Int -> [[Int]]
• Na rozmyšlenou: Totéž pro konečnou diagonálu.
• Definovali jsme funkci soucetMatic, která sečte dvě matice stejných rozměrů.
  soucetMatic :: Num a => [[a]] -> [[a]] -> [[a]]
  soucetMatic = zipWith (zipWith (+))
• Na rozmyšlenou (na příště):
  transponuj :: [[a]] -> [[a]]
  podmatice x1 x2 y1 y2

12. cvičení 11.5.2011

• Rozbor řešení úloh z testíku a domácích úkolů
• Nekonečné posloupnosti - různá řešení
• Matice jako seznamy seznamů - pokračování
• Definovali jsme funkci diagMat, která vytvoří (potenciálně nekonečnou) matici (na diagonále a nad ní jedničky, pod ní nuly).
  diagMat :: Int -> [[Int]]
• Definovali jsme funkci vynasobSkalarem, která vynásobí matici skalárem.
  vynasobSkalarem :: Num a => a -> [[a]] -> [[a]]
  vynasobSkalarem x = map ( map (*x))
• Definovali jsme funkci transponuj, která transponuje matici (pomocí zipWith).
  transponuj :: [[a]] -> [[a]]
• Definovali jsme funkci podmatice x1 x2 y1 y2, která z matice vybere podmatici s danými souřadnicemi levého horního a pravého dolního rohu (pomocí map, take a drop).
• Nekonečná posloupnost
• Definovali jsme funkci posl, která vytvoří nekonečnou upořádanou posloupnost se členy 2^i*3^j*5^k pro přirozená čísla i,j,k.
  posl ::[Int]
  Různé varianty - pomocí merge.
• Na rozmyšlenou: Zobecnění pro seznam čísel / prvočísel.
• Třídy typů
• Základní třídy typů a operace na nich (na příkladech)
• Definice vlastních typů a tříd (na příkladech).

12. cvičení 18.5.2011

• Mocninné řady - zadání
• Různá řešení.
• Rozbor řešení úloh z domácích úkolů
• Definovali jsme datový typ Zlomek jako instanci třídy Eq a Num.
• Stromy.
• Pole v Haskellu.
• Fibonacciho posloupnost.
• Malá násobilka.
• Dva větší příklady na dynamické programování - mince a mřížka.