% cv. 5 ; na 22.3.2017 (St) ; Jan Hric
% v. 1.3.4	29.3.2019
% v. 1.4	20.3.2020
%		1.4.2021

% Obsah: cv5 

% opakovani
% prunik, 3 moznosti rizeni
% logicke formule vyrokove logiky
%   operatory
%   eval
% posbirani promennych z formule: =../2 a pod
% heapsort
%
% --
% vyhledavani, i slozene (?)
% idiom: interpret
% stromy: i n-arni

% zbylo (z cv4): kartezsky soucin
% - i indexovana varianta



%%%%%%%%%%%%%%%%%%%%% Opak.
% priprava adresare:
% :- cd('c:/moje'). % s doprednymi lomitky, s apostrofy a s diskem c:
% oznam adresare:
% :- pwd.
% kolik mate a potrebujete pameti ...
% :- statistics.

%%%%%%%%%%%%
% prunik/3, mod (+,+,-)
% - 3 moznosti, na prednasce bylo na prikladu sjednoceni 
%   - a) podminka na (B)  ; nevyhoda: test 2x
%   - b) rez na (A)       ; mene prehledne, nedeklarativni
%   - c) 2. a 3. klauzule spolu pomoci if->then;else ; 
% - spravnost vuci backtrackingu, viz priklad
% - prunik usporadanych mnozin, viz dale

% interface, budeme pouzivat, mozna
prunik(Xs,Ys,Vs) :- prunik3(Xs,Ys,Vs). %

% chybny prunik0/3: prvni reseni je OK, ale pak vydava dalsi nespravna reseni
% - problem je, ze pri backtrackingu se pouzije i treti klauzule, 
%   protoze neobsahuje podminku (straz)
%   - treti klauzule je deklarativne nespravne (v kontextu procedury s rezem "!" muze fungovat)
prunik0([],_,[]).
prunik0([X|Xs],Ys,[X|Vs]) :- 
  member(X,Ys),     % (A)
  prunik0(Xs,Ys,Vs).
prunik0([_X|Xs],Ys,Vs):- % (B)
  prunik0(Xs,Ys,Vs).

tf2(V):- prunik0([1,2,3],[4,2,1],V).
% vyzkouset i pro verze nize:
% a) je nedeterministicke (vyzaduje strednik na "false"), 
% b) a c) jsou deterministicke (skonci bez stredniku) 

% podobne se muze rozbehnout i nekonecny cyklus, kdyz spatne osetrite podminku pro rekurzi
% priklad: faktorial: fakt(0) = 0*fakt(-1) :-(

% 3 (spravne) varianty
% a) 2x test
prunik1([],_,[]).
prunik1([X|Xs],Ys,[X|Vs]) :- 
  member(X,Ys),     
  prunik1(Xs,Ys,Vs).
prunik1([X|Xs],Ys,Vs):- 
  not(member(X,Ys)),	 % (B)
  prunik1(Xs,Ys,Vs).

% b) rez !
prunik2([],_,[]).
prunik2([X|Xs],Ys,[X|Vs]) :- 
  member(X,Ys),!,     % (A)
  prunik2(Xs,Ys,Vs).
prunik2([_X|Xs],Ys,Vs):- % (C)
  prunik2(Xs,Ys,Vs).

% c) if-then-else "-> ;"
prunik3([],_,[]).
prunik3([X|Xs],Ys,Vs0) :- 
  member(X,Ys) ->     	% (A)
    prunik3(Xs,Ys,Vs1), 
    Vs0=[X|Vs1] 	% (D)
  ; prunik3(Xs,Ys,Vs0).

/* pozn. 
a) test se dělá dvakrát (druhý je (B)), program je časově náročnější
b) použití řezu (A), následně test v třetí klauzuli (C) lze vynechat. 
   Ale třetí klauzule samostatně je deklarativně špatně. 
c) test jednou (A), výstup ze dvou větví ';' je různý, proto musíme explicitně přiřadit výstup (D);
	- v jiných variantách je výstup zapsán v hlavě
 */


% cviceni: rozdilMn/3: mnozinovy rozdil
rozdilMn(Xs,Ys,Vs) :- Vs = [].	% chceme Vs = Xs\Ys
tf2a(Vs) :- rozdilMn([1,2,3,5],[4,3,2], Vs).

% cviceni: usporadane verze prunik/3, sjednoceni/3, rozdilMn/3
% pozn.: 3 predikaty se daji zobecnit do jedne proc., ktera dostane,
% co ma delat v jednotlivych pripadech

% cviceni: 3 operace pro multimnoziny (je jinde?)
rozdilMM(MM1,MM2,MMV) :- MMV = [].	% MMV je výsledná multimnožina
tf2b(Vs) :- rozdilMM([a-2,b-1,c-3,e-4], [a-2,b-2,e-2], Vs).
  % očekávame Vs = [c-3,e-2] , v nějakém pořadí
  % - speciálně, bez dvojic X-0 (zde bez a-0 a b-0)


%%%%%%%%%%%%%%%%
% interpret mnozin ; 
% vyhodnocovani (konstantnich) mnoz. vyrazu evalSet/2, evalSet(+MnVyraz, -V) 
% operatory \-/ /-\ \-- pro sjednoceni, prunik, rozdil respektive
%   - a symetricky rozdil, unarni union, ...
% a koncova podminka, s kontrolou

% ?- evalSet([1]\-/[2]/-\[3]\--[4],V).

% zavedeni operatorů
% - operatory op/3 jsou direktivy pro prolog; nechceme je vkladat do db.
%   -> radek zacina :- anebo ?- (stejne jako pro consult)
%   :- op(precedence, typ, jmeno).
% - operatory usnadnuji zapis funkcnich i predikatovych symbolu, 
%   ale nezavadi zadnou semantiku
%   -> po nacteni je d.s. stejna jako ta z prefixniho zapisu
%   - výpis pomocí vestavěného display/1
% - priorita vs. precedence: vyssi matematicka priorita vic vaze, odpovida to 
% 	nizsi precedenci a poloze niz ve stromu/termu (zakořeněném nahoře)
%   - vzhledem k uz definovanym operatorum, pouzivaji se precedence okolo 300 pro termy

% :- op(precedence, typ, /-\).
:- op(200, yfx, /-\).

% CV: definujte operatory:
% \--/ union unarni, s nejvyssi (matematickou) prioritou, opakovatelny
% /-\ prunik binarni s mensi (matematickou) prioritou, asoc. doprava
% \-- mnozinovy rozdil, binarni s mensi prioritou, asoc. doleva
% -\- symetricky mnoz. rozdil, binarni se stejnou prioritou, neasociativni
% \-/ sjednoceni, s nejmensi prioritou, asoc. doprava 
 
% test:
% tf3(_) :- display([1]\-/[2]/-\[3]\--[4]).

% navrh d.s. 
% - seznamy jdou dobre odlisit, ale muzeme zavest tag pro mnoziny m/1, pro promenne p/1
%   (podobne jako u eval na prednasce)
%   - take m/1 a p/1 muzete zavest jako operatory

% ?- evalSet1(m([1])\-/m([2])/-\m([3])\--m([4]),V). % zapis s operatory

seznam([]).
seznam([_|_]).
vstup2Mn(X,X). % zjednodusene 
% vstup2Mn([],[]).
% vstup2Mn([X|Xs],Vs0):- vstup2Ms(Xs,Vs1), sjednoceni([X],Vs1,Vs0).

evalSet(S,S0) :- 
  seznam(S),	% kontrola druhu/tagu (A)
  vstup2Mn(S,S0). % uprava na korektni tvar, vystup je bez opakovani ...
%evalSet(S1/-\S2,V) :-
 evalSet(/-\(S1,S2),V) :-
  evalSet(S1, V1),
  evalSet(S2, V2),
  prunik(V1,V2,V). % prunik vyse, spravne verze.

% (A) podminka chrani i proti tomu, aby klauzule zpracovala slozene mnoz. vyrazy

tf3(V) :- evalSet([1,2,3]/-\[3,2,5,1]/-\[4,2,1],V).
% syntakticky OK az po zavedeni operatoru 

% Q: ve vstupnim vyrazu (mnozinovem, vyrokovem ...) pri pouziti operatoru muzou byt zavorky.
% pr: ?- evalSet( ([1,2,3]\-/[3,2,5,1]) /-\ [4,2,1],V).
% Q: Jak osetrime zavorky ve strukturalni rekurzi?
% Q: je vhodne/mozne/vyhodne/spravne pouzit nasledujici klauzuli?
% evalSet( (VF1), V) :-
%   evalSet( VF1, V).  
% A: ...

% ad koncova podminka:
% varianta: zpracovani multimnozin
% - A) reprezentace: [a,a,b,b,c,b]
%   - a) semanticke operace prunik, sjednoceni ... to musi _spravne_ zvladnout (<- nezvladnou)
%   - b) koncova podminka kontroluje jine vlastnosti
% - B) reprezentace: [a-2,b-3,c-1] ; tj. histogram/cetnosti
%   - potrebujeme jine operace pro novy datovy typ
% varianta: usporadane mnoziny
% - operace jsou rychlejsi, ale jine
% - trade-off: diky usporadanym vstupum mame rychlejsi operace, ale musime 
%	vytvaret i usporadane vystupy, :-) samozrejme
% - koncova podminka evalSet/2, tj. vstup2Mn/2 prevede lib. vstup na spravny interni tvar
%   - uzivatel netusi, ze to mate usporadane (a nema tusit), 
%   - a i kdyz mu to v dokumentaci napisete, zapomene nebo udela chybu ... 
% - slozitost neusporadaneho pruniku, ... je O(n^2), usporadaneho O(n), pro n-prvkove seznamy

% jine vyrazy a vyhodnocovace:
% vektorove, maticove, ...
% specialni aritmetika zbytkovych trid


%%%%%%%%%%%%%%
% eval vyrokove formule, z prednasky
% CV: tautologie Tau, lině, tj. pomoci splnitelnosti sat/1 z prednasky
%   <- z logiky: negace Tau je nesplnitelna
%   - nebo vhodnym pouzitim eval/1 s negaci non/1
%     ; zdarma mame hledani reseni, tj. ex. kvantifikator, nikoli univerzalni kv.

% pozn1: Tady se nehodi pristup, ze nesplnena formule neuspeje. Ale 
%	chceme vysledek explicitne jako true/false
% pozn2: rozlisovat domenove promenne (zde prvovyroky) a Prologovske promenne (pro formule);
% i v jinych domenach: (domenove) promenne v polynomech, ...

% cast eval/2, z prednasky
% predpokladam vhodnou definici operatorů (jejich kod je zakomentovany), zaveden jen operator and/2
:- op(210, xfy, [and]).  % def. operatoru and/2, doprava asoc.
% :- op(210, xfy, and ).	% nebo takto
eval(Ohod, VF1 and VF2, V):-	% diky operatoru syntakticky projde
  eval(Ohod, VF1, V1),
  eval(Ohod, VF2, V2),
  evalAnd(V1,V2,V).
% bez operatoru musime psat: 
% eval(Ohod, and(VF1,VF2), V) :- ...

eval(_Ohod,true,true).	% nezapomenout na konstanty
eval(_Ohod,false,false).
eval(Ohod, p(X), Val) :- member(X-Val,Ohod).	% promenne
eval(Ohod, non(VF1), V) :-
  eval(Ohod, VF1, V1),
  evalNon(V1,V).
eval(Ohod,or(VF1,VF2), V) :-
  eval(Ohod, non(non(VF1) and non(VF2)), V).

% vyhodnoceni: eval imp/2, ekv/2:

% eval imp/2:
% prevedeme na and, or, non, abychom nemuseli psat rekurzi a tabulku pro evalImp/3
% - anebo napiseme rekurzi a evalImp/3 pomoci prevedeni, viz dale
eval(Ohod, imp(VF1, VF2), V) :- 
  eval(Ohod, or(non(VF1),VF2), V).

% eval ekv/2:
% a) prevedeme, ale ...
/*    * /
eval(Ohod, ekv(VF1,VF2), V) :-
  eval(Ohod, or( and(VF1,VF2),and(non(VF1),non(VF2)) ), V).
/ *   */
%   - bez tabulky pro evalEkv/3, ale VF1 a VF2 se vyhodnocuji 2x -> to nechceme
% b) trade-off: rekurzi vyhodnotime explicitne (jednou), vysledky dosadime do formule
/*    */
eval(Ohod, ekv(VF1,VF2), V) :-
  (V1=true;V1=false),(V2=true;V2=false), % pro generovani ohodnoceni, jinak se zacykli
  eval(Ohod, VF1, V1),
  eval(Ohod, VF2, V2),
  eval(Ohod, or( and(V1,V2),and(non(V1),non(V2)) ), V). % pouzivame vysledky
/*   */
% pozn: v  a) se podformule sdileji -> pametova narocnost vzroste o nove vytvorenou cast
%   - az vyhodnocovani trva dele, protoze prochazi formule opakovane
%   - dalsi upravy VF bez ekv/2 (napr. prevod do CNF) ji typicky opakovane skopiruji 
%     -> vysledek je reprezentovan jako term (s opakovanim), potrebna pamet se zvetsi

% vyhodnoceni spojek (jen potrebnych: non, and)
evalNon(true,false).
evalNon(false,true).
evalAnd(true,true,true).
evalAnd(true,false,false).  
  % varianta: evalAnd(_,false,false). -> evalAnd/3 se splni opakovane, pro (false,false,V)
evalAnd(false,_,   false).


%%%%%%%%%
% dalsi ulohy (z minulych let)
% - obecne: transformace vyrokovych formuli
% cv: pozbirani promennych z VF
%   - dve moznosti
% cv: odstraneni imp a ekv z VF (mezikrok k CNF/DNF)
% cv: propagace non/1 dolu k literalum ; PRISTE
%       - hint: analyza dvou urovni struktury
% cv: prevod na DNF, na CNF: z NNF (negacni NF)
% pozn: nemate "zdarma" vypousteni nesplnitelnych a splnenych klauzuli
% - dalsi: ...
% cv: vse v jednom

/*
% neuplne struktury:
  - vhodnejsi a mene nebezpecny zpusob pouziti neuplnych datovych struktur 
    v kontextu vyhodnocovani eval/3 je, fixovat tvar struktury a jmena promennych a 
    nechat volne promenne pro hledane hodnoty
    - obecnejsi tvar je nechat ohodnoceni volnou promennou. Pak hledani promenne 
	v ohodnoceni (zde member) musi byt tomu prizpusobeny
  - tvar tabulky: [a-Va, b-Vb]
    - potrebujeme pozbirat promenne z VF, 
    - vytvorit ohodnoceni (pomoci map/3) s volnymi hodnotami
    - volat eval/3
  - "jednoduche" programovani s omezenimi/constraint programming: 
    - nekolik vyskytu promenne ve VF musi zdilet stejnou hodnotu
    - urcita forma generuj a testuj (generujeme implicitne castecne stavy d.s.)
*/

tf4(V):- V=[a-_Va,b-_Vb],eval(V,non(p(a)) and p(b),true). 

tf5(V):- V=[a-_Va,b-_Vb],eval(V,non(p(a)) and p(b),false). 
% vysledky odpovidaji def. evalAnd/3: _Vb je neurcene (nezalezi na nem)



%%%%%%%%%%%%%%
% generovani ohodnoceni pro eval
% - idiom: generuj a testuj
% d.s.: ohodnoceni: [a-Va,b-Vb]
% - pomoci indexovaneho kart. soucinu, nebo variance s opakovanim
% ?- iKartN([a-[true,false],b-[true,false]], Ohod).  
%  - mody a typy: iKartN(+[x-[val]],-[x-val])
%    - a, b, x jsou jmena promennych
% - podobne pro jine NPU ulohy
%  - podobne: generovani moznych obarveni grafu
%  - ale: pametove narocne a pomale (NPU)
%  - odstepilo se 

% tf1(X) :- ... % cv5

%%%%%%%%%%%%%%%
% sat/splnitelnost
% moznosti:
% 1. vygenerujeme (uplne) ohodnoceni, formule vyhodnocujeme pri danem ohodnoceni
% 2. vygenerujeme ohodnoceni s volnymi promennymi, za ktere se dosazuje true/false
%    - ...
% (3. vygenerujeme seznam vsech ohodnoceni, a ty prochazime.)
%    - Ohodnoceni je mnoho, tj. je to typicky nepouzitelne (v Prologu; Haskell je jiny) 
%
% ad 1.: postup
% 1a. posbirame promenne z formule: [p,q,r]
% 1b. vygenerujeme konkretni hodnoty (pomoci variaci a opakovanim): [true,false,true]
%	a nasledne konkretni ohodnoceni: [p-true,q-false,r-true]
% 1c. vyhodnotime, a pripadne backtrackujeme
%
% ad 2.:
% 2a. stejne jako 1a
% 2b. vygenerujeme "skelet" ohodnoceni: [p-VP,q-VQ,r-VR]
% 2c. pustime vyhodnocovani, musi pocitat s volnymi promennymi pro hodnoty
% - vydana ohodnoceni se muzou prekryvat, pripadne opakovat;
% - a muzou byt neuplne


%%%%%%%%%%%%%%%
% Poznamka: eval a tok dat
%   - priklad v klauzuli eval/3 pro ekv
% - pokud chceme pro predikat p/2 tok dat p(+,-) i p(-,+),
%	pritom p/2 potrebujeme napsat ruzne pro ruzne toky dat,
%	tak muzeme vyuzit vestavene testovani navazani argumentu
%   - nize popsane =.. a functor jsou (vestaveny) priklad 
% p(X,Y) :- nonvar(X), pPlusMinus(X,Y).	 % p/2 jednim smerem
% p(X,Y) :- nonvar(Y), pMinusPlus(X,Y).  % p/2 druhym smerem
%
% Poznamka:
% - jmena pro argumenty stavu (i jine):
%   - s nulou (Acc0) je vystupni, od zacatku se cisluje prubezne od 1
% p(+D,+Acc1,-Acc0) :- 
%   faze1(+D,+Acc1,-Acc2), 
%   faze2(+D,+Acc2,-Acc3), 
%   faze3(+D,+Acc3,-Acc0).

%%%%%%%%%%%%% 
% genericke zpracovani termu: univ/3 =.., arg/3, functor/3
% f(a,g(b),4) =.. [f,a,g(b),4]	 % rozebere 1 uroven slozeneho termu
% ?- arg(2,f(a,g(b),x),V).	 % V=g(b) , args od 1
% ?- functor(f(a,g(b),x),V,N ).  % V=f, N=3 ; mody (+,-,-), (-,+,+)
% ?- functor(Term,f,3).		 % Term = f(_1,_2,_3)
%
% Univ (=..) se hodi, pokud chceme zpracovat term genericky, bez ohledu na funktory.
% To je malo casty pripad, protoze ruzne funktory zavadime prave proto,
% ze maji ruznou semantiku, kterou chceme vyuzit.
%
% Priklad: z vyrokove formule chceme posbirat promenne
% promVF(+VF,-Vars)

% 1.varianta: pro kazdy funktor samostatna klauzule
promVF1(VF1 and VF2, Prom0) :-
  promVF1(VF1,Prom1),
  promVF1(VF2,Prom2),
  sjednoceni(Prom1,Prom2,Prom0).

% 2.var: pro vsechny funktory arity 2 spolecna kl.
promVF2(VF,[]) :- VF=true; VF = false.	% konstanty
promVF2(p(X),[X]):- !. 	% promenna
promVF2(VF, Prom0) :-
  VF=..[_Op,VF1,VF2],	% univ
  promVF1(VF1,Prom1),
  promVF1(VF2,Prom2),
  sjednoceni(Prom1,Prom2,Prom0).

% 3.var: pro vsechny funktory 1 kl., nutno restrukturovat
promVF(VF,[]) :- VF=true; VF = false.	% konstanty
promVF(p(X),[X]):-!. 	% promenna
promVF(VF, Prom0) :-	% zpracovava 1 term
  VF=..[_Op|VFs],	% univ
  promVFs(VFs,Prom0).	% zpracovava seznam termu
promVFs([],[]).
promVFs([VF|VFs],Prom0) :-
  promVF(VF,Prom1),
  promVFs(VFs,Prom2),
  sjednoceni(Prom1,Prom2,Prom0).



%%%%%%%%%%%%%%%%
% na rozmysleni: heapsort, nestihli jsme

% DCv: na dalsi roky, ne 2017:
% - 1) rozdil/3 (neusporadanych) histogramu, vcetne vypusteni x-0
% - 2) a symetricky rozdil, vhodnym pouzitim 1)


%%%%%%%%%%%%%%%%%%%%
% souhrn: co jste si vyzkouseli (nebo meli zvladnout):
% - rez, negaci, if->then;else
%   - deklarativne spravne klauzule, spravnost vuci backtrakingu
% - idiom: interpret
% - operatory: deklarace, pouziti
% - zpracovani termovych (tj. stromovych) struktur
% - ...

%%%%%%%%%%%%%%%
% setof, bagof,  - priklad, jsou v cv6

%%%%%%%%%%%%%%%%%
% zbylo z cv5

% generuj a testuj
% rozdilove seznamy na vystupu (quicksort)
% - na vstupu "ukusovani" vstupu (heapsort)

%%%%%%%%%%%
% jednoduche trideni, je na prednasce TD
% insertSort/2
% selectSort/2

%%%%%%%%%%%%%%%%%%%%%%%%%%
% heapsort (s binarni haldou)
% - postav tvar heapu, zhalduj, vybirej
%   - vyuziva rozdel/3
%   - stavba: prvek pro vrchol utrhnu hned
% - stavba: doleva doprava
% - hned stavet haldu (rozdel a panuj)
%   - minimum do korene a zbytek rozdelit
%   - stavba v O(n log n)
%   - klasika je postavit 2 subhaldy a potom 1 prvek vlozit
% - kapitansky krok: hloubka je porad logaritmicka
%   - (ani) pri vybirani nemusim udrzovat vyvazenou haldu
%     - posledni halda je neuplna 
%   - vybirani v O(n log n)

%%%%%%%
% compare/3:
% - idiom: vysledky jako data
% podobne: v Prologu pouzivane uspeje/neuspeje jsme v eval/3 
%   nahradili explicitnim true/false (a eval/3 vzdy uspeje)
% podobne: vysledky misto backtrackingu vracime jako seznam reseni


%%%%%%%%%%%%%%%%%%%%%%%%


/*  * /
/ *
*/


%%%%%%%%%%%%%%%%%%%%
% souhrn: co jste si vyzkouseli:
% -


%%%%%%%%%%%%%%%%%%%%%%%%%%%
% runtime
check1(Tested,=,Pattern) :- 
  Tested = Pattern -> write(passed),nl
                   ;  write(error),nl, 
		      write(value__(Tested)),nl, 
		      write(expected(Pattern)),nl.

%----------------

% k.
