lista3

ordina1 complementare coda ordina2 testa intersezione unione ordina3 sotto1 sotto2

	bubbles ordinamento elementi lista

 	DOMAINS
	int=integer
	lint=int*
	

	reale=real
	lreale=reale*
	

	simb=symbol
	lsimb=simb*
	

	car=char
	lcar=car*
	

	str=string
	lstr=str*

	PREDICATES
   	

   	bubble(lint,lint)
   	bubble(lreale,lreale)
   	bubble(lsimb,lsimb)
   	bubble(lcar,lcar)
   	bubble(lstr,lstr)
   	

       
       	scambia(lint,lint)
   	scambia(lreale,lreale)
   	scambia(lsimb,lsimb)
   	scambia(lcar,lcar)
   	scambia(lstr,lstr)
   	

	CLAUSES
	

bubble(Lista,Ord):-
	/* scambia gli elementi
	   se necessario */
	scambia(Lista,Lista1),
	/* prova senza cut */
	!,
	bubble(Lista1,Ord).

/* la lista Š ordinata */
/* non ci sono scambi da fare */
bubble(Ord,Ord).

/* i primi due elementi 
   sono da scambiare */
scambia([X,Y|Resto],[Y,X|Resto]):-
	X>Y.
/* sono da scambiare 
   gli elementi nella coda */	
scambia([Z|Resto],[Z|Resto1]):-
	scambia(Resto,Resto1).	
	

complementare crea lista complementare di altra lista

	DOMAINS
	int=integer
	lint=int*
        

        reale=real
        lreale=reale*
        	

	simb=symbol
	lsimb=simb*
	

	car=char
	lcar=car*
	

	str=string
	lstr=str*
	

	PREDICATES
   	compl(lint,lint,lint)
   	compl(lreale,lreale,lreale)
   	compl(lsimb,lsimb,lsimb)
   	compl(lcar,lcar,lcar)
   	compl(lstr,lstr,lstr)

	appartiene(int,lint)
	appartiene(reale,lreale)
	appartiene(car,lcar)
	appartiene(str,lstr)
	appartiene(simb,lsimb)
	

        CLAUSES
	   	

/* caso a) */
compl(L,[],L):-!.
/* caso b) */
compl([T|C],L,D):-
	appartiene(T,L),
	!,
	compl(C,L,D).
/* caso c) */
compl([H|T],L,[H|D]):-
	!,
	compl(T,L,D).
/* caso d) */
compl([],L,[]).
/*compl(_,_,[]).*/
	

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

coda colloca elemento alla fine di una lista

	DOMAINS
	int=integer
	lint=int*
	

	reale=real
	lreale=reale*
	

	car=char*
	lcar=car*
	

	simb=symbol
	lsimb=simb*
	

	str=string*
	lstr=str*

        PREDICATES
        

        incoda(int,lint,lint)
        incoda(reale,lreale,lreale)
        incoda(car,lcar,lcar)
        incoda(simb,lsimb,lsimb)
        incoda(str,lstr,lstr)
	attacca(lint,lint,lint)
	attacca(lreale,lreale,lreale)
	attacca(lcar,lcar,lcar)
	attacca(lstr,lstr,lstr)
	attacca(lsimb,lsimb,lsimb)
	

        CLAUSES
        

        incoda(X,L,M):-
              attacca(L,[X],M).
              

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

sort fornisce lista ordinata a partire da altra lista

	DOMAINS
	int=integer
	lint=int*
	

	reale=real
	lreale=reale*
	

	simb=symbol
	lsimb=simb*
	

	car=char
	lcar=car*
	

	str=string
	lstr=str*

	PREDICATES
       

       	in(int,lint,lint)
   	in(reale,lreale,lreale)
   	in(simb,lsimb,lsimb)
   	in(car,lcar,lcar)
   	in(str,lstr,lstr)
   	

   	insort(lint,lint)
   	insort(lreale,lreale)
   	insort(lsimb,lsimb)
   	insort(lcar,lcar)
   	insort(lstr,lstr)
   	

	CLAUSES
/* condizione limite:
   alla lista vuota
   corrisponde la lista vuota */
insort([],[]).
insort([X|L],M):-
	/* N Š la parte ordinata di L*/
	insort(L,N),
	/* posiziona X in N, mantenendo l'ordine */
	in(X,N,M).

/* primo caso: X non Š il minimo, 
   non pu• trovarsi in testa; allora deve
   trovarsi in coda */
in(X,[A|L],[A|M]):-
	A<X,
	!,
	in(X,L,M).
/* secondo caso: se X Š il minimo, va in testa */
in(X,L,[X|L]).

testa colloca elemento a inizio lista

	DOMAINS
	int=integer
	lint=int*
	

	reale=real
	lreale=reale*
	

	car=char*
	lcar=car*
	

	simb=symbol
	lsimb=simb*
	

	str=string*
	lstr=str*
	

        PREDICATES
        instesta(int,lint,lint)
        instesta(reale,lreale,lreale)
        instesta(car,lcar,lcar)
        instesta(simb,lsimb,lsimb)
        instesta(str,lstr,lstr)
        

        CLAUSES
        

        instesta(X,L,[X|L]).
         	

intersezione fornisce lista elementi comuni a due liste

        DOMAINS
	int=integer
	lint=int*
	

	reale=real
	lreale=reale*
	

	simb=symbol
	lsimb=simb*
	

	car=char
	lcar=car*
	

	str=string
	lstr=str*
	

           
        PREDICATES

        intersezione(lint,lint,lint)
	intersezione(lreale,lreale,lreale)
	intersezione(lcar,lcar,lcar)
	intersezione(lsimb,lsimb,lsimb)
	intersezione(lstr,lstr,lstr)
	

	appartiene(int,lint)
	appartiene(reale,lreale)
	appartiene(car,lcar)
	appartiene(simb,lsimb)
	appartiene(str,lstr)
	

           
        CLAUSES

/* l'intersezione tra X e l'insieme
   vuoto Š l'insieme vuoto */
intersezione([],X,[]).

/* i due insiemi cominciano
   con lo stesso elemento */
intersezione([X|R],Y,[X|Z]):-
	appartiene(X,Y),
	!,
	intersezione(R,Y,Z).

/* ...non iniziano con lo stesso 
      elemento */
intersezione([_|R],Y,Z):-
	intersezione(R,Y,Z).
		

appartiene(X,[X|_]).
appartiene(X,[_|Coda]):-
	appartiene(X,Coda).

unione fornisce lista formata da elementi di due liste senza ripetizioni

	DOMAINS
		

	int=integer
	lint=int*
        

        reale=real
        lreale=reale*
        	

	simb=symbol
	lsimb=simb*
	

	car=char
	lcar=car*
	

	str=string
	lstr=str*
	

	PREDICATES

	unione(lint,lint,lint)
	unione(lreale,lreale,lreale)
	unione(lcar,lcar,lcar)
	unione(lsimb,lsimb,lsimb)
        unione(lstr,lstr,lstr)

	appartiene(int,lint)
	appartiene(reale,lreale)
	appartiene(car,lcar)
	appartiene(str,lstr)
	appartiene(simb,lsimb)
        appartiene(str,lstr)
	

	CLAUSES

/* l'unione di X con l'insieme vuoto
   e' X */
unione([],X,X).

/* se la testa del primo insieme e' gia'
   contenuto nel secondo insieme, esso non
   va ripetuto nell'insieme unione */
unione([X|C],Y,Z):-
	appartiene(X,Y),
	!,
	unione(C,Y,Z).
/* il predicato appartiene() e' fallito */	
unione([X|C],Y,[X|Z]):-
	unione(C,Y,Z).

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

quikq fornisce lista ordinata a partire da alra lista

	DOMAINS
	int=integer
	lint=int*
	

	reale=real
	lreale=reale*
	

	simb=symbol
	lsimb=simb*
	

	car=char
	lcar=car*
	

	str=string
	lstr=str*

	PREDICATES
           	

   	qsort(lint,lint)
   	qsort(lreale,lreale)
   	qsort(lsimb,lsimb)
   	qsort(lcar,lcar)
   	qsort(lstr,lstr)
       

       	perno(int,lint,lint,lint)
   	perno(reale,lreale,lreale,lreale)
   	perno(simb,lsimb,lsimb,lsimb)
   	perno(car,lcar,lcar,lcar)
   	perno(str,lstr,lstr,lstr)
   	

   	attacca(lint,lint,lint)
   	attacca(lreale,lreale,lreale)
   	attacca(lsimb,lsimb,lsimb)
   	attacca(lcar,lcar,lcar)
   	attacca(lstr,lstr,lstr)
   	

        
	CLAUSES

/* S e' la lista oridnata */
qsort([H|T],S):-
	/* dividi gli elementi
	   di T in U1 e U2 */
	perno(H,T,U1,U2),
	/* ordina U1 */
	qsort(U1,V1),
	/* ordina U2) */
	qsort(U2,V2),
	attacca(V1,[H|V2],S).
/* una lista vuota e' gia'
   ordinata */
qsort([],[]).

/* tutti gli elementi della prima
   lista minori di H, sono posti nella 
   seconda lista */
perno(H,[H1|T1],[H1|U1],U2):-
	H1<=H,
	perno(H,T1,U1,U2).
/* tutti gli elementi della prima
   lista maggiori.di H, sono posti nella 
   terza lista */
perno(H,[H1|T1],U1,[H1|U2]):-
	H1>H,
	perno(H,T1,U1,U2).
/* condizione limite:
   svuotamento dello stack */
perno(_,[],[],[]).

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

sotto1 verifica se lista è compresa in altra lista

 	DOMAINS
	int=integer
	lint=int*
	

	reale=real
	lreale=reale*
	

	car=char*
	lcar=car*
	

	simb=symbol
	lsimb=simb*
	

	str=string*
	lstr=str*
	

      				
	PREDICATES

        sottoinsieme(lint,lint)
        sottoinsieme(lreale,lreale)
        sottoinsieme(lcar,lcar)
        sottoinsieme(lsimb,lsimb)
        sottoinsieme(lstr,lstr)
        

        appartiene(int,lint)
        appartiene(reale,lreale)
        appartiene(car,lcar)
        appartiene(simb,lsimb)
        appartiene(str,lstr)
        

	CLAUSES

/* [A|C] e' un sottoinsieme di Y 
   se A appartiene a Y e X e'
   un sottoinsiene di Y */
sottoinsieme([A|C],Y):-
	appartiene(A,Y),
	sottoinsieme(C,Y).
/* l'insieme vuoto e' sottoinsieme
   di qualsiasi insieme */	
sottoinsieme([],Y).	

appartiene(X,[X|_]).
appartiene(X,[_|Coda]):-
	appartiene(X,Coda).
	

sotto2 fornisce tutti i sottoinsieme possibili ricavabili da una lista

	DOMAINS
	int=integer
	lint=int*
        

        reale=real
        lreale=reale*
        	

	simb=symbol
	lsimb=simb*
	

	car=char
	lcar=car*
	

	str=string
	lstr=str*

	PREDICATES

	subinsieme(lint,lint)
        subinsieme(lreale,lreale)
        subinsieme(lcar,lcar)
        subinsieme(lsimb,lsimb)
        subinsieme(lstr,lstr)

	CLAUSES
	

/* generazione di tutti i sottoinsiemi: */
subinsieme([],[]).
/* ... quelli che cominciano con X */
subinsieme([X|C],[X|C1]):-
	subinsieme(C,C1).
/* ... quelli che non cominciano con X */
subinsieme(S,[X|C]):-
        subinsieme(S,C).