Liste in Prolog - (Prolog) Lezione 5

Le liste sono strutture dati tanto semplici quanto usate. In questa lezione vedremo come usarle in Prolog. Una lista è una sequenza di elementi e, come visto anche nella lezione precedente, può essere scritta in Prolog utilizzando il funtore ‘.’ oppure usando la notazione con parentesi quadre. Quest’ultima è la notazione più comoda e sarà l’unica ad essere trattata in questa lezione. Una lista può essere scritta nel seguente modo:

[item1, item2, item3, item4]


Prolog rappresenta le liste come alberi, ed il principio su cui si basa la rappresentazione è la suddivisione in testa e coda. Ad esempio la lista

[item1, item2, item3, item4]

Ha come testa item1 e come coda la lista

[item2, item3, item4]

La rappresentazione interna di ogni lista è un’albero binario dove ogni coppia di nodi dello stesso livello è formata dalla testa della sua coda.

               *  <- Lista [a,b,c]
              / \
             /   \
            a     * <- Coda con testa a [b,c]
                 / \
                /   \
               b     * <- Coda con testa b [c]
                    / \
                   /   \
                  c     [] <- Lista vuota

Per distinguere la testa dalla coda si utilizza il simbolo ‘|’, ad esempio la lista con elementi a, b e c può essere scritta nei seguenti modi:

[a,b,c] = [a | [b,c] ] = [a,b | [c] ] = [a,b,c | [] ]

Ciò è molto importante nella stesura di regole perchè ci consente di distinguere i vari elementi. Vediamo un primo programma che verifica se un elemento è presente in una lista.

member(X,[X|Tail]).


member(X,[H|Tail]) :-
    member(X,Tail).

Tale programma è basato sulla seguente idea:

X è membro della lista L se
(1) X è la testa di L, oppure
(2) X è memebro della coda di L.

Ed un programma per inserire un elemento in testa ad una lista è

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

Dove X è l’elemento da inserire, L la lista in questione ed il terzo parametro è il risultato dell’inserimento. Sarà posibile la seguente conversazione Prolog.

?- add(d,[a,b,c],L).
  L = [d,a,b,c]

Esistono librerie già fatte che forniscono funzioni per le operazioni basilari sulle liste. Ad esempio XSB fornisce la libreria basics.