% lista(L) gdy L jest lista

% lista pusta to []
lista([]).

% lista z głową H i ogonem T to jest [H|T]

lista([_|L]) :- lista(L).


% len(L, K) gdy L ma długość K

len([], z).

len([_|L], s(K)) :- len(L, K).


% pierwszy(E,L) gdy E jest głową listy L


% Haskellu byłoby:
% pierwszy_haskell (h:_) = h
% f(x) = y  ----> relacja zawierająca pary (x, y)
% ale tu mamy odwróconą kolejność współrzędnych
% ----> relacja  zawierająca pary postaci (h, (h:_))

pierwszy(E, [E|_]).

% ogon(LA, LW) gdy lista LW jest ogonem listy LA

ogon([_|L], L).


% ostatni(E,L) gdy E jest ostatnim elementem listy L

%   / \
% x1 / \
%   x1 / \
%     x3 ...

ostatni(E, [E]).

%ostatni(E, L) :- ogon(L, L1), ostatni(E, L1).

% albo tez dobrze:
% ostatni(E, [_,X|L]) :- ostatni(E, [X|L]).

% tak tez jest dobrze, bo ostatni(E, []) nie odnosi zadnego sukcesu

% ostatni(E, [_|L]) :- ostatni(E, L).


% element(E, L) gdy E jest jednym z elementĂłw listy L

% pierwszy pomysł: element(E, L) :- pierwszy(E, L).

element(E, [E|_L]).

element(E, [_|L]) :- element(E, L).


% scal(L1, L2, L3) gdy L3 = concatenacja listy L1 z L2 (wbudowany append/3)

scal([], L2, L2).

scal([X|L1], L2, [X|L3]) :- scal(L1, L2, L3).

% haskelu byłoby tak:
% scal (h:l1) l2 =
%  let res = scal l1 l2 in
%    h:res


% intersect(Z1, Z2) wtw gdy zbiory (listy) Z1 i Z2 mają jakiś wspólny element

% mozna tak i nie jest zle, chociaz sa wielokrotne sukcesy
% intersect(Z1, Z2) :- element(E, Z1), element(E, Z2).

% poprawic by nie bylo wielokrotnych sukcesĂłw (z uzyciem sortowania)



% podziel(L, N, P) - kiedy N i P to podzial listy L na odpowiednio parzyste i nieparzyste pozycje (liczac od 0)

% np. ma być podziel([0,1,3,5,7], [1,5], [0,3,7]).

podziel([], [], []).

podziel([E], [], [E]).

podziel([E1, E2 | L], [E2|N], [E1|P]) :- podziel(L, N, P).


% podlista(P, L) gdy P jest spójną podlistą listy L (wliczając w to listę pustą i całość)

%pomysł: przez predykat bycia prefiksem

prefiks([], _).
prefiks([H|L1], [H|L2]) :- prefiks(L1, L2).

% albo:

% prefiks(P, L) :- scal(P, _, L).

podlista(P, L) :- prefiks(P, L).

podlista(P, [_|L]) :- podlista(P, L).


% podciag(P, L) gdy P jest dowolnym podciagiem listy L
% np. podciag([],        [1,2,3,4,5]).
% np. podciag([1,3,5],   [1,2,3,4,5]).
% np. podciag([2,4,5],   [1,2,3,4,5]).
% ...

podciag([], []).

podciag(P, [_|L]) :- podciag(P, L).

podciag([X|P], [X|L]) :- podciag(P, L).


/*
       L=[1,2,3]
       /   |    \
      /   P=[]   \
  L=[2,3]       L=[2,3]
  P=[1|P']      P=P
  /   |    \
 /  P'=[]   \
           L=[3]
           P'=P'
        /    |    \
           P'=[]


*/



% wypisz(L) == czytelne wypisanie elementów listy L, z zaznaczeniem jeśli lista pusta (np. elementy oddzielane przecinkami, po ostatnim elemencie kropka)

% np:
napisz_to(X) :- write('oto X:'), nl, write(X).


% chcielibyscmy by: wypisz([1,2,3]) ---> "[1, 2, 3]"


wypisz(L) :- write('['), wypisz_rest(L).

% wypisz_rest(L) - wypisuje listę L ale z pominięciem pierwszego nawiasu kwadratowego

wypisz_rest([]) :- write(']').

wypisz_rest([X]) :- write(X), write(']').

wypisz_rest([X1,X2|L]) :- write(X1), write(', '), wypisz_rest([X2|L]).

% equal(X, Y, P) gdy listy X i Y sa rowne natomiast P to pomocnicza kopia X

equal([], [], P) :- write('koncze z '), write(P), nl.

equal([X|L1], [X|L2], P) :- write('rekure z '), write(P), nl, equal(L1, L2, P).


% porownywanie wartosci arytmetycznych

mniejsze(X, Y) :- X =< Y.
wieksze(X, Y) :- X > Y.


% sortowanie przez wstawianie:

% insertionSort(Lista, Posortowana), gdy Posortowana to posortowana lista Lista
% insert(Lista, Elem, NowaLista) gdy NowaLista powstaje z Lista przez wstawienie elementu Elem na odpowiednie miejsce

insertionSort([], []).
insertionSort([X|L], R2) :-
	insertionSort(L, R1),
	insert(R1, X, R2).

insert([], E, [E]).
insert([X|L], E, [E,X|L]) :- E =< X.
insert([X|L], E, [X|R]) :- E > X, insert(L, E, R).


% srodek(E, L) gdy E jest srodkowym elementem listy nieparzystej dlugosci

% srodek(E, L1, L2) - zjada z listy L1 po jednym elemencie i L2 po dwa elementy i zwraca to co trzeba :)

srodek(E, L) :- srodek(E, L, L).

srodek(X, [X|_], [_]).

srodek(X, [_|L1], [_,_|L2]) :- srodek(X, L1, L2).