LISTE



/* Appartenenza di un elemento ad una lista */


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



/* ALTERNATIVA */

member1(X,[X|_]):-!.
member1(X,[_|C]):-member1(X,C).




/* Lunghezza di una lista  */


lunghezza([],0).
lunghezza([T|C],N):-lunghezza(C,M),
		    N is M+1.




/* Somma degli elementi positivi di una lista */


somma_pos([],0).
somma_pos([T|C],S):-somma_pos(C,Q),
		    comp1(T,Q,S).
comp1(T,Q,S):- T>0,
	       S is Q+T.
comp1(T,Q,S):- T=<0,
	       S is Q.

/* oppure: comp1(T,Q,Q):-T=<0. */




/* Eliminazione Elementi Ripetuti di una lista */


elimina_rip([],[]).
elimina_rip([T|C],L):- elimina_rip(C,L1),
		       comp3(T,L1,L).

comp3(T,L1,[T|L1]):- not member(T,L1).
comp3(T,L1,L1):- member(T,L1).




/* ALTERNATIVA: METODO PROCEDURALE */
  


set(L,E):-set1(L,E,[]).

set1([],E,E).
set1([T|C],E,Q):-member(T,Q),
		 set1(C,E,Q).
set1([T|C],E,Q):-not member(T,Q),
		 set1(C,E,[T|Q]).




/* UNIONE DI DUE INSIEMI (con il member):
union(insieme1,insieme2,insieme_unione) */


union(A,[],A). /* passo base */
union([],A,A):-!. /* caso particolare */           
union(A,[T|C],Q):-union(A,C,K),
		  u(T,K,Q).
u(T,K,[T|K]):-not member(T,K).
u(T,K,K):-member(T,K).



/* Unione di due insiemi: METODO PROCEDURALE */


unione(E1,E2,L):- uni(E1,E2,L,E1).

uni(E1,[],L,L).     
uni([],E2,E2,_):-!.    /* caso particolare */
uni(E1,[T|C],L,P):- member(T,P),
		    uni(E1,C,L,P).
uni(E1,[T|C],L,P):-not member(T,P),
		   uni(E1,C,L,[T|P]).



/* ANCOR MEGLIO: 
   il primo argomento di uni e' inutile, quindi si puo' togliere, 
   di conseguenza bisogna spostare il caso particolare */


unione2([],E2,E2):-!. /* caso particolare */
unione2(E1,E2,L):- uni2(E2,L,E1).
uni2([],L,L). 
uni2([T|C],L,P):- member(T,P),
		  uni2(C,L,P).
uni2([T|C],L,P):-not member(T,P),
		 uni2(C,L,[T|P]).




/* LA PRIMA LISTA E' PREFISSO DELLA SECONDA? */


prefix([],_).
prefix([T|C],[T|K]):-prefix(C,K).




/* LA PRIMA LISTA E' SUFFISSO DELLA SECONDA? */
           


suffix(A,A).
suffix(L,[T|C]):-suffix(L,C).



/* INTERSEZIONE DI DUE INSIEMI */


intersezione(A,[],[]). /* passo base */
intersezione([],A,[]). /* caso particolare */          
intersezione([T|C],A,Q):-intersezione(C,A,K),
			 i(T,A,K,Q).
i(T,A,K,K):-not member(T,A).
i(T,A,K,[T|K]):-member(T,A).




/* Intersezione di due insiemi: METODO PROCEDURALE */


intersezione2(E1,[],[]):-!. /* caso particolare */
intersezione2(E1,E2,L):- inters(E1,E2,L,[]).

inters([],_,L,L).  
inters([T|C],E2,L,P):- member(T,E2),
		       inters(C,E2,L,[T|P]).
inters([T|C],E2,L,P):- not member(T,E2),
		       inters(C,E2,L,P).




/* Differenza di due insiemi */


differenza(X,[],X):-!.
differenza(X,Y,Z):-diff(X,Y,Z,[]).

diff([],Y,Z,Z).
diff([T|C],Y,Z,P):- not member(T,Y),
		    diff(C,Y,Z,[T|P]).
diff([T|C],Y,Z,P):- member(T,Y),
		    diff(C,Y,Z,P).




/* ORDINAMENTI */



/* Date due liste ordinate (istanziate) produce una
   lista ordinata che contiene gli elementi di
   entrambe. */


merge([],[],[]):-!.    /* serve per evitare il risoddisfacimento
                          in caso di due liste uguali  */

merge([],Lista2,Lista2).
vv
merge(Lista1,[],Lista1).

merge([T1|C1],[T2|C2],[T1,T2|C]):- T1=T2,
				   merge(C1,C2,C).

merge([T1|C1],[T2|C2],[T1|C]):- T1T2,
				merge([T1|C1],C2,C).




/* ORDINAMENTO DI UNA LISTA
   (il termine sort esiste gia' di sistema) */


/* insort funziona per liste di numeri */
insort([],[]).
insort([T|C],L):-insort(C,K),
		 insert_ord(T,K,L).
insert_ord(A,[],[A]).
insert_ord(A,[T|C],[A,T|C]):-A=T,
			   insert_ord(A,C,Q).



/* ALTERNATIVA: METODO PROCEDURALE */


insort_p(L,S):-ins_p(L,S,[]).

sort_p([],P,P). /* criterio d'arresto */
sort_p([T|C],S,P):-insert_ord(T,P,Q),
		   sort_p(C,S,Q).
 


/* Metodo QUICK SORT  per ordinare una lista */

/* prima versione: con append */

quick_sort([],[]).
quick_sort([T|C],S):-split(T,C,L1,L2),
		     quick_sort(L1,S1),
		     quick_sort(L2,S2),
		     append(S1,[T|S2],S).

split(_,[],[],[]).
split(T,[X|C],[X|Y],Z):- X=T,
			 split(T,C,Y,Z).



/* seconda versione: senza append */


q_sort(L,S):-quick(L,[],S).

quick([],R,R).
quick([T|C],R,S):-split(T,C,L1,L2),
		  quick(L2,R,S2),
		  quick(L1,[T|S2],S).




/* PERMUTAZIONE qualsiasi di una lista  */


permutazione([],[]).
permutazione([T|C],L):- permutazione(C,K),
			insert(T,K,L).
insert(T,L,[T|L]).
insert(T,[A|B],[A|K]):- insert(T,B,K).



/* ALTERNATIVA: METODO PROCEDURALE */


perm(L,S):-perm2(L,S,[]).

perm2([],S,S).
perm2([T|C],S,Q):-insert(T,Q,Q1),
		  perm2(C,S,Q1).




/* APPEND
(alias giustapposizione di due liste) */



/* il minimo indispensabile */


append([],L,L).
append([T|C],L,[T|K]):-append(C,L,K).


/* OSSERVAZIONE: alla domanda ?-append(X,Y,[1,2,3]). 
		 risponde dando tutti i modi possibili 
                 di creare [1,2,3] giustapponendo due liste  */



/* ALTERNATIVA_1: aggiunta del caso particolare */


append1([],L,L).            /* passo base */                       
append1(L,[],L).            /* caso particolare */
append1([T|C],L,[T|K]):-not eq(L,[]), 
			append1(C,L,K).

/* OSSEVAZIONE: si ottengono risposte diverse da quelle di append solo
		alle domande di tipo  ?-append1(X,Y,[1,2,3]).
				      ?-append2(X,Y.[1,2,3]).  

		e a quelle di tipo    ?-append1(X,Y,Z).
                                      ?-append2(X,Y,Z).       */



/* ALTERNATIVA_2: caso particolare con ! e senza il not eq */


append2([],L,L).           /* passo base */
append2(L,[],L):-!.        /* caso particolare */
append2([T|C],L2,[T|K]):-append(C,L2,K).





/* INVERSIONE DEGLI ELEMENTI DI UNA LISTA */

/* reverse_append inverte gli elementi di una lista utilizzando
   il predicato append */

reverse_append([],[]).
reverse_append([T|C],Q):-reverse_append(C,K),
			 append(K,[T],Q).



/* reverse senza append */


reverse(L,Q):- rev(L,Q,[]).
rev([],Q,Q).
rev([T|C],Q,K):-rev(C,Q,[T|K]).




/* ELENCO DI FATTI UTILI */

 
p(a,andrea).
p(a,adriano).
p(a,antonio).
p(b,birillo).
p(b,boo).
p(c,cosimo).
p(e,elena).
p(g,giacomo).
p(g,gino).
p(g,giusva).
p(g,gianluca).
p(o,osvaldo).
p(o,ovidio).
p(s,silvia).
p(v,vittorio).




/* il predicato gl simula il parassita findall */


gl(X,p(W,X),L):-p(W,X),
		asserta(fatto(X)),
		fail.
gl(X,p(W,X),L):-assertz(fatto(9999)),
		retract(fatto(X)),
		costruz_lista(X,L,[]),
		!.
costruz_lista(9999,L,L):-!.
costruz_lista(X,L,P):-retract(fatto(A)),
		      costruz_lista(A,L,[X|P]).





/* VISITANDO GLI ALBERI... */



/* ELENCO ARCHI DI UN ALBERO */


arco(a,b).
arco(a,c).
arco(a,d).
arco(c,e).
arco(c,f).
arco(d,g).
arco(e,h).
arco(e,i).
arco(e,l).





/* VISITA depth-first ( PREVISITA IN PROFONDITA' ) */


visita_df(X):- azione(X),
	       arco(X,Y),
	       visita_df(Y).

azione(X):-tab(3),
	   write(X).



/*  OPPURE:  */


df:-radice(X),
    visita_df(X).

radice(X):-arco(X,_),
	   not arco(_,X),!.


/* tab(num)  provoca la scrittura di tanti caratteri blank
             quanti son indicati da num  */



/* ALTERNATIVA */


previsita(X):-tab(3),
	      write(X),
	      findall(F,arco(X,F),L),
	      prev(L).

prev([]).
prev([T|C]):-previsita(T),
	     prev(C).



/* ALTERNATIVA */


vis_p(X):-vp([X]).

vp([]).

vp([T|C]):-write(T),
	   tab(3),
	   findall(F,arco(X,F),L),
	   vp(L),
	   vp(C).



 
/* POSTVISITA */


pt:-radice(X),
    postvisita(X).

postvisita(X):-findall(Y,arco(X,Y),L),
	       post(L), 
	       azione(X).
post([]).
post([T|C]):-postvisita(T),
	     post(C).




/* VISITA breadth-first ( VISITA IN LARGHEZZA ) */


vl:-radice(X),
    visita_bf(X).

visita_bf(X):-vis_bf([X]).

vis_bf([]).

vis_bf([T|C]):-tab(2),write(T),
	       findall(F,arco(T,F),L),
	       append(C,L,K),
	       vis_bf(K).




/*  INVISITA  */


iv(I):-radice(X),
       invisita(X,I).

invisita(X,I):-findall(K,arco(X,K),L),
	       inv1(L,I,I,L2),                      
	       azione(X),
	       inv2(L2,I).

inv1([],J,I,[]):-!.
inv1(L,0,I,L).
inv1([T|C],J,I,L2):-invisita(T,I), 
		    A is J-1,
		    inv1(C,A,I,L2).
	      
inv2([],I).
inv2([T|C],I):-invisita(T,I),
	       inv2(C,I). 




/*  *********************************  */



arco(a,b,1).
arco(a,c,4).
arco(a,d,1).
arco(c,e,8).
arco(c,f,2).
arco(d,g,1).
arco(e,h,3).
arco(e,i,2).
arco(e,l,7).

nodo(a,3).
nodo(b,1).
nodo(c,6).
nodo(d,7).
nodo(e,2).
nodo(f,1).
nodo(g,6).
nodo(h,2).
nodo(i,5).
nodo(l,8).




/* cammino dal nodo X al nodo Y di complessita' n */



c1(X,Y):-camm1(X,Y,L,[X]),
         tab(3),
         write(L).

camm1(X,X,L,L).
camm1(X,Y,L,P):-arco(X,W,_),
                camm1(W,Y,L,[W|P]).




/* cammino dal nodo X al nodo Y migliore 
   di complessita' log(n) */


c2(X,Y):-camm2(X,Y,L,[Y]),
         tab(3),
         write(L).

camm2(X,X,L,L).
camm2(X,Y,L,P):-arco(A,Y,_),
                camm2(X,A,L,[A|P]).


/* radice dell'albero  */

radice(X):-arco(X,_,_),
           not arco(_,X,_),
           !.


/* foglie dell'albero */

foglia(X):-arco(_,X,_),
           not arco(X,_,_).

foglie(L):-findall(X,foglia(X),L).



/* PROGRAMMA:   ( Prima Versione )
   via1(X,Y).   stampa le foglie dell'albero tali che
   il peso totale del cammino dalla radice a quelle 
   foglie e' compreso tra i numeri X e Y dati 
   dall'utente */


via1(X,Y):-foglie(L),
           esercizio(L,X,Y).

esercizio([],_,_).

esercizio([T|C],X,Y):-radice(A),
                      contapeso(A,T,Peso),
                      azione(T,Peso,X,Y),
                      esercizio(C,X,Y).
contapeso(A,A,0).

contapeso(A,B,Peso):-arco(D,B,P),
                     contapeso(A,D,P2),
                     Peso is P2+P.

azione(A,Pr,X,Y):-compreso(Pr,X,Y),
                  tab(3),
   	          write(A).
                  

azione(A,Pr,X,Y):-not compreso(Pr,X,Y).
        
compreso(Pr,X,Y):-Pr >= X,
                  Pr =< Y.





/* PROGRAMMA:  ( Seconda Versione )
   esercizio1(L,X,Y). stampa le foglie dell'albero tali 
   che il peso totale del cammino dalla radice a quelle
   foglie e' compreso tra i numeri X e Y dati 
   dall'utente */


esercizio(L,X,Y):- radice(A),
                   foglie(F),
	           cerca(A,F,X,Y,[],L).


cerca(_,[],_,_,Q,Q).

cerca(A,[T|C],X,Y,Q,L):- cammino(A,T,Camm,Costo),
			 confronto(Costo,X,Y),
			 cerca(A,C,X,Y,[T|Q],L).

cerca(A,[T|C],X,Y,Q,L):- cammino(A,T,Camm,Costo),
			 not confronto(Costo,X,Y),
			 cerca(A,C,X,Y,Q,L).


confronto(A,B,C):- A>=B,
		   A=<C.
			 


cammino(A,B,L,Costo):- camm_es(A,B,[B],L,Costo).

camm_es(A,A,Q,Q,0).

camm_es(A,B,Q,L,Costo):- arco(D,B,C1),
		         camm_es(A,D,[D|Q],L,C2),
		         Costo is C1+C2.





/* PROGRAMMA: 
   via2(X,Y). stampa la prima foglia tale che il
   totale del cammino dalla radice a quella foglia 
   e' compreso tra i numeri X e Y dati dall'utente */

via2(X,Y):-foglie(L),
           esercizio2(L,1,Test,X,Y).
          

esercizio2([T|C],1,Test,X,Y):-radice(A),
                              contapeso(A,T,Peso),
                              azione2(T,Peso,X,Y,Test),
                              esercizio2(C,Test,Test2,X,Y).

esercizio2([],_,_,_,_):-write('Non è stata trovata alcuna foglia'),
                        write(' soddisfacente la relazione.').

esercizio2(_,0,_,_,_). 

azione2(T,Peso,X,Y,Test):-compreso(Peso,X,Y),
                          write('La prima foglia che soddisfa la relazione è:'),
                          tab(1),
                          write(T),write('.'),
                          Test=0. 

azione2(T,P,X,Y,_):-not compreso(P,X,Y).
                     


/* PROGRAMMA:
   via3_4.  restituisce il cammino radice-foglia di
   costo minimo e quello di costo massimo */

via3_4:-radice(A),
      foglie(L),
      esercizio3(A,L).

esercizio3(A,[T|C]):-camm3(A,T,Peso,L,[T]),
                     mincamm3(A,C,Peso,L,Pmin,Lmin),
                     azione3(Lmin),
                     maxcamm3(A,C,Peso,L,Pmax,Lmax),
                     azione4(Lmax).

camm3(A,A,0,L,L).
camm3(A,T,Peso,L,K):-arco(B,T,P),
                     camm3(A,B,P1,L,[B|K]),
                     Peso is P1+P.

mincamm3(_,[],P,L,P,L).
mincamm3(A,[T|C],P1,L1,Pmin,Lmin):-camm3(A,T,P2,L2,[T]),
                                   confronto3(P1,L1,P2,L2,P3,L3),
				   mincamm3(A,C,P3,L3,Pmin,Lmin).

maxcamm3(_,[],P,L,P,L).
maxcamm3(A,[T|C],P1,L1,Pmax,Lmax):-camm3(A,T,P2,L2,[T]),
                                   confronto4(P1,L1,P2,L2,P4,L4),
                                   maxcamm3(A,C,P4,L4,Pmax,Lmax).


confronto3(P1,L1,P2,L2,P1,L1):-P1 =< P2.                                                   
confronto3(P1,L1,P2,L2,P2,L2):-P1 > P2.

confronto4(P1,L1,P2,L2,P1,L1):-P1 >= P2.
confronto4(P1,L1,P2,L2,P2,L2):-P1 < P2.
                                                
azione3(L):-write('Il cammino radice-foglia di peso minimo è:'),
            tab(1),
            write(L),
            nl.

azione4(L):-write('Il cammino radice-foglia di peso massimo è:'),
            tab(1),
            write(L).



/* cercanodi(L). stampa la lista dei nodi di un grafo
                 ordinato ciclico */

nodi:-radice(A),
      cercanodi(L),
      write([A|L]).

cercanodi(L):-findall(B,arco(A,B,_),K),
              eliminarip(K,L,[]).

eliminarip([],L,L).
                
eliminarip([T|C],L,P):- member(T,C),
                        eliminarip(C,L,P).
eliminarip([T|C],L,P):- not member(T,C),
                        eliminarip(C,L,[T|P]).

member(T,[T|_]).
member(T,[_|C]):-member(T,C).



/* PROGRAMMA: 
   via5.  stampa l'arco per il quale risulta massima 
   la somma dei tre numeri seguenti:
   - PESO DELL'ARCO,
   - PESO DEL NODO-PADRE,
   - PESO DEL NODO-FIGLIO.    */

via5:-trovarchi([T|C]),
      costoarco(T,Costo),
      maxarco(C,Arcomax,Costomax,T,Costo),
      write('L''arco di peso massimo è: '),
      write(Arcomax),
      write('Il suo peso è: '),write(Costomax).
      


trovarchi(L):-findall(arco(A,B,P),arco(A,B,P),L).

maxarco([],A,C,A,C).
maxarco([T|C],Amax,Cmax,Arco,Costo):-costoarco(T,CT),
                                     confronto5(Arco,Costo,T,CT,Am,Cm),
                                     maxarco(C,Amax,Cmax,Am,Cm).

costoarco(arco(A,B,C),Costo):-nodo(A,C1),
                              nodo(B,C2),
                              Costo is C+C1+C2.


confronto5(A1,C1,A2,C2,A1,C1):- C1 >= C2.
confronto5(A1,C1,A2,C2,A2,C2):-	C1 < C2.





/*    *************************************************      */




/* ESERCIZIO D'ESAME:
   Trattare una lista come fosse un vettore, cioe' data una lista e un
   indice i oppurtuno, il programma restituisce l'i-esimo elemento
   della lista */




es(Num,[T|C],_):- Num=<0,
	      nl,
	      tab(10),
	      write('INDICE SCORRETTO !!!').

es(_,[],_):- nl,
	     write('Il vettore e'' vuoto.'),
	     nl,
	     write('Qualsiasi sia l''indice che '),
	     write('hai messo, e'' sicuramente scorretto !').

es(Num,[T|C],_):- cardinalita([T|C],N),
		  Num>N,
		  nl,
		  tab(10),              
		  write(' INDICE TROPPO GRANDE !').

es(Num,L,Elem):- esercizio(Num,L,1,Elem).

esercizio(Num,[T|C],Cont,T):- Cont=Num.

esercizio(Num,[T|C],Cont,Elem):- Cont<Num,
				 J is Cont+1,
				 esercizio(Num,C,J,Elem).
cardinalita([],0).

cardinalita([T|C],N):- cardinalita(C,M),
		       N is M+1.        







/*   ******************************************************   */




arco(a,b,1).
arco(a,c,4).
arco(a,d,1).
arco(c,e,8).
arco(c,f,2).
arco(d,g,1).
arco(e,h,3).
arco(e,i,2).
arco(e,l,7).


/* cammino dal nodo X al nodo Y di complessita' n */

c1(X,Y):-camm1(X,Y,L,[X]),
	 tab(3),
	 write(L).

camm1(X,X,L,L).
camm1(X,Y,L,P):-arco(X,W,_),
		camm1(W,Y,L,[W|P]).


/* cammino dal nodo X al nodo Y migliore di complessita' log(n) */

c2(X,Y):-camm2(X,Y,L,[Y]),
	 tab(3),
	 write(L).

camm2(X,X,L,L).
camm2(X,Y,L,P):-arco(A,Y,_),
		camm2(X,A,L,[A|P]).


/* radice dell'albero  */

radice(X):-arco(X,_,_),
	   not arco(_,X,_),
	   !.


/* foglie dell'albero */

foglia(X):-arco(_,X,_),
	   not arco(X,_,_).

foglie(L):-findall(X,foglia(X),L).


/*               *********************************                */