% sum(X,Y,Z) = "Z e' la somma dei naturali X e Y".

sum(X,0,X).
sum(X,s(Y),s(Z1)):- sum(X,Y,Z1).

% prod(X,Y,Z) = "Z e' il prodotto dei naturali X e Y".

prod(_,0,0).
prod(X,s(Y),Z):- prod(X,Y,Z1), sum(Z1,X,Z).

% fib(X,N) = "X e' l'n-esimo elemento della succcessione di Fibonacci".

fib(0,s(0)).
fib(s(0),s(0)).
fib(s(s(X)),Z):- fib(s(X),Z1), fib(X,Z2), sum(Z1,Z2,Z).

% mcd(X,Y,Z) = "Z e' il massimo comun divisore dei naturali X e Y".

mcd(X,X,X).
mcd(X,Y,Z):- X>Y, X1 is X-Y, mcd(X1,Y,Z).
mcd(X,Y,Z):- X<Y, Y1 is Y-X, mcd(X,Y1,Z).


% append(X,Y,Z)="Z e' la concatenazione delle liste X e Y".

append([],X,X).
append([X|Xs],Y,[X|Zs]):- append(Xs,Y,Zs).

% member(X,L) = "l'elemento X appartiene alla lista L?".

member(X,[X|_]).
member(X,[_|Ys]):- member(X,Ys).

% reverse(X,Y) = "Y e' il ribaltamento della lista X".

reverse([],[]).
reverse([X|Xs],Z):- reverse(Xs,Zs), append(Zs,[X],Z). 

% length(L,N) = "N e' la lunghezza della lista L (versione con aritmetica Prolog)".

length([],0).
length([_|Xs],Z):- length(Xs,Zs), Z is Zs+1.

% length1(L,N) = "N e' la lunghezza della lista L".

length1([],0).
length1([_|Xs],s(Zs)):- length1(Xs,Zs).


% select(X,L1,L2) = "seleziona la prima occorrenza dell'elemento X nella lista L1 e restituisce in
%                    L2 la lista priva di tale elemento."
 
select(X,[X|Xs],Xs).
select(X,[Y|Xs],[Y|Zs]):-select(X,Xs,Zs).


% perm(X,Y) = "Y e' una permutazione della lista X".

perm([],[]).
perm(Xs,[X|Zs]) :- select(X,Xs,Ys), perm(Ys,Zs). 


split([],[],[]).
split([X],[X],[]).
split([X,Y|Z],[X|Z1],[Y|Z2]):- split(Z,Z1,Z2).

% merge(X,Y,Z) = "Z e' la lista ordinata ottenuta dalla fusione delle liste ordinate  Y e Z".

merge(X,[],X).
merge([],X,X).
merge([X|Xs],[Y|Ys],[X|Z]):- X=<Y,merge(Xs,[Y|Ys],Z).
merge([X|Xs],[Y|Ys],[Y|Z]):- X>Y,merge([X|Xs],Ys,Z).

% ms(X,Y) = "mergesort(X,Y)".

ms([],[]).
ms([X],[X]).
ms([X,Y|Xs],Z):- split([X,Y|Xs],X1,X2), ms(X1,O1),ms(X2,O2),merge(O1,O2,Z).

% ordered(L)="La lista L e' ordinata?".

ordered([]).
ordered([_]).
ordered([X,Y|Z]):- X=<Y, ordered([Y|Z]).

% naivesort(X,Y) = "ordinamento naive della lista X (metodologia "generate&test")".

naivesort(X,Y):- perm(X,Y), ordered(Y).

% prefix(L1,L2) = " L1 e' una lista prefisso della lista L2".

prefix(L1,L2):- append(L1,_,L2).

% suffix(L1,L2) = " L1 e' una lista suffisso della lista L2".

suffix(L1,L2):- append(_,L1,L2).

% sublist(X,Y) = "X e' una sottolista della lista Y".

sublist(X,Y):- suffix(Z,Y), prefix(X,Z).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% alberi binari

% struttura dati

% nil e' l'albero binario vuoto
% per ogni termine t, albero binario l, albero binario r,  
% tree(t,l,r) e' un albero binario.

% nodes(T,N) = "N e' il numero di nodi nell'albero binario T"

nodes(nil,0).
nodes(tree(_,L,R),Z):-nodes(L,N1),nodes(R,N2), Z is (N2+N1+1).
                         
% balanced(T) = "T e' un albero binario bilanciato?".

balanced(nil).
balanced(tree(_,L,R)):-  nodes(L,N1), nodes(R,N2),
                         abs(N1-N2)=<1, balanced(L), balanced(R).

% inorder(T,L) = "L e' la lista contenente  i nodi dell'albero binario T nell'ordine imposto
%                 dalla visita simmetrica di T".
                          
inorder(nil,[]).
inorder(tree(X,L,R),Z):- inorder(L,Z1), 
                         append(Z1,[X],Z2), 
                         inorder(R,Z3),
                         append(Z2,Z3,Z).                         

% alberi binari di ricerca

% Definizione:
% nil e' un alberi binario di ricerca
% tree(t,l,r) e' un albero binario di ricerca se l e r sono alberi binari di ricerca e  
% root(l) =< t < root(r).

% insert(X,T1,T2) = "T2 e' l'albero binario di ricerca risultato dell'inserimento dell'elemento X
%                    nell'albero binario di ricerca T1".

insert(X,nil,tree(X,nil,nil)).
insert(X,tree(Y,L,R),tree(Y,Z,R)):-X=<Y,insert(X,L,Z).
insert(X,tree(Y,L,R),tree(Y,L,Z)):-X>Y,insert(X,R,Z).


% search(X,T) = "l'elemento X e' presente nell'albero binario di ricerca T?".

search(X,tree(X,_,_)).
search(X,tree(Y,L,_)):- X<Y, search(X,L).
search(X,tree(Y,_,R)):- X>Y, search(X,R).

% build(L,T) = " T e' un albero binario di ricerca i cui nodi sono gli elementi della lista L".

build([],nil).
build([X|Y],T):- build(Y,T1), insert(X,T1,T).