/* cviceni neproc.prog 2010+2012 v. 3.6.2010 27.3.2012 21.3.2014, 20.5. Skratky: Predp_oklady, Uloha, Var_ianta, Question, Answer, Apl_ikace, DC_viceni 1.cv 2014: struktury 2012: rodicovske vztahy: prarodic/2 + trasovani, ded/2, jeRodic/1, sourozenec/2, vlastniSourozenec/2, teta, bratranec; predek + var. 2.cv 2014: Datum 8x, rodic/2, unarni reprezentace cisel 2012: unarni reprezentace: Soucet, 2x, soucin 2x +akumulator, rozdil na soucet interpret datova struktura datum, ... komplexni cislo, (2-4 strom) 3.cv 2014: biootoc, transpozice matice 2012: seznamy: sufix, prefix, sufixy, prefixy (vsechny), bioinf.otoceni 2012: osetrovani chyb/typu, dva interfejsy -permutace - opak, 2 varianty kombinace, s opakovanim, variace 2010: kartezsky soucin: 2, 3, N mnozin ? dalsi kombinace, permutace, variace, podle lex. poradi. 4.cv 2014: Kombinace, seznam reseni ; stromy/BVS-stavba, DC: zhaldovateni 2012: jak vypada insertsort pri zpracovani mezivysledku, akumulatoru, rekurzi podle vystupu BVS na usp. seznam, seznam na Haldu, Heapsort-cast 2010: transpozice matice, scitani, nasobeni matic, nasobeni konstantou .s.. vyhodnocovani maticoveho vyrazu kontrola rozmeru matice vsechny kombinace - seznam reseni kartezsky soucin ? heapsort - vybirani z haldy 5.cv 2014: lookup2D ; mnoziny, prunik 3x, interpret 2012: Aritmetika: Skalarni soucin sks/3, (faktorial/2), fibonacciho p., jine posl. Kartezsky soucin, varianty dat.str., kart.s. pro n seznamu + listify/2 Vyhledavani: lookup/3, v seznamu, ve strome, slozeny klic: lookup2D DC: vybrani podle podminky v n-arnim strome 2010: (spracovanie stromov - binarnych: vkladanie, vypustanie, AVL) (lookup, lookup2D ) zjednodusovanie log. formuli: vyhodnocovani bylo na prednaske prevod formule na NNF (Negation normal form), DNF, CNF N-arni stromy: vraceni podstromu podle cesty Spojeni hranove ohodnocenych stromu ? histogramy - multimnoziny 6cv. 2014: orezani binarniho stromu, cesta/find v N-arnim stromu, slucovani usporadanych N-stromu (struktury ficur); DC: (std) prevod N-stromu na binarni a zpet ; var: tabelovany vypis N-stromu 2012: cerveny a zeleny rez, rez vs. not. vs if-then-else vyhledavani v NSstrome spojovani NStromu evalVF, s promennymi, prevod do CNF 2010: rubikova kostka - navrh struktury barveni grafu - heuristicky (pomoci nezavisle mnoziny) staticke setrideni vrcholu, i druhotne kriteria dynamicke setrideni vrcholu DC: hamiltonovska kruznice (izomorfizmus grafu - rozkladovy algoritmus) 7cv. 2014: programovani v malem/strednim/velkem, operatory, VF: (predn.: tvar FormuleVyrokoveho Poctu, vyhodnoceni, splnitelnost - s dosazovanim do volneho ohodnoceni); nahrada/substituce promennych; prevod na DNF/CNF (3 fazy), Var: prevod v 1 fazi 2012: generuj a testuj: Obecne CSP (premenne, domeny a podm.), priklady, damy na sachovnici, rozhodovaci (vs. optimalizacni) p. damy: moznost nekolika reprezentaci (s ruznymi implicitnimi podminkami) generuj a testuj (hruba sila), vyhody, nevyhody, jedno reseni vs. vsechna reseni pouziti findall, pametova narocnost vs. Lazy(Hs), casova narocnost, certifikaty NPU varianty: generuj po castech a hned testuj, CP/CSP: testuj a generuj vsechna reseni explicitne: generuj a filtruj, nevyhody (jiny pristup): izomorfizmus grafu: naivne vs. deleni na tridy osli mustek : generovani castecnych reseni ~> "prohledavani stavu" jako prohl. grafu! Stavy: farmarVlkKozaZeli, rubikova kostka, barveni grafu, ... Rubikova kostka, reprezentace: 1. povrchova(=syntakticka), semanticka: kosticky+orientace syntakticka: sdruzovat steny tah/3 s pomenovanim, odvozene tahy, tahy/3 jako interpret interprety/DSL: priklady ; read zdarma+operatory ; reprezentace promennych pocitani s multimnozinami (bags): isBag, unionBag/2, ..., unarni fce/normalizace na soucet 1 koncove podminky, zobecneni na pravdepodobnosti reprezentace: usporadana vs. neusporadana, vhodnost normalizace (pri makeBag) - bez opak. a cetn. 0 2010: rez: ord_union, union vyber podstromu podle podminky: top, all, bottom 8cv. 2012: reg. vyrazy a derivace RV - kod 2010: technika: map2/4 - aplikace soucet vektoru, matic foreach/2 - funkc. param p/1 mapBT - map pro binarni stromy konstrukce stromu aho-corasick reg. vyrazy a derivace RV - kod 9cv. Scheme filter split v Quicksorte, predani lambda funkci (zdvih) hornerovo schema 3x mk_BT (make_binary_tree) DC: map, insertBT 10cv. Haskell - klouzavy prumer ze 3 - klouzavy prumer z n - mergesort, sude, liche, merge - testKomut - kartezsky soucin - filter - tridy ekv. - lookup, zjednoduseny - automaty (2x), reprezentace DKA vs. NKA, krok - (rychle umocnovani) - (FFT) 11.cv. HS 2012 -- krokovac konecnych automatu (det., nedet.) -- vyhodnocovani konc. podminky u nedet. -- any/all, (or/and) -- zip, zipWith, zip3 -- grafy, reprezentace -- opacny graf -- DC: zdvojeni grafu (... a jine operace) 12.cv 2012 -- hi-ord funkce -- huffmanovo kodovani a) kodovani podle tabulky b) prevod stromu na tabulku c) postaveni huff. stromu d) dekodovani podle stromu ... 12.cv 2014 (Hs 3) 13.cv 2014 (Hs 4) -- cvicime : strucne seznamy - pytagorejske cisla - opacny graf - unionL :: [[a]] -> [a] - FFT - procisla , sito - unarni Nat, aktivni konstruktory - usporadani (spravedlive): po uhloprickach, (maxlex) - porovnani dvojich, next: dalsi dvojice, ... 13.cv 2012 -- fold a varianty 14.cv 2014 (Hs 5) 1) nacitani prefixniho vyrazu 2) foldNT, sizeNT, depthNT 3) huffmanovo kodovani a) kodovani podle tabulky b) prevod stromu na tabulku c) postaveni huff. stromu d) dekodovani podle stromu -------- programatorske a jine techniky a idiomy: - tok dat: - strukturalni rekurze (podle _zadanych_ dat) - skladani substituci - akumulator - stav - rekurze podle vystupu (~unfold) - interfejsova klauzule/predikat - seznam vysledku - vystup: 1. backtrackingem, 2. seznam vysledku, 3. hodnoty stavu/akumulatoru, (4. hodnoty argumentu v rekurzi) ... - testy selhanim, osetreno (vyse) u volani, a mix - explicitni vysledek - deterministicke rozhodovani, podle toku dat - ~"zarazka", pridani "umele" urovne navic (typicky u koncove podminky) - kontrola pri vstupu - 2 interfejsy - interpret - DSL Domain Specific Language - matice,vektory ; mnoziny, multimnoziny ; reg. vyrazy ; - data: - predavani dat/options - pojmenovani (testovacich) dat: grafy - variantni reprezentace - regularni datove typy, s tagy; bez catchAll klauzule (a rezu) - nestandardni reprezentace: seznamy jako cisla - neuplne datove struktury - rozdilove seznamy - generuj a testuj - testovani vlastnosti (Quickcheck) - stavovy program ? trampolina,(binarizace) (tabelace?) (aktivni konstruktory) */ % 1.cv + 2012 % rodicovske vztahy rodicovske vztahy: prarodic/2 + trasovani, ded/2, jeRodic/1, sourozenec/2, vlastniSourozenec/2, teta, bratranec; predek + var. % ... % 2.cv - 2012 % Soucet, 2x, soucin 2x +akumulator+interface, rozdil na soucet % pocitani s numeraly s(s(0)) - (pouze) jako ukazka rekurze % i jine struktury, napr. seznam, resp. jeho delku, lze pouzit podobne % soucet1 : strukturalni rekurze, "skladani substituci" % rekurze muze byt rizena 1. nebo 3. argumentem soucet1(0, Y, Y). soucet1(s(X), Y, s(Z)) :- soucet1(X,Y,Z). % tok dat: % ?- soucet1(s(s(0)), s(0), V) % 2.kl s(0) s(0) V' ... V=s(V') % 2.kl 0 s(0) V'' V'=s(V'') % 1.kl uspech 0 s(0) s(0) V''=s(0) % slozenim substituci V= s( s( s(0) )) % v obecnem pripade, kdy neni mezivysledek vlozen unifikaci, musime mezivysledek % postspracovat (napr. v faktorialu, quicksortu, mergesortu, ...) % Nemame pristup na uz zpracovane data, zpracovavane od "konce" datove struktury % soucet2 : akumulator; jako akumulator pouzivame 2 argument soucet2(0, Y, Y). % predani akumulatoru soucet2(s(X), Y, Z) :- soucet2(X, s(Y), Z). % tok dat: % ?- soucet1(s(s(0)), s(0), V) % 2.kl s(0) s(s(0)) V % 2.kl 0 s(s(s(0))) V % 1.kl uspech 0 -''- V=s(s(s(0))) % v obou pripadech plati invariant X+Y = Z na kazde urovni rekurze % jen soucet1/3 Z meni. soucet2/3 Z nemeni, protoze smeny se akumuluji v akumulatoru % Srovnani Akum vuci postsprac: Mame pristup na jiz zpracovane data, % zpracovavane od zacatku datove struktury % DC: soucin1 - pomoci postprocesingu % soucin2 - akumulator % potrebujeme samostatny *argument* pro akumulator, protoze druhy argument musime predavat % nasledne potrebujeme interfaceovy predikat soucin2(X,Y,Z) :- soucin2a(X,Y,0,Z). soucin2a( 0, _Y,A,A). % baze, predani vysledneho akumulatoru soucin2a(s(X), Y,A, Z) :- soucet(A,Y,A1), soucin2a( X, Y,A1, Z). % Charakteristiky "akumulatoru": 1) interface 2) dodatecny argument - akumulator % 3) pocatecni hodnota Aku 4) zmena Aku v rekurzi, vysledkovy arg. bez zmeny % ! nelze pouzit soucin2(-X,-Y,+Z) % rozdil1(+X,+Y,?Z) :- soucet1(+Y,?Z,+X) rozdil1(X,Y,Z) :- soucet1(Y,Z,X) % interpret, lepsi interface k aritm. vyrazum (a jinym vyrazum) % zatim bez promennych % evalAV(+AV,-Vysledek) :- vyhodnoti AV na numeral V evalAV(N,N) :- nat(N). % koncova podminka, numeral evalAV(AV1+AV2, V) :- evalAV(AV1,V1), evalAV(AV2,V2), soucet(V1,V2,V). % podobne klauzule pro dalsi operace % ?- evalAV( s(0) + s(s(0) + s(s(s(0))) , V). % ?- evalAV( s(0) + s(s(0) - 0 * s(s(0)) , V). % DC: div, mod % pro strucny kod: pocitat oboje a potom si vybrat v interface /* Shrnuti - zpusoby rekurze: a) postspracovanim mezivysledku (vcetne skladani substituci) b) akumulator c) podle struktury vystupu - permutace1/2 -- Jaka je vhodna/spravna datova struktura pro datum/3 ; moznosti jsou: a) [2012,2,29] b) datum(2012,2,29) c) datum(29,2,2012) d) datum(29,'únor',2012) e) datum(den(29),mes(2),rok(2012)) f) [den(29),mes(2),rok(2012)] g) [den-29, mes-2, rok-2012 ] g2) [-(den,29), -(mes,2), -(rok,2012)] h) "20120229" string i) '20120229' spec. konstanta j) d20120219 konstanta k) 20120219 cislo obvykle je spravna volba b) - je kompaktnejsi (pametove uspornejsi) nez a/ a odlisuje datum/3 od napr. bodu_v_3D/3 - umoznuje jednoduchy pristup na slozky (vs. h/-k/) - argumenty jsou urceny polohou (a dohodou/konvenci), wrapery ad e/ jsou zbytecne - f/, g/: horsi pristup na slozky, moc obecne, nutny/vhodny interface g/ pouzitelne, pokud je mnozina atributu promenliva - funktor muze odlisovat ruzne reprezentace typu, napr. komplexni cisla polarni od pravouhlych -> procedury prijimaji kompl.c. obou druhu a samy si je rozlisi komplPolar(Z,Fi) komplPr(X,Y) */ % 3.cv % 2012 doplnit: % 2012: seznamy: sufix, prefix, pomoci append, sufixy, prefixy (vsechny), bioinf.otoceni % DC: concat % 2012: osetrovani chyb/typu, dva interfejsy % Priklady na tok dat: % append append([],L,L). append([X|L1],L2,[X|L3]) :- append(L1,L2,L3) % pozorovani append je napsano rekurzi podle prvniho a/nebo tretiho parametru % jak se chova append v mode: 1) (+,+,+) 2) (+,+,-) 3) (-,-,+), resp. (?,?,+) 4) (+,-,-) ad 3) nedeterministicky vraci vsechna rozdeleni, resp. podle pozadovanych podminek CV: napiste volani/kus kodu, ktery bude vracet rozdeleni s obema castmi neprazdnymi ad 4) OK, vlastne tvorba rozdiloveho seznamu ?- append([1,2],Xs,Ys), Rs=Ys-Xs. Xs = _1 , Ys = [1,2|_1] , Rs=[1,2|_1]-_1 % apl: delete/3: delete(X,Ls,Vs): vypusti jeden vyskyt X z Ls a zbyle prvky da do Vs delete(X,Ls,Vs):- append(As,[X|Bs],Ls), append(As,Bs,Vs). % pozn: ruzne volani append/3 jsou v ruznem modu % Q: funguje v modu (?,-,+) % A/Ne: pokud ne, je to odstranitelna chyba? % A/Ano: pokud ano, je deterministicky? % conc/2, % spojeni nekolika seznamu, mod (+,?) conc([],[]). conc([L|Ls],Vs):- append(L,Vs1,Vs), % mod (+,-,-) conc(Ls,Vs1). % Vs1 se dopocita a substituuje, % Vyhoda: tail rekurzivni % Q: muzu pouzit cons na deleni v modu (-,+) ? % A: NE. Generuje prazdne seznamy L % ?- conc(V,[1,2,3]). % V=[[],[],[], ... bum --- % ad kombinace: pokryti pripadu, if vs backtrack % permutace(+In,-Out): Out vydava backtrackingem, A: podle vstupu; B: podle vystupu % % permutace, strukturalni rekurze podle vstupu permutace_A([],[]). permutace_A([I|Is],Os):- permutace_A(Is,Os2), delete(I,Os,Os2). % puvodni/stejne delete, pridava na vsechna mozna mista % Q: jake je poradi vydavanych permutaci? % var B, z prednasky permutace([],[]). permutace(Is,[X|Os]):- delete(X,Is,Is2), permutace(Is2,Os). % tvorba vysledku: rekurze podle vystupu % vypusti jeden vyskyt prvku X z In, zbytek v Out (?X,+In,?Out), % ... anebo prida: (+X,-In,+Out) delete(X,[X|Xs],Xs). delete(X,[Y|Is],[Y|Os]):- delete(X,Is,Os). /* spravnost vzhledem k backtrackingu: pridani koncove podminky delete(X,[],[]). , ktera ma zajistit vzdy uspech, je nevhodne. Pro zamyslenou semantiku (!), ze (jedno) X chci vypustit, pokud se v seznamu nachazi, je tento fakt deklarativne nespravny, protoze plati vzdy, a nejenom, pokud se X v seznamu nevyskytovalo. Nasledne volani delete(2,[1,2,3],V) vrati V = [1,3] a V = [1,2,3], co neni zamyslene chovani. Spravne reseni (potrebuje rez anebo if-then-else,) vola delete jako podproceduru a fail osetruje v nadrazene proc. */ % kombinace /* priklad aplikace: chceme prozkoumat vsechny podgrafy dane velikosti. Pomoci kombinaci vybereme vrcholy a nasledne ziskame indukovany graf. Q: volba datovych struktur: 1) prvky, ze kterych vybirame, 2) kolik prvku vybirame A: 1) explicitne - seznam prvku 2) ruzne zpusoby: a) unarni notace s(s(0)), b) cislo 2, c) delka "vystupniho" seznamu [_,_] s anonymnimi promennzmi - nelze (primocare) pri vydavani vsech komb. v seznamu Q: lze vsechny zpusoby vstupnich dat pouzit pri backtrakingu i pri seznamu vysledku? A: ad c) hm idea: zafixujeme jedno konkretni poradi prvku podle dodaneho seznamu prvku */ % kombinace(+K,+N, -V), % volani napr. kombinace(s(s(0)),[1,2,3],V); vysledek V=[1,2] ... komb(0,_Ns,[]). komb(K,[N|Ns],[N|Vs]):- K=s(K1), % K1 is K-1, komb(K1,Ns,Vs). komb(K,[_|Ns], Vs):- K=s(_), % tj. K>0, bez testu mame opakovana reseni, pro ruzne delky Ns komb(K,Ns,Vs). % Q: jake je poradi kombinaci, jake je poradi prvku v kombinacich? % Q: co musim zmenit pro jine poradi? % (pozn. A) % s cisly komb1(0,_Ns,[]). komb1(K,[N|Ns],[N|Vs]):- K>0, K1 is K-1, komb1(K1,Ns,Vs). komb1(K,[_|Ns], Vs):- K>0, % bez testu mame opakovana reseni, pro ruzne delky Ns komb1(K,Ns,Vs). /* Q: jake je chovani pro K>N? (tj. "1 nad 2") Q: lze ho zlepsit? Q: Co musim zmenit pro kombinace s opakovanim A: Q: Co musim zmenit pro variace bez opakovani (s opakovanim) Q: pro variace: jake je poor-man solution (s vyuzitim uz znamych procedur z "knihoven") DC: 1. Co se zmeni, pokud chceme kombinace s opakovanim? 2. ... variace 3. ... variace s opakovanim */ % varianta: rekurze podle vystupu komb2(0,_Ns,[]). komb2(K,Ns,[N|Vs]):- K>0, K1 is K-1, append(_,[N|Ns1],Ns), komb2(K1,Ns1,Vs). % kdyz K < length(Ns), tak programy prohledavaji neuplne kombinace :-( % DC: a) odstranit, % b) a nepocitat opakovane delku: predavat si ji /* seznam vsech 'kombinaci bez opakovani': pametove narocne, kombAll(+N,+Prvky, -Vysledek), vysledek je seznam kombinaci, kazda ma delku N - zadani velikosti pomoci cisel (jsou i jine moznosti) porovnejte s backtrakingovou verzi Q: jak se ma program chovat kdyz reseni neexistuje? - srovnat: 1) vrati [], 2) zfailuje. Napr. ?-kombAll(2,[a],V). pozn: v Prologu nelze kombinace vydavat postupne jako "lazy stream". */ kombAll(0,_Ps,[[]]). % ve vysl. je prazdna kombinace, at mame k cemu pridavat prvky kombAll(N,[P|Ps],Kombs):- N>0, N1 is N-1, kombAll(N,Ps,Kombs1), % stejna delka komb, cil muze byt posledni (tail-rekurzivni) kombAll(N1,Ps,Kombs2), % kombinace o 1 kratsi pridejHlavy(P,Kombs2,Kombs2a), % "map" pridani prvku P append(Kombs2a,Kombs1,Kombs). % (pouze) zde se urcuje poradi komb. ve vysledku % lze prevest na tail-rekurzivni verzi, rozdilove seznamy nebo akumulator % volani: ?-kombAll(2,[a,b,c],V). % V=[[1,2],[1,3],[2,3]] % obe rekurze volame ve stejne klauzuli, protoze potrebujem oba mezivysledky pro konstrukci % celeho seznamu % neformalne: map: kazdy prvek ve vstupnim seznamu transformuji na jeden prvek ve vystupnim seznamu; transformace je predana jako parametr (naucime se pozdeji; i ve FP) % map zachova strukturu seznamu (, stromu, ...), ale vymeni/upravi prvky %---- /* pozn A: neocekavane chovani deklarativne spravneho programu a) zacykli se a2) vyda nektera reseni a zacykli se b) vydava reseni opakovane - casto lze opravit (napr. u kombinaci/3): klauzule pokryvaji _disjunktni_ pripady - lze pouzit if-then-else - souvisi: protoze Prolog backtrackuje (misto if-then-else), je vynechani podminky u "else" (posledni klauzule) casto chybou, ktera porusi deklarativitu (a spravnost) - napr: prunik, sjednoceni - chceme programy spravne (i) vzhledem k backtrackingu */ % kartezsky soucin z dvou seznamu prvku, vystup [d(X,Y)], (nebo X-Y) kart([],Ys,[]). kart([X|Xs],Ys,Vs):- makeDvojice(X,Ys,Vs1), % vyrobi vsechny dvojice d(X,_) append(Vs1,Vs2,Vs), % lze spojit pro lib. Vs2 kart(Xs,Ys,Vs2). % kartezsky soucin 3 mnozin kart3(X,Y,Z,V):- kart(Y,Z,V1), kart(X,V1,V). % Q: v jakem tvaru jsou vysledky? % kartezsky soucin N mnozin /* zmena reprezentace: vstup je seznam mnozin, vystup je mnozina seznamu (ne dvojic/trojic) ukonceni na dvou mnozinach (ala kart), jedne (listify) nebo zadne ([[]]). Posledni je nejjednodussi. pozn: v Hs by sme pouzili kart/_ a nasledne map/_ pro zmenu vystupni dat. strukt. */ kartN([],[[]]). kartN([Xs|Xss],Ks):- kartN(Xss,Ks1), kart2(Xs,Ks1,Ks). % kart2: namisto dvojic d(X,Y) vydava [X|Y] :-) % pouceni: ne vzdy je prvni navrh dobre pouzitelny dale %---- % kartezsky soucin, vystup jsou dvojice X-Y % kartDv(+Xs,+Ys,-Dvojice) kartDv([],_Ys,[]). kartDv([X|Xs],Ys,Dv) :- parovaniDv(X,Ys,Dv1), append(Dv1,Dv2,Dv), % zbyle dvojice Dv vlozime do vysledne struktury kartDv(Xs,Ys,Dv2). parovaniDv(X,[],[]). parovaniDv(X,[Y|Ys],[d(X,Y)|Vs]):- parovaniDv(X,Ys,Vs). % pokud chceme kartezsky soucin tri mnozin, muzeme pouzit kartDv/3, ale vysledky budou d(X,d(Y,Z)). kart3(Xs,Ys,Zs,Vs):- kartDv(Ys,Zs,Vs1), kartDv(Xs,Vs1,Vs). % lepsi/obecnejsi je pouziti seznamu - na vstupu i vystupu % ?- kartN([[1,2],[3],[4,5]], V) % na poradi vysledku nezalezi % V= [[1,3,4],[1,3,5],[2,3,4],[2,3,5]] % Prevod BVS na seznam, inorder % prevodBVS2List(BVStrom,SeznamInorder), vystupni seznam je usporadany prevodBVS2List(nil,[]). prevodBVS2List(t(L,X,R),V) :- prevodBVS2List(L,VL), % rekurze 2x prevodBVS2List(R,VR), append(VL,[X|VR],V). % (A), spracovani mezivysledku % (A) varianta: ..., concat([VL,[X],VR],V). % spojeni tri seznamu, z X je jednoprvkovy [X] % poradi ve vysledku je urceno poradim spojeni v (A), ne poradim volani rekurzi % zpusob spojeni v (A) lze predat "funkcionalnim" parametrem, napr. pro % nestandardni poradi "Xbegin VL VR Xend" ala XML % Lze pouzit Akumulator/Stav, ale data by musela tect sloziteji a pevnym zpusobem % pri minimu, maximu ze stromu (BVS) nepotrebuju 2 rekurzivni volani, pouze 1 % -> prochazeni strukturou neni vzdy celou strukturou % DC1: kartezsky soucin: KartN % ------------------ % 4.cv % ad vsechny reseni: % na poradi (obvykle) nezalezi, ale chceme vedet, jake bude /* transpozice matice: transp(+MI, -MO) moznosti: A: rekurzi podle vstupu, tj. podle poctu sloupcu vstupu B: rekurzi podle vystupu, tj. delky vstupniho _radku_ ! B je jednodussi */ % varianta B transp([[]|_],[]). % dosly prvky v radku transp(MI, [R| MTransp]):- rozdelMat(MI, R, M2), transp(M2,MTransp). % oddeli z MI 1. sloupec R a zbytek matice M2 % rozdelMat(+MI, -R, -M2) - lze rozdelit na 2x map rozdelMat([],[],[]). % oba vystupy skladanim substituci rozdelMat([[P|R]|M],[P|R2],[R|M2]):- rozdelMat(M,R2,M2). % varianta A /* - je neprirozené koncit na prazdne matici, protoze pak nevygenerujeme jednoduse spravny pocet sloupcu ve vysledku; - koncime na jednoradkove matici: [1,2,3] ~~> [[1],[2],[3]] */ transp2([R],MTransp):- % koncime na jednoradkove matici listify(R,MTransp). % seznam jednoprvkovych sloupcu, v prednasce transp2([R|M],MTransp):- transp2(M,MTransp2), % nejdriv rekurze pridejSl(R,MTransp2,MTransp). % synchronni "map" se dvema vstupy: (+,+,-) pridejSl([],[],[]). pridejSl([P|Ps],[R|Rs],[[P|R]|M2]):- pridejSl(Ps,Rs,M2). listify([],[]). listify([P|Ps],[[P]|Vs]);- listify(Ps,Vs). %-------------- % maticove operace, maticove vyrazy % +/2, */2, -/2, transp/1, inv/1, m/1 - prime zadani matice % kratK(Konst,+Mat), plusK(Konst,+Mat), - bodove operace % jednotkovaMat(RozmerM,RozmerN), nulovaMat(dtto), % mf(Filename) - nacteni matice ze souboru ... % ... a dalsi: oramovani, slozeni za sebe, pod sebe, lin.komb dvou a vic ... % priklad vyrazu: m([[1,2],[3,4]])+ inv(transp(jednotkovaMAt(2,2)) % soucet matic (+Mss1,+Mss2,-Mss0) - synchronni prochazeni po bodech soucetMat([], [], [] ). soucetMat([R1|Rs1],[R2|Rs2],[R0|Rs0]):- soucetVec(R1,R2,R0), % soucet vektoru soucetMat(Rs1,Rs2,Rs0). soucetVec([], [], [] ). soucetVec([P1|Ps1],[P2|Ps2],[P0|Ps0]):- P0 is P1 + P2, % analogicky i jine bodove operace soucetVec(Ps1,Ps2,Ps0). % analogicky kratKMat(Konst,MI,MO), plusKMat(K,MI,MO), linKomb2Mat(K1,K2,M1,M2,M0) % vnitrni operace bude P0 is Konst * P1; P0 is Konst+P1; P0 is K1*P1+K2*P2 ... % soucin matic (+M1, +M2, -M0) - ma jinou (nebodovou) strukturu % ! je vhodnejsi si druhou matici transponovat, aby sme z ni mohli prirozene (tj. podle struktury) % vybirat puvodni sloupce, po transpozici radky soucinMat(M1,M2,M0):- transp(M2,M2T), soucinMat2(M1,M2T,M0). soucinMat2([], _M2, []). soucinMat2([R1|Rs1],M2,[R0|Rs0]):- soucinVecMat(R1,M2,R0), % soucin pevneho vektoru a cele matice soucinMat2(Rs1,M2,Rs0). soucinVecMat(_R1,[],[]). soucinVecMat(R1,[R2|Rs2],[V|Vs]):- sks(R1,R2,V), % skalarni soucin soucinVecMat(R1,Rs2,Vs). % skalarni soucin vektoru (+,+,-) % - lze i akumulatorem, viz nize sks([],[],0). sks([X|Xs],[Y|Ys],V):- sks(Xs,Ys,V1), % poradi nutne: nejdriv rekurze V is X*Y+V1. % pak pouziti v aritmetice % sks/3 akumulatorem a tail-rekurzivne (optimalizace) % ! obecne: pocita s jinou asociativitou (asoc. doleva) nez % primo rekurzivni verze (aso. doprava) -> nesmi to vadit sksAcc(Xs,Ys, V):- sksA_(Xs,Ys,),V). % init Acc sksA_([],[],V,V). % predani Acc, seznamy konci synchronne sksA_([X|Xs],[Y|Ys],A1,V):- A2 is X*Y+A1, % uprava Acc sksA_(Xs,Ys,A2,V). % rekurze % vyhodnocovani maticoveho vyrazu evalM(m(Mat),Mat):- skontrolujMat(Mat). evalM(jednotkovaMat(M,N), Mat):- generujEMat(M,N,Mat). evalM(M1+M2,M):- evalM(M1,V1), evalM(M2,V2), soucetMat(V1,V2,M). evalM(M1*M2,M):- evalM(M1,V1), evalM(M2,V2), soucinMat(V1,V2,M). evalM(linKomb2Mat(K1,K2,M1,M2), Mat):- % prevedeni na jine operace evalM(kratKMat(K1,M1)+kratKMat(K2,M2),Mat). % ... % priklad volani je videt na poslednim radku % jine vyhodnocovani: kontrola rozmeru evalR(m(Mat), M-N) :- spoctiRozmery(Mat,M,N). evalR(jednotkovaMat(M,N),M-N). evalR(transp(Mat),N-M):- evalR(Mat,M-N). evalR(Mat1+Mat2,M-N):- evalR(Mat1, M-N), evalR(Mat2,M2-N2), (M=M2, N=N2 ; error("chyba rozmeru matice v souctu")) % nedokonale % ... % DC: Co a jak predavat, aby sme vedeli, kde je chyba? % var.: A: shora (rozsirujici se aktualni kontext), B: zdola (upresnovat podvyraz s chybou) % idea: chcem popis cesty do podvyrazu/podstromu - v 1. podvyrazu, v nem v 2. podvyrazu .. je chyba % (DC): relacni kalkul: a) navrh operaci a jejich reprezentace; b) vykonne procedury a interpret % opacna relace, reflexivni relace, ... %--------- /* heapsort stavba vyvazeneho stromu a jeho zhaldovateni (pri zachovani tvaru) bylo na prednasce varianty vytvoreni usporadaneho seznamu z haldy: - A: ala mergesort - B: odebrani korene a propagace "chyby" dolu pozn: i kdyz neodebiram z haldy pravidelne, na asympt. casovou slozitost to nema vliv */ % Q: je vhodne predavat dve podhaldy samostatne anebo vyrobit jednu haldu s dirou (nekonecnem): t(L,maxInt,R)? % A: lepe samostatne , protoze 1) stejne haldu hned rozeberu a 2) nemusim vymyslet a osetrovat "maxInt" heapsort(Xs,Srt):- vyvazBS(Xs,Vyvaz), heapify(Vyvaz, Heap), heap2list(Heap, Srt). % var. A: ala mergesort :-( heap2list_A(void,[]). heap2list_A(t(L,X,R),[X|Vs]):- heap2list(L,VLs), heap2list(R,VRs), merge(VLs,VRs,Vs). % var B: propagace "diry" dolu heap2list(void,[]). heap2list(t(L,X,R),[X|Vs]):- spojHeap(L,R,H), % podhaldy predavam samostatne heap2list(H,Vs). % nepouzivame "if-then-else" spojHeap(void,R, R). spojHeap(L, void,L) :- L\=void. % bez opak. pro cil spojHeap(void,void,X). spojHeap(t(L1,X1,R1),R,t(H,X1,R)) :- R = t(_L2,X2,_R2), % pokrocily zpusob, aby se R nemuselo znovu skladat X1<=X2, % x1 je mensi -> do korene spojHeap(L1,R1,H). spojHeap(t(L1,X1,R1), t(L2,X2,R2), t(t(L1,X1,R1),X2,H)) :- % podstrom je pripraven % mene efektivni zpusob, L se snovu sklada X1 > X2, spojHeap(L2,R2,H). % X2 jsme odebrali navrch a "dira" se posunula dolu ("nad" L2 a R2) %Varianta: stavba haldy s prehazovanim: pridavame vzdy doleva, ale "potom" prohodime % insertHeap(+novyPrvek, +staraHalda, -novaHalda) % vyhoda : buduje vyvazenou haldu insertHeap(X, void, t(void,X,void)). insertHeap(X, t(L,Y,R), t(R0,X0,L0)):- % vzdy prohozeni L a R X X0=X, insertHead(Y,L,L0) % mensi X v koreni, Y vnoruju ; X0=Y, insertHead(X,L,L0). % X vnoruju % l2h(+L,-H) : ze seznamu L vybuduje _vyvazenou_ haldu H % DC: prevest na tail rekurzivni verzi (tj. akumulator) l2h([], void). l2h(X|Xs], H0):- l2h(Xs,H1), insertHeap(X,H1,H0). % pozn: zatridovani prvku do haldy pri zhaldovateni uz vytvorene struktury: % - prvek chceme vymenit s mensim z obou synu. To ma log. slozitost. % - pokud prvek zatridime doleva a pak jeste doprava, program je spravny, ale je linearni % (... a nemuseli jsme pouzivat haldy) % 5.cv. ------------- /*cvic 5. r.2012 Aritmetika: Skalarni soucin sks/3, (faktorial/2), fibonacciho p., jine posl. Kartezsky soucin, varianty dat.str., kart.s. pro n seznamu + listify/2 Vyhledavani: lookup/3, v seznamu, ve strome, slozeny klic DC: vybrani podle podminky v n-arnim strome --- Predp: aritmetika U: Skalarni soucin Var: rekurzi i akumulatorem Q: Jak se chovat, kdyz jsou seznamy ruzne dlouhe? U1: faktorial. Nejjednoduseji rekurzi U2: fibonacciho cisla. Idea: rekurzi, ale ve vykonne rekurzi si pamatuju 2 posledni cleny Q: proc je v rekurzi podminka N>0 ? ... Q: proc oddelujeme vykonnou cast? Q: Jak upravit program aby mel jen jednu koncovou podminku ?Q: Proc upravujeme program, aby mel jen jedny koncovou podminku (U3:) Obecny zpusob vypoctu rad, s pevnym poctem clenu U4: Jakou reprezentaci zvolit pro vypocet rady T_n = sum_i (T_i * T_(n-i)), 1=2, % kvuli deklarativite N1 is N-1, % priprava rekurze fib2(N1,F1,F2), % rekurze, s pameti % nespravne: fib(N-1,F1,F2) F is F1+F2. fib(N,F) :- fib2(N,F,_). % interface DC: prepsat do TRO tvaru - pokud dalsi clen rady zavisi na minulych k clenech, pamatuju si k poslednich clenu (lepe samostatne, pripadne v k-tici) pokud dalsi clen rady zavisi na vsech minulych clenech, pamatuju si vsechny v seznamu Pouzitelne obecne i pro rady z minuleho prikladu, ale nepotrebne cleny zbytecne zabiraji pamet DC: upravte pro fibonacciho cisla radaT(1,[1]). radaT(N,[TN|Ts]) :- % TN dopredu N>1, N1 is N-1, radaT( N1,Ts), spoctiT(N,Ts,TN). % spoctiT: idealne predavat funkcionalnim parametrem spoctiT(N, Ts, TN) :- % T_n = n + sum T_i * T_(n-i) reverse(Ts,TRev), sks(Ts,TRev,Sks), % pouzivane ekvivalentni vyjadreni sumy pomoci skalarniho soucinu, TN is N + Sks. % slo by vytahovat T_i, ale to je pomale %--- % prunikMn(+In1,+In2,-Out) : ze dvou (korektnich) mnozin vyrobi prunik % 3 moznosti: byly na prednaskach % 1) test 2x, s not/1; 2) pouziti rezu; 3) pouziti if-then-else % zde: 3) prunikMn([],_Ys,[]). prunikMn([X|Xs],Ys,V):- (member(X,Ys) -> V=[X|V1] ; V=V1 ), prunikMn(Xs,Ys,V1). % druhou mnozinu Ys nechci menit (vyroba d.s. je drazsi nez cteni) % (klasicke) reseni pomoci dvou klauzuli bez rezu a druhe podminky je *nespravne* % pri backtrackingu: prvni vydane reseni je spravne, potom vydava jeho podmnoziny :-( prunikMn1([],_Ys,[]). prunikMn1([X|Xs],Ys,[X|V1]) :- member(X,Ys), % zde patri rez '!' prunikMn1(Xs,Ys,V1). prunikMn1([X|Xs],Ys,V):- % klauzule neni deklarativni % nebo zde patri podminka \+(member(X,Ys)) prunikMn1(Xs,Ys,V). % chovani: % ?- prunikMn([1,2,3],[2,3,4], V). % V=[2,3]; % V=[2]; % V=[3]; % V=[]; % no % Jine: sjednoceniMn, rozdilMn, symetricky rozdil jako srozdil/3, test rovnosti eqMn/2 % ad srozdil: srozdil(In1,In2, V):- rozdilMn(In1,In2,V1), rozdilMn(In2,In1,V2), sjednoceni(V1,V2,V). % varianta: vyuzijeme interpret mnozin srozdil(In1,In2,V) :- isset(V, (In1-In2)+(In2-In1)). % ad eqset: mnoziny nemaji standardni reprezentaci, musim porovnavat po prvcich (nebo jinak) eqset(In1,In2):- srozdil(In1,In2,V), V=[]. % Varianty % 1) usporadane mnoziny -> operace maji slozitost O(n), misto O(n^2) % 2) bag alias multimnoziny (alias histogramy) --- interprety, DSL: Domain Specific Language, EDSL: Embedded DSL DSL: specialni podjazyky, casto pro specifickeho uzivatele, (caste ve FP) - syntakticka analyza vyrazu zdarma, - uzivatelsky citatelne vyrazy, vetsinou - pouzitelne techniky ze semantiky programovacich jazyku - stejny zapis se da interpretovat ruzne: misto mnoziny chci jen mohutnost, nebo chci pocitat s multimnozinami (jiny interpret: isbag/2) (mozny) priklad DSL drive: aritmetika pro unarni repr. cisel priklad DSL dale: regularni vyrazy, derivace RV Dalsi: vyhodnocovani bool. fce, maticova vyrazy, vektorove vyrazy priklad zde: mnozinove vyrazy (s nevnorenymi prvky): isset/2 % pozn: eqMn/2 nepouzivame v isset/2, protoze nevraci mnozinu % interface: mod isset(-Set,+SetExpr) % klasicke operace; isset(V,M1+M2) :- % sjednoceni isset(V1,M1), % vyhodnoceni podvyrazu isset(V2,M2), sjednoceniMn(V1,V2,V). % vlastni semanticka operace isset(V,M1*M2) :- % prunik isset(V1,M1), isset(V2,M2), prunikMn(V1,V2,V). isset(V,M1-M2) :- % rozdil isset(V1,M1), isset(V2,M2), rozdilMn(V1,V2,V). isset(V, --(M1,M2)) :- % sym. rozdil isset(V1,M1), isset(V2,M2), isset(V, (V1-V2) + (V2-V1)). % prevedeni na jine operace (syntakticky cukr/pozlatko) % pozn.: nechceme M1 a M2 vyhodnocovat dvakrat % zadani mnoziny explicitne isset(V,L) :- % seznam isList(L), list2Mn(L,V). % odstraneni duplicit, pripadne usporadani, ... proste zajisteni korektnosti % rozsirujeme DSL: between, aritmeticke posl. ... isset(V,between(Min,Max)) :- % intervaly cisel between(Min,Max,V). % vestavene; vime co generuje, nekontrolujeme isset(V,arit(Lo,Hi,Step)) :- % aritmeticke intervaly od Lo do Hi (vcetne) s krokem Step myArith(Lo,Hi,Step,V). % ... % mozne rozsireni: cyklicke intervaly ... % podpora pro tvorbu dvojic ... % a cokoli: code, s nejakym dohodnutym interface pro parametry isset(V, code(Pred, Params,V)):- % embedded volani Prologu, vypocet cehokoli call(Pred,Params,V1), % vlastni volani, vyuziva rozsireneho call/N % predikaty s dohodnutym interface, ktere pouzivam, musim naprogramovat list2Mn(V1,V). % aspon zakladni kontrola % volani: slozena cisla do 1000: % ?-isset(V,between(2,1000)-code(prvocisla,[max=1000,verbose=no],Out)). % ?-isset(V,[1,2]*[2,3]+[4,5]-[3,4]). % priklad % "syntakticka" chyba v DSL % catch-all pravidlo, pokud nebacktrackuju % vypis: 'chyba', kde, jaka, parametry ... isset(V,Expr) :- % (Expr\= _+_ ;Expr\= _-_; Expr\= _*_; Expr\= --(_,_); Expr\= between(_,_); % Expr\= arit(_,_,_); Expr\=code(_,_,_) ) % pokud nejsou v progr. rezy write(['Error in isset/2: neznama operace', Expr]),nl, V=[]. % vystup, napriklad --- ?U: pruchod matice ~ transpozicni sifra (varianty) ?U: navrhnout interpret pro sestavovani a dekodovani transpozicni sifry priste: (6.cv) evalVF - meli predn. vyhodnocovani spojky ekvivalence, linearne jine vyhodnocovani: fuzzy, (N/A) vf2nnf - prevod, i postupny vf2cnf dnf2cnf - de fakto roznasobeni ala kart. soucin interpret VF, a jine interprety: Matice, .... DC: transpozicne sifry (kryptografia) - vztah interepretov k DSL Predp: if-then-else U: sjednoceni, prunik Q: porovnejte usporadanou a neusporadanou verzi ?U: histogram, tj. multimnoziny ... ?U streamove spracovanie s kapitanskym krokom grafy ... barveni :-) implicitni reprezentace reprezentace Stavoveho prostoru derivace RV - kod ad: na dalsi tyzden som zadal pisomne DC, ak to stihnete: ! potrebuje not nebo rez nebo if-then-else (zjednodusene:) je dany n-arni strom struktury: t(hodnota, [klic1-postrom1, klic2-podstrom2, ...]) a podminka podm/1 , ktera se pro podstrom splni anebo nesplni. Strom konci (tj. je list), kdyz je seznam podstromu prazdny :-) Mate vydat v _seznamu_ vsechny "prostredni" stromy, ktere splnuji podminku podm/1. Prostredni v tomto kontextu znamena, je nad nimi (ne nutne bezprostredne) je strom , ktery ji splnuje a pod nimi je (pod)strom , ktery je splnuje. Navod: protoze strom ma dve urovne struktury (stromy a seznamy (pod)stromu), tak prirozene reseni bude mit dve vzajemne rekurzivni procedury Varianty: a) prostredni b) pouze horni c) pouze dolni d) vsechny e) vsechny, ale s oznacenim 'horni', 'dolni', 'prostredni' - f) ... zadane s cestou podm/2 : podm(Cesta,Strom) ... podm/1 se mysli doslova, tj.: pruchodNT(Strom, OutStromy):- ...., podm(Podstrom1),.... Ooops: tak si uvedomuju, ze asi budete potrebovat i negaci podminky: not(podm(Strom)) - to jeste nebylo na prednasce ---- */ /* (2010:) logicke formule: 2014/7: na prednasce bylo: tvar formule; vyhodnoceni formule; splnitelnost formule (ohodnoceni je volna promenna) P: nahrada/substituce za promenne: zatim pouze true/false nahradaFVP(+Ohod,+FIn,-FOut) tvar ohodnoceni: [jmenoProm - hodnota(true | false)] napr. [a-true,b-false,c-true] pozn. p/1 potrebuju pro odliseni promennych ve formulich, v ohodnoceni vim, ze dosazuju jen za promenne, tj. staci jmeno (napr. a), bez p/1 (ne p(a) ) */ % operatory, definice ... nahradaFVP(_O,true,true). nahradaFVP(_O,false,false). nahradaFVP(O,p(X),V):- member(X-V,O). %find (1) nahradaFVP(O, and(X,Y), and(VX,VY)):- % povolena spojka and/2 nahradaFVP(O,X,VX), nahradaFVP(O,Y,VY). nahradaFVP(O, or(X,Y), or(VX,VY)):- nahradaFVP(O,X,VX), nahradaFVP(O,Y,VY). nahradaFVP(O, imp(X,Y), imp(VX,VY)):- nahradaFVP(O,X,VX), nahradaFVP(O,Y,VY). nahradaFVP(O, ekv(X,Y), ekv(VX,VY)):- nahradaFVP(O,X,VX), nahradaFVP(O,Y,VY). nahradaFVP(O, non(X), non(VX)):- nahradaFVP(O,X,VX). /* - (1) pokud je promennych mnoho a chceme je ukladat a vyhledavat v binarnim strome, tak zmenime reprezentaci a vyhledavaci proceduru; proste si musi odpovidat. - s operatory muzeme psat: nahradaFVP(O, X and Y, VX and VY):- ... - ! zavorky (v operatorove syntaxi) se v strukturalni rekurzi neosetruji: Klauzule typu: nahradaFVP(O, (X) ,VX):- nahradaFVP(O, X, VX). -> zpusobi zacykleni, protoze (X) a X jsou stejne termy (interne) varianty 1) upravte program tak, aby ohodnoceni mohlo byt castecne. Promenne, ktere nejsou v ohodnoceni, se nechaji ve formuli bez zmeny. 2) upravte program tak, aby mohl vyrokove promenne nahrazovat jinymi formulemi ( :-) ) - zkracovani zdrojaku, idea pouzitelna i dale/jinde : A1) nahradaFVP(_O,F,F) :- F=true; F=false ; F=p(_) . A2) nahradaFVP(_O,F,F) :- member(F,[false,true,p(_)]). B1) nahradaFVP(O,F,V) :- ( F= F1 and F2, V = V1 and V2 % zpracovani bin. spojek ma stejnou strukturu ; F= F1 or F2, V = V1 or V2 % lisi se jmeno spojky na vstupu a ji odpovidajici vystup ; F= F1 imp F2, V = V1 imp V2 ; F= F1 ekv F2, V = V1 ekv V2 ), nahradaFVP(O,F1,V1), nahradaFVP(O,F2,V2). % ...a rekurze - protoze spojky (zde a ruzne funkcni symboly obecne) maji ruznou semantiku, je spis vyjimkou, ze se zpracovavaji stejne B2) pomoci =.. nahradaFVP(O,F,V) :- F=..[FS,F1,F2], % rozbor vstupu O=..[FS,V1,V2], % vyroba vystupu, FS je uz znamy nahradaFVP(O,F1,V1), nahradaFVP(O,F2,V2). % ...a rekurze - zde jsou osetreny binarni spojky; pokud zavedu proceduru pro osetreni seznamu argumentu, ... F=..[FS|Args], O=..[FS|Outs], ...map(Args,Outs)... muzu v jedne klauzuli zpracovat spojky vsech cetnosti, vlastne i konstanty -> zkracovani kodu - pokud je znamy vycet funkcnich symbolu (~tagu u variantnich zaznamu), tak se tento zpusob obvykle nepouziva. Naopak, musi se pouzit, pokud nezname vycet povolenych f.s., tj. kdyz zpracovavame _obecne_ programy nebo termy (napr. v unifikacnim algoritmu) (~zpracuje schema, nejen vycet) */ /* dodatek: priklad na tok (stavovych) dat: velikost formule tail-rekurzivne s akumulatorem U: pocet spojek ve formuli: sizeFVP(+Formule,-Size) interface: sizeFVP1(+Formule,+SizeIn,-SizeOut) */ sizeFVP(F,S):- sizeFVP1(F,0,S). % interface sizeFVP1(F,N,N) :- member(F,[true,false,p(_)]. % koncove trivialni pripady sizeFVP1(non(F1),S1,S0):- S2 is S1+1, sizeFVP1(F1,S2,S0). % tail-rekurzivni sizeFVP1(and(F1,F2),S1,S0):- S2 is S1+1, sizeFVP1(F1,S2,S3), sizeFVP1(F2,S3,S0). sizeFVP1(or(F1,F2),S1,S0):- S2 is S1+1, sizeFVP1(F1,S2,S3), sizeFVP1(F2,S3,S0). sizeFVP1(imp(F1,F2),S1,S0):- S2 is S1+1, sizeFVP1(F1,S2,S3), sizeFVP1(F2,S3,S0). sizeFVP1(ekv(F1,F2),S1,S0):- S2 is S1+1, sizeFVP1(F1,S2,S3), sizeFVP1(F2,S3,S0). /* varianta pro 4 _binarni_ spojky: !neni obvykle, ze se spojky zpracovavaji stejne <- ruzne spojky maji ruznou semantiku sizeFVP1(F,S1,S0):- (F=and(_,_); F=or(_,_); F=imp(_,_); F=ekv(_,_) ), % test spojek F1=arg(F,1,F1), F2=arg(F,2,F1), % vyber args S2 is S1+1, sizeFVP1(F1,S2,S3), sizeFVP1(F2,S3,S0). */ /* prevod na negovanou normalni formu, CNF, DNF var. (A): vse v jednom pruchodu termem, ! pod negaci menim prevadeni mezi DNF a CNF B: postupne: LF -> LFR -> NNF -> CNF termy: jako na prednasce: true/0, false/0, konstanty p/1 p(x) domenove promenne and/2, or/2, non/1, imp/2, ekv/2 (xor, nand, nor) vyhoda p(x): promenne maji samostatny namespace (...) */ % lf2lfr(+LF,-LFR) prevod na Log. Formulu Redukovanu (pouze and, or, non) lf2lfr(true,true). % konstanty a promenne bez zmeny lf2lfr(false,false). lf2lfr(p(X), p(X)). lf2lfr(and(X,Y), and(VX,VY)) :- % povolena spojka and/2 lf2lfr(X,VX), lf2lfr(Y,VY). % rekurzivna uprava lf2lfr(or(X,Y), or(VX,VY)) :- % povolena spojka or/2 lf2lfr(X,VX), lf2lfr(Y,VY). % dtto lf2lfr(non(X), non(VX)) :- % povolena spojka non/1 lf2lfr(X,VX). % len 1 argument lf2lfr(imp(X,Y), V) :- % lina varianta pro imp/2: 1 krok a ... lf2lfr(or(non(X),Y),V). % ... rekurze potom % lf2lfr(imp(X,Y),or(non(VX),VY)) :- % obvykla rekurzivni varianta % lf2lfr(X,VX), lf2lfr(Y,VY). % lf2lfr(ekv(X,Y), V) :- % lina varianta pro ekv/2 % lf2lfr(and(imp(X,Y),imp(Y,X)),V). % nevhodne: X a Y sa spracuji 2x nezavisle lf2lfr(ekv(X,Y), or(and(VX,VY),and(non(VX),non(VY))) ) :- % lina varianta pro ekv/2 lf2lfr(X,VX), lf2lfr(Y,VY). % X a Y sa spracuji 1x, ve vysledku sdili strukturu (pamet) % ale: i kdyz argumenty sdili strukturu, dalsi zpracovani termu to nevyuzije %pozn: % /* prevod na NNF. Predpokladame uz redukovanou formuli, jinak bychom museli este osetrit zbyle spojky - spojky uvnitr non/1 musime osetrit samostatne */ % lfr2nnf(+LFR, -NNF) % prevod log. fle redukovane na Negovanou Norm. formu lfr2nnf(X,X):- X=true; X=false; X=p(_). % koncove podminky, najednou lfr2nnf(and(X,Y),and(VX,VY)) :- % nektere spojky (and, or) bez zmeny lfr2nnf(X,VX), lfr2nnf(Y,VY). lfr2nnf(or(X,Y),or(VX,VY)) :- lfr2nnf(X,VX), lfr2nnf(Y,VY). % ekv/2, imp/2 uz nemusime osetrovat v redukovane formuli, pouze pri (A) lfr2nnf(non(X),non(X)) :- X=true; X=false; X=p(_). lfr2nnf(non(non(X)),VX) :- % X upravujeme, negaci odstranime lfr2nnf(X,VX). lfr2nnf(non(and(X,Y)),or(VX,VY)) :- % de Morganovo pravidlo lfr2nnf(non(X),VX), lfr2nnf(non(Y),VY). % negaci posilame dale do hloubky % lfr2nnf(non(and(X,Y)),V) :- % de Morganovo pravidlo % lfr2nnf(or(non(X),non(Y)),V). % lina varianta, 1 krok lfr2nnf(non(and(X,Y)),or(VX,VY)) :- lfr2nnf(non(X),VX), lfr2nnf(non(Y),VY). % vynechano: nemozny vstup non(ekv(...)) ... /* prevod NNF na CNF */ % nnf2cnf(+NNF,-CNF) % Q: je mozne/vhodne osetrit jen prvni argument na distributivitu a pak argumenty prohodit? % A: hrozi (tj. nachylne k) zacykleni % prevod formule na CNF: vse v jednom, jen pouziti predchazejicich lf2cnf(LF,CNF):- lf2lfr(LF,LFR), lfr2nnf(LFR, NNF), nnf2cnf(NNF,CNF). % prevod reprezentaci v obecnem strome (bude i dal a obecneji) a zpatky /* l.formula na tvar t(FunkcniSymbol,[podstromy]) napr: and(non(p(x)),p(y)) ~~> t(and,[t(non,[t(p(x),[])]),t(p(y),[])]) u promennych je moznost volby reprezentace. pouziti: jednou prevedu a pritom osetrim jednotlive spojky samostatne, na vysledne stromove reprezentaci potom muzu vykonne casti spojovat */ lf2strom(Konst,t(Konst,[])) :- Konst=true; Konst=false. lf2strom(Prom, t(Prom,[])) :- Prom = p(_). % nema podformule % lf2strom(p(X), t(p,[t(x,[])])). % jina moznost lf2strom(and(X,Y),t(and,[VX,VY])) :- lf2strom(X,VX), lf2strom(Y,VY). lf2strom(or(X,Y) ,t(or ,[VX,VY])) :- lf2strom(X,VX), lf2strom(Y,VY). lf2strom(non(X), t(non,[VX])) :- lf2strom(X,VX). lf2strom(imp(X,Y),t(imp,[VX,VY])) :- lf2strom(X,VX), lf2strom(Y,VY). lf2strom(ekv(X,Y),t(ekv,[VX,VY])) :- lf2strom(X,VX), lf2strom(Y,VY). % vyhledani podstromu podle cesty % struktura stromu: seznam trojic f(klic, hodnota, podstromy), z prednasky % podstromy pocitam od 1, cislo 0 na konci znamena vybrani hodnoty. % spojeni dvou stromu, seznamy jsou utridene podle klicu % struktura: seznam trojic f(klic, hodnota, podstromy) % ----- ad binarni stromy: oddelit klic od hodnoty, porovnava se jen Klic t(Levy, Klic-Hodn, Pravy) - v Hodn muze byt informace pro AVL, R-B stromy ... 6.cv. Zeleny a cerveny rez. ntree: nt(Hodnota,[klic-podstrom]) priklad: vyber podle dane cesty, klice se muzou opakovat hodnoty vybereme nasledne anebo cestu ukoncime 0, ktera znamena vyber hodnoty misto podstromu ad: vlastne hledani podle slozeneho klice (ala Aho-Corasickova) selectNT(Cesta, InStrom, Podstromy) :- vybere podstromy na spravne ceste selectNT([], S, [S]). % vracime seznam selectNT([K|Ks], nt(_H,Ss), Vs) :- selectNTL(K,Ks,Ss,Vss), concat(Vss,Vs). % neprima rekurze % selectNTL je vlastne (idiom) filter podle klice. selectNTL(K,_ ,[],[]). selectNTL(K,Ks,[K1-S|Ss],Vs) :- ( K=K1 -> selectNT(Ks,S,V1), Vs=[V1|Vs1] % var: slo by hned spojit ; Vs = Vs1 % explicitni "prirazeni" vysledku ), selectNTL(K,Ks,Ss,Vs1). % Vs1 se pouzije v obou vetvich DC: v ceste muze byt minus misto jednoho lib. klice, pripadne hvezdicka misto posloupnosti klicu U: Sjednoceni Feature Struktur, FS jsou reprezentovany NStromy. Pro stejne klice chceme spojit podstromy, rekurzivne. Idea: sjednoceni/merge Var: a) rozdil FS, b) prunik FS - N-arni stromy maji ruzne varianty, napr. vrcholove a hranove ohodnocene, s opakovanim klicu, s vice hodnotami ... ; vhodna varianta sa lisi podle pouziti priste: - generuj a testuj: jednoduche, ale 1) ne vzdy vestavene prologovske prohledavani vyhovuje (spis malokdy) 2) efektivni, pokud je generovana mnozina o malo vetsi nez vysledna 3) nekdy potrebujeme vsechna reseni v seznamu -> generuj a filtruj v lazy jazyku generujeme postupne ... (rozhodovaci NP-uplne ulohy se lehce napisi :-( ) dalsi: vybirani prvku z matice podle nejakeho vzoru - po spirale - po diagonalach = obecne: podle dvojindexu Scheme: unique, histogram, <- bloky stejnych klucov ! operace, ktere nezahodi explicitni data, tj. vrati vsechny; az potom selektor DC histogram 7.cv generuj a testuj: Obecne CSP, priklady, damy na sachovnici, rozhodovaci (vs. optimalizacni) problemy damy: moznost nekolika reprezentaci (s ruznymi implicitnimi podminkami) generuj a testuj (hruba sila), vyhody, nevyhody, jedno reseni vs. vsechna reseni prohledavani vs. heuristiky pouziti findall, pametova narocnost vs. Lazy(Hs), casova narocnost, certifikaty NPU, apl: kryptografie varianty: generuj po castech a hned testuj, CP/CSP: testuj a generuj vsechna reseni explicitne: generuj a filtruj (jiny pristup): izomorfizmus grafu: naivne vs. deleni na tridy osli mustek : generovani castecnych reseni ~> prohledavani stavu" jako prohl. grafu! Stavy: farmarVlkKozaZeli, rubikova kostka, barveni grafu Rubikova kostka, reprezentace: syntakticka(=povrchova), semanticka: kosticky+orientace syntakticka: sdruzovat steny tah/3 s pomenovanim, odvozene tahy, tahy/3 jako interpret interprety/DSL: priklady ; read zdarma+operatory ; reprezentace promennych pocitani s multimnozinami (bags): isBag, unionBag/2, ..., unarni fce/normalizace na soucet 1 koncove podminky, zobecneni na pravdepodobnosti reprezentace: usporadana vs. neusporadana, vhodnost normalizace (pri makeBag) - bez opak. a cetn. 0 --- CSP: promenne xi nabyvaji hodnot z domen Di pr: damy, sudoku, barveni grafu, SAT, ... damy8: (64x):0-1 ; (8x)64 ; (8x)8 ; perm(8) v repreprezentaci je cast podminek uz splnena damy(N,Ds):- % pro posledni moznost repr. ints(N,Ns), % Ns=[1,2,3,..8 (=N) ] perm(Ns,Ds), testDamy(Ns,Ds). % vlastne radky a sloupce samostatne, ale synchronizovane ... findall(Ds, (perm(Ns,Ds), testDamy(Ns,Ds)), Reseni). % pamet=O(reseni), ne O(moznosti) - generuj a filtruj: explicitni generovani vsech permutaci a pak filtrovani: -> spotrebuje velkou pamet najednou, (v Hs s linym generovanim staci pamet alokovat postupne) --- rubik ... reprezentace syntakticka/pozicni, podle sten (Predni,Leva,Zadni,pRava,Horni,Dolni), v nejakem usporadani a konkretni barvy (Z_elena,C_ervena,B_ila,Y_ellow,M_odra,O_range): kostkou nehybeme -> v repr. bez prostrednich kosticek struktura: vyuziva shlukovani do sten (po 8) rk(s(b,b,b,z,c,y,y,y), % predni stena bez prostredku s(m,z,... ), % leva ... )) tah/3: popis/jmeno tahu: pl1=predni,doprava,1x % jmena tahu mohou byt i struktury, napr. t(predni,doprava) z {..}x{doprava,doleva,dvakrat} tah(pr1,rk(s(P1,P2,P3,P4,P5,P6,P7,P8),s(L1,L2,L3,...), ...), % stara pozice rk(s(P6,P4,P1,P7,P2,P8,P5,P3),s(L1,L2,D1,L4,D2,...),..) ). % predni se otoci vpravo, doleva jde cast dolni steny ... odvozene tahy: tah(pr2,I,O) :- tah(pr1,I,I1), tah(pr1,I1,O). tah(pl1,I,O) :- tah(pr1,O,I). % prohozeni I a O, obecne nemusi fungovat otoceni pravou stenou, pomoci otoceni kostky tah(rr1,I,O) :- kostkaVlevo(I,I1), % interni proc. tah(pr1,I1,I2), kostkaVpravo(I2,O). % interni proc. nepotrebuji pojmenovani tahu kostkaVlevo(rk(P,L,Z,R,H,D),rk(R,P,L,Z,H1,D1)) :- % vyuziti shlukovani do sten stenaVpravo(H,H1), stenaVlevo(D,D1). % zavisi na konkretni repr./usporadani stenaVpravo(s(P1,P2,P3,P4,P5,P6,P7,P8),s(P6,P4,P1,P7,P2,P8,P5,P3)). % interpret, vykonani posl. tahu: % tahy/3: [tahy], In, Out tahy([],I,I). tahy([T|Ts],I,O):- % I,I1,O je vlastne predavani stavu tah( T ,I,I1), tahy(Ts,I1,O). --- interprety: vestavene is vyuziti operatoru, read pr: vyhodnocovani formuli, maticove a vektorove vyrazy, rubik, (multi)mnozinove vyrazy multimnoziny: seznam dvojic [Klic-Cetnost], dovolime i necele cetnosti (~pravdepodobnosti) alias histogramy (v 1D) varianty: usporadane vs. neusporadane, normalizovane(!): bez opakovani a bez 0 (diskutabilni pro psti) evalBag: jako u log. fli, obecne s Env_ironment operace: union/2, minus/2, intersect/2, krat(C)/1 (nasobi cetnosti xC), listToBag/1 (cetn:=1) ... samostatne operace, mimo eval: napr. celkova cetnost ... evalBag(Env, B1 union B2, V):- evalBag(Env, B1,VB1), evalBag(Env, B2,VB2), unionBag(VB1,VB2,V). ... evalBag/3 pro jine operace evalBag(Env, L, V) :- % koncova podm isList(L), % kontrola, muze selhat normalizeBag(L,V). % normalizace, napr. usporadani, odstraneni opak., pripadne s varovanim ... % ! usporadani a pod. nechceme pozadovat na uzivateli na vstupu --- kod, bags Sjednoceni multimnozin/bags rez vs not vs if: - rez je nedeklarativni, a nachylny k chybam (spis pri udrzbe) - not pocita dvakrat -> mene efektivni, nevhodny u nekonstantnich (O(1)) podminek a zretezeni podminek - if: mene prehledny, umoznuje zretezene podminky, nutno explicitne unifikovat vystupni prom., preprocesing a postprocesing se neopakuje (u ostatnich se opakuje v jednotlivych klauzulich) U: usporadane sjednoceni multimnozin (bag): struktura [Klic-Cetnost] Impl: pomoci if-then-else unionBag([],B2,B2). unionBag(B1,[],B1) :- B1 \= []. unionBag(B1,B2,B) :- B1=[K1-C1|B3], B2=[K2-C2|B4], % chci pristup na B1 a B2 vcelku ( K1 = K2 -> C is C1+C2, B = [K1-C|B5], % B5 je volne unionBag(B3,B4,B5) % Klic ubiram z obou ; K1 @< K2 -> B = [K1-C1|B5], % K1-C1 do vysledku unionBag(B3, B2, B5) % B1 zkratim ; /*else*/ B = [K2-C2|B5], unionBag(B1,B4,B5) % B2 zkratim ). ad: v podmince je obvykle nevhodne/nemozne neco pocitat, lze pouze testovat (uspech/fail), protoze promenne z podminky jsou volne v else-vetvi % sjednoceni pro neusporadane, bez opakovani unionBag2([],B2,B2) :- !. % zeleny rez, zabrani 2 resenim pro vstupy [],[] unionBag2(B1,[],B1) :- !. % zeleny rez unionBag2([K1-C1|B1],B2,[K1-C0|B0]):- ( delete(K1-C2,B2,B3) % !bez opakovani; kdyz nenajde, neuspeje % B3 je novy bag -> pamet O(n^2) -> C0 is C1+C2 % B3 urceno v podmince ; B3 = B2, C0 = C1 % (A) ), unionBag2(B1,B3,B0). % kdyz "dojde" B3, koncim hned, i diky rezu % Samostatna klauzule pro (A): neobsahuje vystupni unifikace unionBag2([K1-C1|B1],B2,[K1-C1|B0]):- % vime (dopredu), ze vystup se nemeni \+(member(K1-_,B2)), % kvuli deklarativite unionBag2(B1,B2,B0). % vime, ze b2 se nemeni 8.cv call/1, a varianty Reg. vyrazy. U: derivace RV podle pismena struktura RV: +/2, */1, seq/2, p/1 pismeno, lambda/0 prazdne slovo, empty/0 prazdny jazyk pr: p(b) seq (p(a)+ *(p(c))) - nacteni vyrazu ho prevede do interniho (stromoveho/naparsovaneho) tvaru Pozn: zavorky jsou pomocne symboly a v popisu struktury se nevyskytuji derivace RV podle (jednoho) pismena, bez zjednodusovani: derRV(RV,Pism,DerRV)/3 DC: zobecnete na derivaci podle slova DC: zjednodusovani, aspon trochu DC: prevod bohatsiho RV (any/0, +/1, opt/1 0-1) na chudy tvar, pro "any" potrebuju abecedu % definice pouzitych operatoru, */1 spis prefixni nez postfixni, a s malou precedenci derRV(lambda,_,empty). % vzdy chceme vydat nejaky jazyk, pripadne prazdny :-) derRV(empty ,_,empty). derRV(RV1+RV2, P, D1+D2) :- derRV(RV1,P,D1), derRV(RV2,O,D2). derRV(*(RV1), P, seq(D1,*(RV1)) ) :- derRV(RV1,P,D1). derRV(p(P),P,lambda) :- !. derRV(p(_P1),P,empty). % jine pismeno, nedeklarativni, kvuli rezu % idiom: p/1 mi umoznuje vyhnout se zachytne (catch-all) klauzuli pro "ostatni" znaky derRV(RV1 seq RV2, P, D0) :- derRV(RV1,P,D1), derRV(RV2,P,D2), % nelze dat do podminky, % protoze potrebujeme v else vetvi ( obsahujeL(RV1) -> % obecne: first(RV1,First), member(lambda,First) -> D0 = D1 seq RV2 + D2 ; D0 = D1 seq RV2 ). /* Pozn: RV v _zavorkach_ v programu neosetrujeme - zavorky se zpracuji pri syntakticke analyze a v internim tvaru se proto nevyskytuji - klauzule pro "obsluhu" zavorek by zpusobila zacykleni: derRV( (RV1), P, D1) :- derRV(RV1,P,D). */ % obsahujeL(empty). % empty neobsahuje lambda -> nechceme konc. podm % obsahujeL(p(_)). % dtto obsahujeL(lambda). obsahujeL(*(_)). obsahujeL(RV1+RV2) :- obsahujeL(RV1) ; obsahujeL(RV2). % pripadne se splni 2x: once/1 nize obsahujeL(RV1 seq RV2) :- obsahujeL(RV1), obsahujeL(RV2). % DC: naprogramujte first/2: first(RV,First), First je seznam (reprezentujici mnozinu) moznych prvnich pismen a pripadne lambda % hacker's corner: once(Pred) :- call(Pred),!. % splni se jednou % omezene kvantifikace: forall z prednasky TD U: Naprogramovat test, zda RV prijima dane slovo. Impl. pomoci derivace: Postupne prochazeni RV podle derivace podle slova. Na N znaku, potom test obsahujeL/1. Var: Anebo podle delky slova. Pozn: - zjednodusovani RV je mozne (a vhodne), ale neupravime RV na jednoznacny standardni tvar - RV (nejlepe zjednoduseny) odpovida stavu automatu ; pomoci tabelace a spekulativnim vyhodnocovanim, tj. derivaci podle vsech moznych pismen lze postavit (nenormalizovany) deterministicky automat /* 9cv. Scheme ad: flatten (atom?) --- reverse linarne (define (reverse xs) (define (rev1 acc xs) ;lokalni vykonna procedura (if (null? xs) acc (rev1 (cons (car xs) acc) ; novy acc_umulator, tail-rekurze ; cons je vhodnejsi nez append (cdr xs) ) ) ) (rev1 () xs) ) ; telo reverse je volani pomocne fce --- filter: dostane funkci jednoho arg. (tj. podminku) a seznam prvku; vrati seznam prvku, ktere splnuji podminku (define (filter p xs) (if (null? xs) () (if (p (car xs)) (cons (car xs) (filter p (cdr xs))) (filter p (cdr xs)) ) ) ) - Q efektivita: v tele jsou dve rekurzivni volani. Nehrozi exponencialni slozitost jako u fibonacciho cisel? - popiste chovani 4 vyskytu p: definice vs. pouziti, volani vs. predani aplikace filter: split v quicksorte (jeden mozny zpusob predavani parametru): split dostane funkci "mensi" jednoho argumentu a seznam prvku, vrati dva seznamy: v prvnim prvky, pro ktere plati podminka, ve druhem ostatni (define (split_Poor mensi xs) (cons (filter mensi xs) (filter ?? xs) ) ) Q: co patri na misto otazniku? prvni pokus: volani ... (filter (not mensi) xs) ... je nespravne, protoze not neguje hodnoty, ne funkce A: ... (filter (lambda (x) (not (mensi x))) xs) ... v FP muzu mit (jako platny kod) funkci zdvihF1 (zdvih funkce s 1 arg) (define (zdvihF1 op f) (lambda (x) ; vracena funkce (op (f x)) ) ) ; telo funkce a potom volani vypada: ... (filter (zdvihF1 not mensi) xs) ... Q: argumenty quicksortu je funkce cmp dvou argumentu, ktere se porovnavaji. Jak se bude volat split? ... (split (lambda (x) (cmp x pivot)) xs) jiny priklad "upravy funkce": swap argumentu funkce dvou promennych (define (swap f) (lambda (x y) (f y x)) ) aplikace: ... (2012) Q: funkce zip dostava 3 argumenty, a to funkci f dvou args a dva seznamy, obvykle stejne dlouhe. Zip aplikuje f na odpovidajici si prvky seznamu a vytvori vysledek delky kratsiho ze seznamu (define (zip f xs ys) (if (or (null? xs) (null? ys)) ; aspon jeden seznam skoncil () (cons (f (car xs) (car ys)) (zip f (cdr xs) (cdr ys)) ) ) ) Q: tri ruzne vyznamy f pro ruzne vyskyty priklad volani zip: nasobeni 2 vektoru po bodech (napr. po FFT) ; fce *vectBodove/2 (define (*vectBodove us vs) (zip (lambda (x y) (* x y)) us vs) ) ; bez rekurze ; podobne scitani a odcitani 2 vektoru ... Q: ktera jina operace je vhodna pro nasobeni vektoru konstantou? --- hornerovo schema 3x - viz prednasky 1) vypocet hodnoty v bode 2) konstrukce (efektivni) funkce pro vypocet polynomu z koeficientu 3) konstrukce zdrojaku (tj. vyrazu) teto funkce v scheme je eval/1 a apply/2, ktere kvuli typum nejsou v Haskellu eval v - vyhodnoceni vyrazu v apply f args - zavolani funkce f na argumenty dane v seznamu pouziti eval: (let ((y 5)) (eval (hornerovoSchema3 '(3 2 1) 'y))) -- druhy par. hornerovoSchema3 je jmeno promenne, tj. symbol y vysledek (HornerovoSchema3 '(3 2 1) 'y) je symbolicky vyraz pro polyn. x^2+2*x+3, tj. napr. '(+ 3 (* y (+ 2 (* y (+ 1 (* y 0)) )) )) ktery muzeme vyhodnotit v kontextu, kde je y definovano pr: apply (apply list '(1 2 3)) ~> vola (list 1 2 3) (apply + (list 1 2 3)) ~> 6 -- apply je vhodne pro vnorene (embedded) jazyky, protoze umoznuje jednotny pristup k volani funkci (2011) - bezny zpusob je programovani funkci s (funkcionalnimi) parametry -> jsou obecne, zadanim parametru je lze specializovat, (closure) -> kratsi kod, mene chyb -> "syntakticka" cena za funkcionalni parametr je mala pr: sort s porovnavaci funkci DC: zip: dostava 2 seznamy a funkci dvou argumentu a vraci seznam prvku. Prvek vznika zavolanim funkce na stejne pozice vstupu', pripadny delsi seznam zkrati. - pozn: v scheme je 'map s promennym poctem argumentu - aplikace: scitani, odcitani, nasobeni vektoru po slozkach, aritm. prumer DC: volani zip s lambda funkci pro aritmeticky prumer DC: zip vraci seznam funkci vazeneho aritmetickeho prumeru. Hodnoty x a y jsou fixovany ze vstupu, 1 parametr je vaha a (alfa), pocitame hodnotu a*x+(1-a)*y - idiomy FP, odlisnosti FP -! datove struktury (z dvojic): seznamy, n-tice, stromy, tagovane struktury (kompl. cisla) --- n-nasobna aplikace aplN dostava n, funkci f jednoho parametru a hodnotu x. Funkci f vola opakovane n-krat na x, tj f^n(x) dva zpusoby: 1) ala rekurze , 2) ala akumulator - pouziti: x je stav (napr. automatu), f je zmenova funkce (delta), aplN simuluje n kroku. 1) (define (aplN1 n f x) (if (= n 0) x (f (aplN1 (- n 1) f x)) )) 2) (define (aplN2 n f x) (if (= n 0) x (aplN2 (- n 1) f (f x)) )) ; f x se pocita hned (eager) Q: ma smysl se snazit o optimalizaci jako u rychleho umocnovani cisel (tj. postupne "na druhou") (DC) fixpoint: volame f na x, dokud f^n(x) a f^(n+1)(x) nejsou stejne, vracime vyslednou hodnotu fixpointu --- make BT - prazdny strom je 'void, lze taky definovat konstruktor - pro neprazdny strom 1) tag je 't, vcetne tagu definuju ctverici (define (mkBt l x r) (cons 't (cons l (cons x r))) ) 2) tag stejny, definuju jako seznam (vestavena funkce list) (define (mkBt2 l x r) (list 't l x r) ) Q: je struktura v 1) a 2) stejna? Ma stejnou spotrebu pameti? --- DC: 1) map 2) insert do BT (pripadne s parametrickym porovnavanim) 10cv. Haskell - klouzavy prumer ze 3 - klouzavy prumer z n - mergesort, sude, liche, merge - testKomut - kartezsky soucin - filter - tridy ekv. - lookup, zjednoduseny - automaty (2x), reprezentace DKA vs. NKA, krok - (rychle umocnovani) - (FFT) -- klouzavy prumer ze tri prvku klouzavyp3 :: [Float] -> [Float] klouzavyp3 (x1:x2:x3:xs) = ((x1+x2+x3)/3.0) : klouzavyp3 (x2:x3:xs) -- nedokonale klouzavyp3 _ = [] -- pokud nejsou 3 prvky na vstupu -- klouzavy prumer z n klouzavypN :: Int -> [Float] -> [Float] klouzavypN n xs = if length xs < n then [] else prumer (take n xs) : klouzavypN (tail xs) -- prumer= ... -- DC: jak zoptimalizovat, aby se delka nepocitala na kazde urovni rekurze? -- DC: jak zoptimalizovat, aby se nova hodnota prumeru spocitala ze stare v O(1)? - (FFT) -- mergesort, sude, liche, merge -- mergesort s porovnavacou funkciou cmp, a pomocne procedury mergesort :: (a->a->Bool) -> [a] -> [a] -- nepresne, chybi: Eq a => mergesort _cmp [] = [] mergesort _cmp [x] = [x] -- potrebujeme konc. podm., jinak se zacykli mergesort cmp xs = merge (mergesort cmp (liche xs)) (mergesort cmp (sude xs)) -- volani: (do prednasek) tme1 = mergesort (<) [1,2,3] -- vzestupne, bezne (pretizene) porovnavani tme2 = mergesort (flip (<)) [1,2,3] -- sestupne tme1 = mergesort (\(x1,y1)(x2,y2)->y1a->b) chceme otestovat, zda je komutativni pro dane dvojice vstupu testKomut :: (a->a->b) -> [(a,a)] -> Bool testKomut f [] = True testkomut f ((x,y):xs) = f x y == f y x && testKomut f xs -- DC: reseni pomoci map a and :: [Bool] -> Bool -- diky linemu vyhodnocovani se dvojice generuji a zpracovavaji postupne -- kartezsky soucin, dva zpusoby -- filter: vybere ze seznamu prvky, ktere splnuji (parametrem) danou podminku filter :: (a->Bool) -> [a] -> [a] filter p [] = [] filter p (x:xs) | p x = x : filter p xs | True = filter p xs -- tridy ekv. -- je dana fce ekvivalence :: a->a->Bool; dany seznam chceme rozdelit na tridy ekvivalence tridyEkv :: (a->a->Bool) -> [a] -> [[a]] -- vstup je seznam, vystup je seznam trid ekv., tj. seznam seznamu tridyEkv f [] = [] tridyEkv f (x:xs) = (x: filter (\y -> f x y) xs): tridyEkv f (filter (\y -> not(f x y)) xs) -- ^^ trida {x} ^^ ostatni prvky -- lookup, zjednoduseny, pro automaty; vzdy uspeje lookup :: a -> [(a,b)] -> b -- zjednodusene :-( -- automaty (2x), DKA vs. NKA, krok -- reprezentace prechodove funkce (delta) DKA: -- 1) [(stav,symbol,novyStav)] -- nejde pouzit lookup -- 1a) [((stav,symbol),novyStav)] -- klic je slozeny, "no a?" - nevadi -- 2) [(stav,[(symbol,novyStav)])] -- DC: upravte struktury pro nedet. automaty (bez lambda-prechodu) -- 1 krok, -- krok :: krok1a stav symbol delta = lookup (stav,symbol) delta krok2 stav symbol delta = lookup symbol (lookup stav delta) -- DC: pro nedet krok2N :: [stav] -> symbol -> [ (stav,[ (symbol,[stav]) ]) ] -- potrebujeme map pro vstup a concat pro vystup -- (rychle umocnovani) -- x^n umocni :: Int -> Integer -> Integer umocni n x | n==0 = 1 | even n = umocni (n`div`2) (x*x) | otherwise = x * umocni (n-1) x -- liche n -- (full-laziness) 11.cv. HS -- krokovac konecnych automatu (det., nedet.) -- vyhodnocovani konc. podminky u nedet. -- exists, (any) -- zip, zipWith, zip3 -- grafy, reprezentace -- opacny graf -- DC: zdvojeni grafu (... a jine operace) -- lookup pro vyhledani v seznamu -- zjednodusena verze: vzdy uspeje (u DKA plati) -- DC: proc nestaci funkce `elem` jako v Prologu? -- typy prechodove funkce NKA delta type Delta stav symbol = [(stav,[(symbol,stav)])] type DeltaN stav symbol = [(stav,[(symbol,[stav])])] -- DC: vysvetlete rozdil mezi reprezentaci prechodove funkce bud -- jako datove struktury nebo jako (haskelske) funkce -- krok: jeden krok deterministickeho automatu krok :: Delta stav symbol -> stav -> symbol -> stav krok delta st sy = lookup sy (lookup st delta) -- kroky: kroky podle vstupu, vydava stav kroky :: Delta stav symbol -> stav -> symbol -> stav kroky delta st [] = st kroky delta st (sy:sys) = kroky delta (krok delta st sy) sys -- krokyN: pro nedet. automat - mame mnoziny stavu krokyN :: Delta stav symbol -> [stav] -> symbol -> [stav] krokyN delta sts [] = sts krokyN delta sts (sy:sys) = krokyN delta (krokN delta sts sy) sys -- krokN: zde: seznam stavu na seznam stavu; -- varianta: jeden stav na seznam, "nedeterminizmus" osetrit az pri volani krokN :: Delta stav symbol -> [stav] -> symbol -> [stav] krokN delta sts sy = union (map (\st -> lookup sy (lookup st delta)) sts) -- DC: union :: [[a]] -> [a] -- urcovani koncoveho stavu: mame k dispozici isFinal :: ... -> stav -> Bool pro -- urceni, zda (jeden) stav je koncovy -- koncove stavy jako datove struktura: seznam: [stav] -- koncove stavy jako funkce: (isFinal stavy) isFinal :: [stav] -> stav -> Bool isFinal stavy stav = stav `elem` stavy -- jen jine jmeno -- isNedetFinal - aspon jeden stav NKA je koncovy isNedetFinal :: (a -> Bool) -> [a] -> Bool -- primocara rekurze isNedetFinal [] = False isNedetFinal (s:ss) = isFinal s || isNedetFinal ss -- abstrahujeme vykonnou funkci: existuje aspon jeden prvek, ktery splni test -- v logice: _omezena_ existencni kvantifikace (v HS fce any, jinde nazyvana exists) -- soucast Prelude any :: (a-> Bool) -> [a] -> Bool any f [] = False any f (x:xs) = f x || any f xs -- chceme line/lazy (||) -- aplikace: isNedetFinal xs = any isFinal xs -- variantna definice exists any f xs = or (map f xs) any f _xs = (or . map f) _xs -- pozn: pokud je map a or li'ne, pak se any vyhodnocuje li'ne, -- ale na rozdil od prime rekurze spotrebuje (postupne) pamet -- na mezivysledky (vystupy map a vstup or) -- dualne: fce all: vraci True, kdyz pro vsechny prvky plati podminka all f xs = and (map f xs) -- DC: or - aspon jedna hodnota je pravdiva -- soucast Prelude or :: [Bool] -> Bool -- (zpracovani seznamu pomoci foldr) -- analogicke funkce pro splneni vsech podminek ... and :: [Bool] -> Bool -- vsechny hdnoty jsou pravdive -- zip, zipWith -- zip dostava dva vstupni seznamy a z prvku na stejnych mistech vytvori dvojice. -- (moc primocary pristup:) Tyto dvojice pak zpracuje napr. map zip :: [a] -> [b] -> [(a,b)] zip (x:xs) (y:ys) = (x,y) : zip xs ys zip _ _ = [] -- do druhe klauzule se prejde, jen pokud je nektery seznam prazdny -- ! na rozdil od Prologu -- pokud jsou seznamy ruzne dlouhe, zkrati se podle kratsiho -- specialne: pokud je jeden seznam nekonecny stream, zkrati se podle druheho -- abstrakce zip: predavame funkci, ktera urcuje, jak zpracovat odpovidajici "dvojici" -- typy na vstupu a vystupu jsou ruzne zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] zipWith f (x:xs) (y:ys) = x `f` y : zipWith f xs ys zipWith _ _ _ = [] -- DC: zip3 a zipWith3 pro tri vstupni seznamy. (... a analogicky pro vic vstupnich seznamu) -- DC: z typovych duvodu musi byt funkce zip, zip3, zip4 ... samostatne. Vysvetlete, rozeberte jine moznosti. -- Grafy -- navrhnete konkretni reprezentace grafu: matice sousednosti, seznamy sousedu -- bez ohodnoceni, s ohodnocenim vrcholu nebo hran -- opacny graf -- type Graf a = [(a,[a])] opacnyG graf = map (\(v,_) -> (v,predch graf v) ) graf -- kazdemu vrcholu najdeme vsechny predchudce, -- ! predavame pouze vrchol v, jeho sousedy nepotrebujeme where predch graf v = map (\(x,_) -> x) -- (1), z dvojice chceme jen prvni slozku: vrchol ( filter (\(x,sous) -> v `elem` sous ) -- filtrujeme vrchol s hranou do v graf ) -- ad (1): protoze mame celou informaci o hranach, muzeme pripadne vybrat take ohodnoceni hrany -- ! zpracovavame cele datove struktury -- DC: zdvojeni grafu (... a jine operace) {- na vystupu je k graf, ktery obsahuje dve kopie vstupniho grafu. Hranou jsou spojeny vrcholy v jednotlivych kopiich jako v puvodnim grafu a navic odpovidajici si vrcholy mezi kopiemi -} -- konecny automat jako ohodnoceny graf ------------ -- cprod::[[a]]->[[a]] -- kaetezsky soucin -- functional pearl, lambda-liftnute ~skryte params cprod = foldr f [[ ]] where f xs yss = foldr (g yss) [ ] xs g yss x zss = foldr (h x) zss yss h x ys uss = (x : ys) : uss -- syntakticka analyza ;@mocniny data NT a = NT a [NT a] deriving (Eq,Ord,Read,Show) valNT (NT x _) = x -- prefix, s cetnostou syntPre :: (Ord a, Num a) => [(b,a)] -> NT (b,a) syntPre xs = syntPre1 s xs where syntPre1 ((NT(c,nx)_):s) xs | nx<0 = error "in syntPre: moc argumentu" syntPre1 (top@(NT(c,0)ts):NT (c1,n1) ts1 : s) xs = -- top je uplny term syntPre1 (NT (c1,n1-1) (ts1++[top]):s) xs syntPre1 s ((c,n):xs) = syntPre1 (NT (c,n) [] :s) xs syntPre1 s [] | length s>1 = error "in syntPre: neuplny vyraz" | (0/=)$snd$valNT$head s = error "in syntPre: neuplny vyraz_2" | otherwise = head s -- OK, prave jeden vysledek s = [] -- init: stack -- postfix, s cetnostou syntPost xs = syntPost1 s xs where s = [] syntPost1 s ((c,0):xs) = syntPost1 (NT c []:s) xs syntPost1 s ((c,n):xs) | length s >= n = syntPost1 (NT c (take n s):drop n s) xs | otherwise = error "in syntPost: neuplny vyraz" syntPost1 s [] | length s >1 = error "in syntPost: moc argumentu" | otherwise = head s ---- prvocisla: eratostenovo sito prvocisla = sito [2..] sito (p:xs) = p : sito (filter (\y->y`mod`p/=0) xs) -- ((/=0).(`mod`p)) -- sito (p:xs) = p:sito [x | x<-xs, x`mod'p /=0] -- prvocisla prvocisla2 (x:xs) = x: prvocisla2 (filter (\y->y`mod` x /=0) xs -- ...filter((0/=).(`mod` x)) xs ... ---- rekurzivni definice typu -- unarni cisla: Zero, S/1 data Nat = Zero | S Nat -- prirozene cisla dve = S (S Zero) tri = S $ S $ S Zero plusNat Zero y = y -- z Robinsovovy aritmetiky plusNat (S x) y = S (plusNat x y) -- pro Nat muzeme definovat plus, krat ... a instanci Num -- Programatorsky idiom/Navrhovy vzor (builder); misto konkretnich konstruktoru piseme obstraktni konstruktory; ~odpovida konkretnim kostruktorum s naslednym pouzitim "fold" dve'= s (s zero) where s = S zero = Zero -- ale abstraktni konstruktory muzou stavet strukturu jinak, napr. binarni cislo (misto unarniho) -- pr: konstruktory pri stavbe seznamu muzou vyhazovat opakovane prvky, pocitat histogram nebo prvky usporadavat -- formule vyrokoveho poctu data FleVP a = Con Bool -- typ natvrdo, pracujeme s formulemi VP | Var a | Not (FleVP a) | And (FleVP a) (FleVP a) | Or (FleVP a) (FleVP a) | Imp (FleVP a) (FleVP a) | Ekv (FleVP a) (FleVP a) -- a dalsi spojky, pokud chceme -- typicky (domenove) promenne pojmenujeme retezci, ale muzeme i cisly (za typovou promennou a dosadime String, resp. Int) -- meta: jako uzivatel chceme co nejvic moznosti (zde: spojek) v programu/knihovnach -- jako tvurce/spravce/navrhar chceme co nejmene rysu; casto je vhodne data prevadet -- do vhodneho "core" tvaru -- jine moznosti navrhu: -- 2. moznost : samostatne konstanty -- data FleVP2 a == CTrue | CFalse | ... -- konstanty odlisene, pokud je jich malo -- 3. moznost : spojene spojky -- data FleVP3 a == Con Bool | Var a | Term String [FleVP a] -- -- dovoluje pridavat spojky za behu, ale nekontroluje napr. jejich pocet argumentu -- jmena spojek jsou natvrdo String, pripadne vyctovy typ; dovoluje patt.match -- -- 13.cv 2014 (Hs 4) -- cvicime : strucne seznamy - pytagorejske cisla - opacny graf - unionL :: [[a]] -> [a] - FFT - procisla , sito - unarni Nat, aktivni konstruktory - usporadani (spravedlive): po uhloprickach, (maxlex) - porovnani dvojich, next: dalsi dvojice, ... 12.cv 2012 -- hi-ord funkce -- huffmanovo kodovani a) kodovani podle tabulky b) prevod stromu na tabulku c) postaveni huff. stromu d) dekodovani podle stromu 13.cv 2012 -- fold a varianty 14.cv 2014 (Hs 5) 1) nacitani prefixniho vyrazu 2) foldNT, sizeNT, depthNT 3) huffmanovo kodovani a) kodovani podle tabulky b) prevod stromu na tabulku c) postaveni huff. stromu d) dekodovani podle stromu ------------ 13.cv 2014 -- cvicime : strucne seznamy - pytagorejske cisla, omezene neomezene - opacny graf; a oboje - unionL :: [[a]] -> [a] - FFT - procisla , sito - unarni Nat, aktivni konstruktory - usporadani (spravedlive): po uhloprickach, (maxlex) - porovnani dvojic primo a prevodem; next: dalsi dvojice v usporadani ----------- -- opacny graf -- uloha: k orientovanemu grafu ( v enjekaej reprezentacii) vyrobit opacny graf -- meta: pokud budeme pouzivat hrany aj protismerne, tak je mozne a vhodne mat v grafe nielen naslednikov, ale aj predchodcov. -- type Graf2 a = [(a,[a],[a])] -- trojice (vrchol, naslednici, predchodcovia) opacnyG2 gr = map (\(v,ns,ps) -> (v, ps,ns)) gr -- to bolo jednoduche, ale ucinne; pouziva viac pamati -- pre klasicku reprezentaciu -- type Graf a = [(a,[a])] -- struktura (vrchol, naslednici) opacnyGr gr = map spracujV gr where spracujV (v,_ns) = (v,map fst$filter (\(p,ps)-> v `elem` ps) gr) -- vrcholy p, ako prva zlozka, ktore maju medzi svojimi naslednikmi ps vrchol v ------ -- jine usporadani (dvojic) {- klasicke lexikograficke usporadani dvojic (prirozenych cisel) ma nevyhodu, ze nevybira prvky z radků spravedlive, tj. pred nekterymi prvky je nekonecne mnoho dvojic. Spravedlive usporadani jsou napr. uhloprickove a maximolexikograficke. Uhloprickove usporadava uhlopricky (tj. soucty) a v ramci uhlopricky lexikograficky. Maxlex usporadava podle maxima a potom lexikograficky. Oboje je zobecnitelne na realna cisla, na n-tice a na seznamy. V pripade seznamu se do maxima bere take delka seznamu. Naprogramujte: 1. porovnani dvojic 2. generovani nasledujici dvojice. 2a. Pouzijte v iterate pro generovani posloupnosti 3. ... neco z cviceni 4. napiste newtype a instanci tridy -} -- uhloprickove cmpU :: (Ord a,Num a)=>(a,a)->(a,a)->Bool cmpU (x1,y1) (x2,y2) = (x1+y1,x1) <= (x2+y2,x2) nextU :: Num a => (a,a) -> (a,a) nextU (x,0) = (0, x+1) -- konec uhlopricky, posun na dalsi nextU (x,y) = (x+1,y-1) -- po uhlopricce genSrtU :: Num a => (a,a) -> [(a,a)] -- generovani od lib. prvku -- genSrtU0 :: Num a => [(a,a)] -- generovani od 0 genSrtU x = iterate nextU x -- maxlex -- prevedeme na klasicke --cmpML :: Ord a => (a,a) -> (a,a) -> Bool cmpML (x1,y1) (x2,y2) = (max x1 y1, x1,y1) <= (max x2 y2,x2,y2) nextML (x,y) | x == y = (0, x+1) -- zaciname dalsi pas | x < y-1 = (x+1,y ) -- svisla cast | x == y-1 = (y, 0 ) -- posledni svisly | otherwise = (x, y+1) -- vodorovna cast genSrtML x = iterate nextML x -- zobecneni .... -- instance, i v prednaskach -- newtype ------------ -- sjednoceni nekolika seznamu unionL :: [[a]] -> [a] unionL = foldr union [] -- FFT -- ladene fft :: Num a => a -> [a] -> [a] fft _ [x] = [x] fft e xs = vs where (sude,liche) = rozdel xs vs1 = fft (e*e) sude vs2 = fft (e*e) liche slozka2 = zipWith (*) vs2 (iterate (e*) 1) vs = zipWith (+) vs1 slozka2 ++ zipWith (-) vs1 slozka2 --vs0 = zipWith3 (\s l ei->s+l*ei) vs1 vs2 (iterate (e*) 1) ++ -- zipWith3(\s l ei->s-l*ei) vs1 vs2 (iterate (e*) 1) -- varianta -- deli na (sude, liche) rozdel [] = ([],[]) rozdel (z@[x]) = (z,[]) rozdel (x1:x2:xs) = (x1:xs1,x2:xs2) where (xs1,xs2) = rozdel xs 14.cv 2014 1) nacitani prefixniho vyrazu -- vys 2) foldNT, sizeNT, depthNT -- fold pro n-arni stromy, i v prednaskach data NTree a = Tr a [NTree a] -- jeden konstruktor -- Tr :: a -> [NTree a]-> NTree a foldNT :: (a -> [b] -> b ) -> NTree a -> b -- funkce v arg.1 opisuje, jak se zpracuje 1 uroven; podobne jako kdyz konstruktor (ve FP) -- popisuje, jak se konstruuje 1 uroven datove struktury foldNT f (Tr a ps) = f a (map (foldNT f) ps) -- map spracuje _seznam_ podstromu, kazdy nezavisle -- pouziti foldNT -- sizeNT: velikost stromu, tj. pocet vrcholu sizeNT :: Tree a -> Int sizeNT = foldNT (\x vs -> sum vs + 1) -- secti vysledky vs z rekurze a pricti 1 za aktualni vrchol -- depthNT: hloubka stromu, pro list musime vhodne osetrit rekurzi depthNT :: Tree a -> Int depthNT = foldNT (\_x vs -> if null vs then 0 else 1+max vs) 3) huffmanovo kodovani, -- ladene -- strom bez vnitrnich informaci, data pouze v listech: Tree a -- tabulka: pismeno na seznam kodu; kody 0/1, ale pomoci Int: [(a,[Int])] data Tree a = Leaf a | Branch (Tree a) (Tree a) -- a) kodovani podle tabulky -- v tabulce se dobre hleda; po znacich prevest a spojit codeH :: Eq a=> [(a,[b])] ->[a] ->[b] codeH tab xs = concat( map (\x->unJust$lookup x tab) xs) --unJust (Just x) = x -- zbavi sa Just, -- kdesi vys -- b) prevod stromu na tabulku -- toTabH, pro kodovani potrebuju tabulku misto stromu toTabH :: Tree a -> [(a,[Int])] toTabH (Leaf x) = [(x,[])] toTabH (Branch l p) = map (\(x,code)->(x,0:code)) (toTabH l) ++ map(\(x,code)->(x,1:code)) (toTabH p) -- c) postaveni huff. stromu -- tezka cast; !! to uz kdesi musi byt -- na vstupu jsou znaky a frekvence, na vystup jde strom makeH :: [(a,Int)] -> Tree a makeH xs = v where -- po fazich xs2 = map (\(x,n)->(Leaf x,n)) xs -- vyrobime male stromecky xs3 = sort cmpH xs2 -- usporadame, podle n vzestupne cmpH (x1,n1) (x2,n2) = n1<=n2 -- podle druhe slozky, tj. cetnosti xs4 = head $ -- vyberieme jednoprvkovy zoznam dropWhile (\x->length x>1) $ -- zahadzujeme nedokoncene spojovanie iterate (spojH cmpH) xs3 -- spajame stromy spojH cmpH((x1,n1):(x2,n2):xs) = insert cmpH (Branch x1 x2,n1+n2) xs -- spojeny zatriedime v = fst$head xs4 -- ostal 1 strom, vratime ho sort _cmp [] = [] sort cmp (x:xs) = [y|y<-xs,not $ x`cmp`y]++[x]++[y|y<-xs,x`cmp`y] insert cmp x [] = [x] insert cmp x (y:ys) | x `cmp`y = (x:y:ys) | otherwise = y:insert cmp x ys -- d) dekodovani podle stromu -- nejdou pouzit bezne funkce, protoze delka kodu a teda odebirane casti je promenliva decodeH :: Tree a -> [Int] -> [a] decodeH t [] = [] -- konec vstupu decodeH t xs = c:decodeH t xs1 -- rozkoduj 1 znak c a pokracuj where (c,xs1) = decode1 t xs decode1 (Leaf c) xs2 = (c,xs2) decode1 (Branch l p) (0:xs2) = decode1 l xs2 decode1 (Branch l p) (1:xs2) = decode1 p xs2 -- prazdny vstup znamena chybny kod, neresime -- lokalne v decode1 se podstrom zmensuje, ale v hlavni fci ddecodeH se predava histogram xs = map (\x->(head x,length x)) $ tridyEkv (==) xs -- pro analyzu spravy test20 xs = (histogram xs) ------------ -- pozn -- closure. hm -- memory leak: 3 druhy 1. velka vyhodnocena struktura zustava v pameti, kvuli sdileni vysledek prvniho generatoru v strucnych seznamech; lacine data _re-generovat_ (a nesdilet); misto konstanty pouzit dummy funkci; 2. velka struktutura se buduje a nevyhodnoti akumulator ve foldl; pouzit strictni vyhodnoceni 3. argument je slozeny a drzi odkaz na nepotrebnou strukturu fst (a,big) -- read,show: je oddeleny prevod z/na string od vlastniho vypisu -- aktivni konstruktory, mozna navrhovy vzor buider -- ad fold: misto samostatnych funkci pro jednotlive konstruktory lze pouzit jednu funkci, ktera popisuje zpracovani jedne urovne datove struktury ze zobecnenych kostruktoru realizovanych pomoci Either, tj. stejne jako pri unfold */