% cv. 3 ; na 8.3.2017 ; Jan Hric
% v. 1.4.1	26.3.2018

% Obsah:
% seznamy
% debug: otoc a otoc s akumulatorem 
% prefix/2, sufix/2, 
% prefixy/2, sufixy/2
% concat/2 ...
% ...
% faktor/2 : spojitý podseznam 


% unifikace seznamu, priklady
% opakovani
tc1([X,Y]) :- 
    [X|Y]   = [a,b,c], write([X,Y]),nl
  ; [X,Y|_] = [a,b,c], write([X,Y]),nl
  ; [_,X|Y] = [a,b,c], write([X,Y]),nl
  ; [X,Y]   = [a,b],   write([X,Y]),nl
  ; true.
% volat jako tc1([X,Y]).

tc2([X,Y]):-
    [X,Y] = [a,b,c].

tc3(Val):-
  display(1-2+3*4=a/_X),nl,
  display(klic-Val).

tc4(_):-
  display([1,a,_X]).


% kdyz zapomenete napsat spravnou podminku do hlavy, lze unifikovat dodatecne
prazdnySeznam(Xs) :- Xs = [].

% neprazdnySeznam(+Xs) :- splni se, prave kdyz Xs je neprazdny
neprazdnySeznam(__). % Cviceni

% Jablicka nebo hrusky
% vic vystupu v jedne klauzuli; napriklad po drahych testech; taky za if-then-else
jnh(V) :-  testNaJablicka, V = jablicka
         ; testNaHrusky,   V = hrusky .

testNaJablicka.
testNaHrusky.

% pro ruzne ucely ruzne varianty predikatù: (z prednasky)
% a) vypust1(?X,+Xs,-Vs) : vypusti 1 prvek X z Xs, zbyle jsou ve Vs, backtrakuje
  % ?X muze znamena +X nebo -X, tj. X je nebo neni zadane
  % (castecny) invariant: Vs je o jedna kratsi
% b) vypustPrvni(...)    : vypusti prvni vyskyt X
  % invariant: Vs je o jedna kratsi
% c) vypustVsechny(X,Xs,Vs) : vypusti vsechny vyskyty
% pro b) a c), chovani , kdyz se nenajde: selze nebo uspeje
% Past: Pokud chceme vzdy uspet a pritom prvek pouze vypustit, pokud tam je, tak
%  a) nedokazeme vydat kompaktne (prostrednictvim volne promenne) pouze ostatni prvky
%    -> prvek pro vypousteni X musi byt zadan; souvisi s negaci: not/1 (bude na pøednášce)
%  b) potrebujeme si pamatovat (v dalsim argumentu) zda jsme prvek *skutecne* vypousteli
%    -> a na konci rekurze se podle toho zaridit


% - ruzne vzory rekurze
% - zpracovani celych struktur (najednou) ; 
%  - protipriklad: zpracovavat seznam jako indexovane pole

% append/3, opakovani, a projekce
% prefix, sufix, prefixy
append1([],Zs,Zs).
append1([X|Xs],Ys,[X|Zs]):-append1(Xs,Ys,Zs).

% append1(-,-,+) jako generator vysledkù
%   vyuzivame rekurzi podle 3. argumentu
td3([Vs1,Vs2]) :- append1(Vs1,Vs2,[a,b,c]).

% Q: append(+,-,-) : jak dopadne volani?
td3a([[a,b,c],Vs1,Vs2]) :- append1([a,b,c],Vs1,Vs2).

% prefix/2, prefix(+Xs,-Ps) :- Ps je prefix Xs.
% projekce
prefix(_Xs,_Ps) :- append1(_,_,_). % cviceni

% cviceni: prefix, pøímá rekurze 
%   napriklad kvuli efektivite

% sufix/2, sufix(+Xs,-Ss) :- Ss je sufix Xs.
sufix(_Xs,_Ps) :- append1(_,_,_).

% opakovani+trasovani:
% otoc1(+Xs,-Vs):- Vs je  otoceny Xs, kvadraticky
% rekurze podle 1. arg.
otoc1([],[]).
otoc1([X|Xs],Vs0) :- 
  otoc1(Xs,Vs1),
  append(Vs1,[X],Vs0). % 2.arg. je jednoprvkovy seznam (*)
	% (*) casta chyba: append(Vs1, X ,Vs0) ; 2. arg!, Hs: typova kontrola

% debug:
otoc1a([],[]) :- write([konec,[],[]]),nl.
otoc1a([X|Xs],Vs0) :-  write([do___,X,Xs,Vs0]),nl,  % na puvodni 2. arg nemame pristup
						% nelze je vypsat
                      otoc1a(Xs,Vs1),
                      write([mezi_,q,Xs,Vs1]),nl,
		      append(Vs1,[X],Vs0),
		      write([out__,X,Xs,Vs1,Vs0]),nl.
% Vs0, Vs1 jsou ukoncene seznamy

% otoc, linearni, s akumulatorem
% otoc2(+Xs,-Vs), otoc2x(+Xs,+Acc,-Vs)
otoc2(Xs,Vs) :- otoc2x(Xs,[],Vs).
otoc2x([],Vs,Vs). % rekurze podle 1. arg.
otoc2x([X|Xs],Acc,Vs) :- % Vs prenasime bez zmeny
  otoc2x(Xs,[X|Acc],Vs). % proc. je tail-rekurzivni

% debug
otoc2a(Xs,Vs) :- otoc2xa(Xs,[],Vs).
otoc2xa([],Vs,Vs) :- write([konec,[],Vs]),nl. % rekurze podle 1. arg.
otoc2xa([X|Xs],Acc,Vs) :- % Vs prenasime bez zmeny
  write([do___,X,Xs,Acc,Vs]),nl,
  otoc2xa(Xs,[X|Acc],Vs), % proc. je tail-rekurzivni
  write([ven__,X,Xs,Acc,Vs]),nl.

% pouceni: na akumulator mame pristup v rekurzi, data se zpracovavaji v jinem poradi
% vystupni promenna je stejna, mame (casto) tail-rekurzi

td1(Out):- otoc1a([a,b,c],Out).

td2(Out):- otoc2a([a,b,c],Out).

% korektnost vzhledem k backtrackingu:
% vydat prave spravna reseni, a skoncit
td4(Vs):- otoc1([a,b,c],Vs).	% mod otoc1(+,-): vyda reseni a konci
td4a(Vs):- otoc1(Vs,[a,b,c]). 	% mod otoc1(-,+): vyda reseni a cykli
% break: Ctrl-C

% nekonecne mnoho reseni, ktere nejdou vyjadrit kompaktne
td4b(X, Vs) :- member(X,Vs).
% - a skracovany vypis


% ! programatorsky idiom: seznam vysledku
% neuspech odpovida prazdnemu seznamu vysledkù (napriklad, i jine moznosti)

% sufixy/2, sufixy(+Xs,-Sss) :- Sss je seznam vsech sufixù Xs
sufixy([],__).		% cviceni
sufixy([_X|Xs],__) :- 
  true, 
  sufixy(Xs,_Sss1), 
  true.

td5(Vss):- sufixy([a,b,c],Vss).
% ! bez backtrackingu

% prefixy/2, prefixy(Xs,Pss) :- Pss je seznam vsech prefixù Xs
% prefixy(Xs,Pss) :- % cviceni/bonusove
  
% idea map(Pred,Ins,Outs) :- ...
% ... pro konkretni Pred/2
% zde: pridani (pevneho) prvniho prvku

% Q: ktere vektorove operace odpovidaji pouziti map?
% Q: jake abstraktni operaci odpovida soucet vektorù?

% mnoho vstupu:
% concat(+Xss,-Vs) :- Xss je seznam vnorenych seznamu, Vs je jejich pospojovani
concat([],[]).	
concat([_Xs|Xss],_Vs0) :-		% cviceni
    % doplnit preprocesing
  concat(Xss, _Vs1),
    % doplnit postprocesing
  true. % konec

% dve moznosti pro concat/2, jako obvykle (jednu jsem vam predpripravil)
% lisi se efektivitou

td6(Vs) :- concat([[1,2],[],[3],[4,5]],Vs).

% Q: muzem pouzit concat/2 pro rozdeleni: concat(-Xss,+Is)
%   Q: pripadne, kterou variantu?
%   Q: pripadne, jde to opatchovat a zachranit?

% dva vystupy:
% rozdeleni na prvni a druhou polovinu: z prednasky?
% idea: seznam v akumulatoru jsme pouzili jako pocitadlo delky 
% je dobre vedet, jak se rozdeli seznam liche delky
%  Q: proc?

% rozdel/3, rozdel(+Xs,-Sude,-Liche) :- rozdeli Xs na Sude a Liche prvky
% cviceni

% pouziti v mergesort/2, mergesort(Xs,Vs) :- Vs je usporadana verze Xs.
% predikaty pro porovnani: X < Y, X =< Y
% predpokladejte, ze mate merge/3, 
%  merge(+Xs1,+Xs2,-Vs) :- Vs je usporadane zmergovani Xs1 a Xs2
% pro pouziti v mergesortu chceme nechavat i opakujici se hodnoty.
mergesort(Xs,Vs):- 	% cviceni
  rozdel(Xs,_Xs1,_Xs2),
    % doplnit
  merge(_Vs1,_Vs2,Vs),
  true.

% ordered(Xs) :- test, zde prvky jsou v neklesajicim poradi.
ordered(__) :- true. % cviceni/bonus

% pro ladeni: 
% - deklarativni specifikace podminek (typicky castecnych, ale i uplnych)
%  - lepsi nez unit testy
% priklad: podminky pro merge/3
% Q: podminky na delku/mohutnost seznamù 
% Q: dalsi, az uplne podminky
% - vyuziva se mj. deklarativnosti, procedur bez sideefektù

% DC: trans/2, transpozice matice, predpokladame korektni zadani ;-)
% trans(+Mat, -Transp) 
  % Q: proc korektni zadani
% dve moznosti, ...


% dalsi: (rezerva)
% na prednasce: permutace, vypust
% idea/idiom: rekurze podle vystupu
%   - jiny priklad tehoz: selectSort/trideni vyberem

% kombinace (bez opakovani)
% interface: C(5,3), prvky explicitne - jako u permutaci
% a) komb1(3, [1,2,3,4,5], V) :- backtrackingem ; az budou cisla
% b) komb2(s(s(s(0))), [1,2,3,4,5], V) :- dtto
% c) komb3([1,2,3,4,5], [X1,X2,X3]) :- V = [X1,X2,X3], ...
% 	delka vystupu je urcena delkou seznamu
% c1) komb4/3, komb4([_,_,_],[1,2,3,4,5], Vs) :- 1.arg je citac, ze ktereho synchronne vybirame;
%       varianta na permutace
% pro a) a b) lze jednoduse generovat seznam vsech kombinaci
%  - ale je to pametove narocne, Prolog nema line vyhodnocovani

% Nektere NP-uplne problemy lze jednoduse _popsat_. 
%   Porad budou vypocetne tezke.
% Metoda generuj a testuj (pomoci backtrackingu).



%--------
% idea map

% otoc 2x + trasovani

% deleni na dva + bonus

% Pouziti v mergesortu

%----------------

% Bool se "vraci" jako uspech/neuspech ; pouzitelne v testech  

%----------
vypust(X,[X|Xs],Xs).
vypust(X,[Y|Ys],[Y|Zs]):-vypust(X,Ys,Zs).

vloz(X,Xs,Ys) :- vypust(X,Ys,Xs).

otocAk(Xs,Ys) :- otocAk(Xs,[],Ys).
otocAk([],A,A).
otocAk([X|Xs],A,Ys):-otocAk(Xs,[X|A],Ys).

k.
