Liste

 Si dice lista, una sequenza ordinata di un qualunque numero di elementi; gli elementi di una lista possono essere atomi, strutture, liste o qualunque altro tipo di dato. L'ordine in cui i termini si susseguono è importante; per esempio, la lista [a,b,c,d] è differente dalla lista [a,c,d,b] anche se singolarmente gli elementi che vi compaiono sono gli stessi.

Il modo abituale di rappresentare liste in Prolog è il seguente:

[genova,milano,roma]
[10,20,[30,40],cinquanta]
[a,b,[C,D,[e]]]
[ ]

È importante sottolineare i seguenti fatti: è possibile avere, come si può notare dagli esempi, liste di liste di liste... senza alcun limite teorico al livello di annidamento; nelle liste possono comparire anche variabili (come nella terza lista dell'esempio precedente); esse vengono trattate esattamente come le normali variabili Prolog.

In generale nell'ambito di una lista possibile individuare due parti strutturalmente significative, abitualmente note come testa e coda. Con il termine testa viene indicato il primo elemento della lista, e con il termine coda tutto ciò che resta della lista stessa, tolto il primo elemento. Consideriamo per esempio, le quattro liste precedente mente introdotte, per le quali testa e coda sono così definite:

LISTATESTACODA
[genova,milano,roma]genova[milano,roma]
[10,20,[30,40],cinquanta]10[20,[30,40],cinquanta]
[a,b,[C,D,[e]]]a[b,[C,D,[e]]]
[ ]--
L'ultima lista, essendo priva di elementi, non possiede nè una testa nè una coda. Dovreste notare che la struttura della testa di una lista è quella del suo primo elemento, ovvero se il primo elemento di una lista è un'atomo, la sua testa sarà un atomo, se è una variabile sarà una variabile, se è una lista sarà una lista, e così via. Per quanto riguarda invece la coda, essa è sempre e comunque una lista che racchiude gli elementi restanti. Nel caso di una lista contenente un solo elemento, la testa sarà l'elemento stesso e la coda la lista vuota.
LISTATESTACODA
[a]a[]
[[a, b, c]][a, b, c][]
La suddivisione di una lista in testa e coda è un'operazione molto comune in Prolog, tanto che esiste un'apposita notazione per rappresentare una lista che ha una certa testa e una certa coda [testa|coda]. Introducendo in questa notazione due variabili, ad esempio [X|Y], è possibile istanziare liste che hanno X come testa e Y come coda.

Le variabili contenute nelle liste vengono istanziate mediante il meccanismo del matching , come mostrato negli esempi seguenti dove si eguagliano LISTA1 e LISTA2.

LISTA1LISTA2istanziazione
[X,Y|Z][rossi,verdi]X=rossi
Y=verdi
Z=[]
[X,Y|Z][prolog,lisp,pascal]X=prolog
Y=lisp
Z=[pascal]
[X,Y,Z][prolog,lisp,pascal]X=prolog
Y=lisp
Z=pascal
[studenti,[Y,Z]][X,[mario,giovanni]]X=studenti
Y=mario
Z=giovanni

[X,Y|Z] indica una lista composta da un primo elemento X, da un secondo elemento Y e da una coda Z (eventualmente vuota).
[X,Y,Z] indica una lista composta esattamente da tre elementi X, Y Z.
[X,[Y,Z]] indica una lista composta da un primo elemento X e da un secondo elemento [Y,Z] che è a sua volta una lista composta da due elementi.

Provate a vedere come il Prolog risponde alle seguenmti domande: 

% file liste/es1.pl
/*

?- [genova,milano,roma] = [X|Y].
?- [10,20,[30,40],cinquanta] = [X|Y].
?- [a,b,[C,D,[e]]] = [X|Y].
?- [a]= [X|Y]. 
?- [[a, b, c]] = [X|Y].
*/

Consultate nel Database del Prolog i seguenti fatti. 

% file liste/es2.pl

 e_una_lista([questo,e,un,paragrafo,sulle,liste]).
 e_una_lista([la,vispa,teresa,[avea,tra,l,erbetta]]).
e provate queste domande: 
 ?-e_una_lista([X|Y]).
 
 ?-e_una_lista([_|X]).

 ?-e_una_lista([_,_,_,[X|_]]).
Cercercate di immaginare come il Prolog risponderà. Controllate le vostre risposte con quelle fornite dall'interprete Prolog.

Membro: appartenenza ad una lista

Una delle operazioni più frequenti nell'ambito della programmazione logica è quella di voler sapere se un dato elemento è presente o meno in una certa lista. Il modo più semplice per effettuare questo in Prolog, è quello di andare a vedere se l'elemento coincide con la testa della lista; se questoè vero, il compito finito; altrimenti si può andare a vedere se l'elemento compare nella coda della stessa lista. Quest'ultima operazione equivale in realtà a considerare una nuova lista (la coda della lista di partenza) e a ripetere su di essa il procedimento prima descritto. Il processo di analisi e accorciamento della lista viene quindi iterato finchè non si verifica una delle condizioni seguenti:
  1. l'elemento viene individuato;
  2. la lista è finita, ovvero si è rimasti con una lista la cui coda è la lista vuota. In questo caso si ha un fallimento.

Introduciamo ora il predicato:

membro(X,Y).
il quale è vero quando l'elemento associato alla variabile X è contenuto nella lista associata alla variabile Y. Possiamo scrivere il predicato membro tenendo conto che:
  1. X appartiene a Y se coincide con la testa di Y. In Prolog:
    membro(X,[X|Y]).
  2. X appartiene a Y se X compare nella coda di Y. In Prolog:
    membro(X,[_|Y]) :- membro(X,Y).
Questa regola presenta un esempio molto classico di ricorsione perchè è definita in termini di se stessa; ovvero, affinchè questa formulazione della regola membro sia vera, occorre che siano vere una o più istanze differenti della regola stessa. Le due regole prima introdotte, sono, insieme, sufficienti a realizzare il concetto di appartenenza. Vediamo alcuni esempi. 
%file: liste/es3.pl

 membro(X,[X|_]).
 membro(X,[_|Y]):-membro(X,Y).
Come risponderà l'interprete Prolog alle seguenti domande? 
 
 ?-membro(a,[i,n,f,o,r,m,a,t,i,c,a]).
 
 ?-membro(b,[c,o,m,p,u,t,e,r]).

 ?-membro(c,[m,i,[s,c,e],l,a]).

Approfondimemti: come il Prolog tratta la ricorsione

Approfondimemti: pericoli insiti nella ricorsione

Conc (Append): concatena due liste

Vogliamo definire la relazione
conc(L1,L2,L3)
dove L1 e L2 sono due liste e L3 è la loro concatenazione.

Per concatenare due liste possiamo utilizzare le seguenti regole:

  1. Se il primo argomento di conc è la lista vuota allora il secondo e il terzo argomento devono coincidere.In Prolog:
    conc([],L,L).
  2. Se il primo argomento non è una lista vuota allora lo possiamo pensare composto da una testa e una coda [X|L1]. Concatenare questa lista con una seconda lista L2 produce come risultato una terza lista [X|L3], dove L3 è la concatenazione di L1 e L2 (vedi la Fig. 1). In Prolog:
    conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3). 

               
                 [X|L1]
   
         |X|-------L1----------||-------L2----------|
       
         |X|-------------------L3-------------------| 
                               
                              [X|L3]
Fig 1. Concatenazione di liste.

Dopo aver inserito nel database del Prolog le clausole per conc 

/* file: liste/es5.pl

/* concatena due liste */

conc([],L,L).
conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3).
potete usarlo per concatenare due liste:
?- conc([a,b,c],[d,e,f],L).
oppure per dividere in due parti una lista
?- conc(X,Y,[a,b,c]).

Sottoliste

Utilizzando il predicato conc scrivere un nuovo predicato sublist
sublist(S,L).
che controlli se la lista S è una sottolista di L.
Suggerimento. La lista S sarà una sottolista della lista L se esistono altre due liste, L1 e L3, eventualmente vuote, tali che concatenando L1 ed S si ottenga L2 e concatenando quest'ultima con L3, si ottenga la lista L. Vedi la Fig. 2. 

            |-----------------L-----------------|            

            |-----L1----|-----S-----|-----L3----|

            |----------L2-----------|
Fig 2. Sublist.

Un possibile goal è il seguente:

?- sublist([b,c,d],[a,b,c,d,e]).
Provate a scrivere un goal per trovare tutte le sottoliste di [a,b,c,d,e].
Assicuratevi che non venga prodotta, fra le varie sottoliste, la lista vuota.

Inserire e cancellare elementi da una lista

Per aggiungere l'elemento X in testa alla lista L è sufficiente scrivere [X|L]. Tuttavia possiamo anche scrivere un predicato add(X,L,L1) che aggiunge l'elemento X in testa alla lista L fornendo come risultato la lista L1 in questo modo:
add(X,L,[X|L]).

Vogliamo ora scrivere il predicato

delete(X,L,L1).
che elimina dalla lista L una qualsiasi occorrenza di X dando come risultato la lista L1. Possiamo utilizzare le seguenti regole:
  1. Se l'elemento X è la testa della lista cancellare X significa tenere solo la coda della lista. In Prolog:
    del(X,[X|L],L).
  2. Se X è nella coda può essere cancellato dalla coda mantenendo la stessa testa. In Prolog:
    del(X,[T|C],[T|C1]) :- del(X,C,C1).
Provate il seguente goal:
?- del(b,[a,b,c,b,d,b],L).
Il predicato del può anche essere utilizzato con il secondo argomento variabile e istanziando il terzo come in:
?- del(z,L,[a,b,c,d,e]).
In questo caso si otterrà una lista L che contiene z in una posizione qualsiasi.
Possiamo anche scrivere un predicato
insert(X,L,L1)
per inserire un elemento X in una qualsiasi posizione di L (con risultato L1 ) sfruttando del.

Definite i predicati add, del e insert 

%file: liste/es7.pl

% add 
add(X,L,[X|L]).

%delete 
del(X,[X|L],L).
del(X,[T|C],[T|C1]) :- del(X,C,C1).

%insert
insert(X,L,L1) :- del(X,L1,L).
Cosa risponderà l'interprete Prolog alle seguenti domande? 

?- add(x,[y,z,t],L).

?- del(b,[a,b,c,b,d,b],L).  % usare l'opzione "all" di query 

?- insert(z,[a,b,c,d,e],L). % usare l'opzione "all" di query

Generare tutte le permutazioni degli elementi di una lista

Il predicato
permutazione(L,P).
ha successo se P è una permutazione degli elementi della lista L.
Con il meccanismo del backtracking si possono generare tutte le permutazioni P degli elementi della lista L.
Se
L=[a,b,c]
si otterrà
P=[a,b,c];
P=[b,a,c];
P=[b,c,a];
.........
Le permutazioni possono essere generate usando le seguenti regole:
  1. Se la prima lista è vuota anche la seconda deve essere vuota.
    permutazione([],[]).
  2. Se la prima lista non è vuota allora avrà la forma [X|L], e una permutazione di questa lista può essere ottenuta inserendo l'elemento X in una posizione qualsiasi della lista L1 permutazione di L, come mostrato in Fig. 3. Per inserire X in L1 possiamo usare il predicato insert, visto precedentemente. In Prolog:
    permutazione([X|L],P):- permutazione(L,L1),insert(X,L1,P). 
       |X|------------L----------|
        |
        |
        \----\ 
             | 
             V
         |------------L1---------|  

       (L1 e' una permutazione di L)
Fig. 3 Permutazioni.

Definite il predicato permutazione. 

         
%file liste/es8.pl

% permutazioni 
permutazione([],[]).
permutazione([X|L],P):- permutazione(L,L1),insert(X,L1,P).         


%delete
del(X,[X|L],L).
del(X,[T|C],[T|C1]) :- del(X,C,C1).

%insert
insert(X,L,L1) :- del(X,L1,L).
Scrivete un goal per controllare se [b,c,a] è una permutazione di [a,b,c]. Scrivete inoltre un goal per ottenere tutte le permutazioni degli elementi della lista [a,b,c].