%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Predicati di base per operare su liste
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% member(X,L): vero se X e' un elemento della lista L

  member(X,[X|_R]).
  member(X,[_Y|R]) :- 
      member(X,R).

% append(L1,L2,L3): vero se la lista L3 e' la concatenazione 
% delle liste L1 ed L2

  append([],L2,L2).
  append([X|R1],L2,[X|R3]) :-
      append(R1,L2,R3).

% sublist(P,S,N): vero se la lista P e' una sottolista della
% lista S, iniziante dall'elemento N

  sub_list(P,S,N) :-
      append(A,_P2,S),
      append(P1,P,A),
      length(P1,N).

% qsort(L1,L2): vero se L2 e' come la lista L1 ma ordinata 
% in senso crescente (utilizza l'algoritmo di ordinamento del
% "quick sort"

  qsort([],[]).
  qsort([H|T],S) :- 
      split(H,T,A,B),
      qsort(A,A1),qsort(B,B1),
      append(A1,[H|B1],S).
    
  split(H,[A|X],[A|Y],Z) :- A<H,!,split(H,X,Y,Z).
  split(H,[A|X],Y,[A|Z]) :- split(H,X,Y,Z).
  split(_,[],[],[]).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Goal d'esempio
%
% ?- member(b,[a,b,c]).
% yes
%
% ?- member(X,[a,b,c]).
% X = a;
% X = b;
% X = c;
% no
%
% ?- append([a,b],[c,d],L).
% L = [a,b,c,d]
%
% ?- append(L1,L2,[a,b,c]).
% L1 = [], L2 = [a,b,c]
% L1 = [a], L2 = [b,c];
% L1 = [a,b], L2 = [c];
% L1 = [a,b,c], L2 = [];
%
% ?- sub_list([b,c],[a,b,c,d,e],N).
% N = 1
%
% ?- qsort([3,1,6,2],R).
% R = [1,2,3,6]
