LISTE LISTE
•• Le liste sono una delle strutture dati primitive più diffuse nei linguaggi Le liste sono una delle strutture dati primitive più diffuse nei linguaggi di programmazione per l'elaborazione simbolica (es: Lisp)
di programmazione per l'elaborazione simbolica (es: Lisp)
•• In Prolog le liste sono dei In Prolog le liste sono dei termini termini costruiti a partire da uno speciale costruiti a partire da uno speciale
atomo (che denota la lista vuota) e utilizzando un particolare operatore atomo (che denota la lista vuota) e utilizzando un particolare operatore funzionale (l'operatore “.”).
funzionale (l'operatore “.”).
funzionale (l'operatore “.”).
funzionale (l'operatore “.”).
•• La definizione di lista può essere data ricorsivamente nel modo La definizione di lista può essere data ricorsivamente nel modo seguente:
seguente:
–
– l’atomo l’atomo [][] rappresenta la lista vuotarappresenta la lista vuota –
– il termine il termine .(T,Lista).(T,Lista) è una lista se è una lista se TT è un termine qualsiasi e è un termine qualsiasi e ListaLista una Lista.
una Lista. TT prende il nome di prende il nome di TESTATESTA della lista e della lista e ListaLista di di CODACODA
LISTE: ESEMPI LISTE: ESEMPI
•• II seguenti seguenti termini termini Prolog Prolog sono sono liste liste::
(
(11)) [][]
(
(22)) ..(a,(a, [])[]) (
(33)) ..(a,(a, ..(b,[]))(b,[])) (
(44)) ..(f(g(X)),(f(g(X)), .. (h(z),(h(z), ..(c,(c, [])))[]))) (
(55)) ..([],([], [])[])
2 2
(
(55)) ..([],([], [])[]) (6)
(6) .(.(a,[]), .(b, []))).(.(a,[]), .(b, [])))
•• Il Il Prolog Prolog fornisce fornisce una una notazione notazione semplificata semplificata per per la la rappresentazione rappresentazione delle
delle liste liste:: la la lista lista . .(T,LISTA) (T,LISTA) può essere rappresentata anche come [T
[T | | LISTA] LISTA]
•• TaleTale rappresentazionerappresentazione puòpuò essereessere paragonataparagonata all'applicazioneall'applicazione della
della funzionefunzione "cons""cons" deldel LispLisp.. LaLa testatesta (head)(head) TT ee lala codacoda (tail)(tail) LISTA
LISTA delladella listalista nonnon sonosono altroaltro cheche ii risultatirisultati dell'applicazionedell'applicazione delle
delle funzionifunzioni LispLisp "car""car" ee "cdr""cdr" allaalla listalista stessastessa..
LISTE: ESEMPI LISTE: ESEMPI
•• Le Le liste liste nell'esempio nell'esempio precedente precedente possono possono essere essere rappresentate rappresentate nel
nel modo modo seguente seguente:
(
(11)) [][]
(
(22)) [a[a || []][]]
(
(33)) [a[a || [b[b || []]][]]]
(
(44)) [f(g(X))[f(g(X)) || [h(z)[h(z) || [c[c || []]]][]]]]
(
(44)) [f(g(X))[f(g(X)) || [h(z)[h(z) || [c[c || []]]][]]]]
(
(55)) [[][[] || []][]]
(
(66)) [[a[[a || []][]] || [b[b || []]][]]]
•• Ulteriore Ulteriore semplificazione semplificazione;; la la lista lista
[a|[a| [b|[b| [c]]][c]]]può può essere essere rappresentata
rappresentata nel nel modo modo seguente seguente::
[a,[a, b,b, c]c]LISTE: ESEMPI LISTE: ESEMPI
•• Le Le liste liste nell'esempio nell'esempio precedente precedente possono possono essere essere rappresentate rappresentate nel
nel modo modo seguente seguente:
(
(11)) [][]
(
(22)) [a][a]
(
(33)) [a,b][a,b]
(
(44)) [f(g(X)),h(z),c][f(g(X)),h(z),c]
4 4
(
(44)) [f(g(X)),h(z),c][f(g(X)),h(z),c]
(
(55)) [[]][[]]
(
(66)) [[a],b][[a],b]
•• Ulteriore Ulteriore semplificazione semplificazione;; la la lista lista
[a|[a| [b|[b| [c]]][c]]]può può essere essere rappresentata
rappresentata nel nel modo modo seguente seguente::
[a,[a, b,b, c]c]UNIFICAZIONE SULLE LISTE UNIFICAZIONE SULLE LISTE
•• L'unificazione (combinata con le varie notazioni per le liste) è un L'unificazione (combinata con le varie notazioni per le liste) è un potente meccanismo per l'accesso alle liste
potente meccanismo per l'accesso alle liste
p([
p([11,,22,,33,,44,,55,,66,,77,,88,,99])]).. :
:--p(X)p(X).. yes
yes X=[X=[11,,22,,33,,44,,55,,66,,77,,88,,99]] yes
yes X=[X=[11,,22,,33,,44,,55,,66,,77,,88,,99]] :
:-- p([X|Y])p([X|Y]).. yes
yes X=X=11 Y=[Y=[22,,33,,44,,55,,66,,77,,88,,99]] :
:-- p([X,Y|Z])p([X,Y|Z]).. yes
yes X=X=11 Y=Y=22 Z=[Z=[33,,44,,55,,66,,77,,88,,99]] :
:-- p([_|X])p([_|X]).. yes
yes X=[X=[22,,33,,44,,55,,66,,77,,88,,99]]
•• Le Le procedure procedure che che operano operano su su liste liste sono sono definite definite come come procedure procedure ricorsive
ricorsive basate basate sulla sulla definizione definizione ricorsiva ricorsiva di di lista lista
•• Verificare Verificare se se un un termine termine è è una una lista lista
is_list(T)
is_list(T) == truetrue sese TT èè unauna listalista false
false sese TT nonnon èè unauna listalista
OPERAZIONI SULLE LISTE OPERAZIONI SULLE LISTE
6 6
false
false sese TT nonnon èè unauna listalista is_list([])
is_list([]).. is_list([X|L])
is_list([X|L]) ::-- is_list(L)is_list(L)..
:
:-- is_list([is_list([11,,22,,33])]).. yes
yes :
:-- is_list([a|b])is_list([a|b]).. no
no
OPERAZIONI SULLE LISTE OPERAZIONI SULLE LISTE
•• Verificare Verificare se se un un termine termine appartiene appartiene ad ad una una lista lista
member(T,L)
member(T,L) "T"T èè unun elementoelemento delladella listalista L”L”
member(T,
member(T, [T[T || _])_]).. member(T,
member(T, [_[_ || L])L]) ::-- member(T,member(T, L)L).. :
:-- member(member(22,, [[11,,22,,33])]).. yes
yes :
:-- member(member(11,, [[22,,33])]).. no
no :
:-- member(X,member(X, [[11,,22,,33])]).. yes
yes X=X=11;; X=
X=22;; X=
X=33;;
La relazione
La relazione member member può quindi può quindi essere utilizzata in più di un modo essere utilizzata in più di un modo (per la verifica di appartenenza di (per la verifica di appartenenza di un elemento ad una lista o per un elemento ad una lista o per
individuare gli elementi di una lista).
individuare gli elementi di una lista).
OPERAZIONI SULLE LISTE OPERAZIONI SULLE LISTE
•• Determinare Determinare la la lunghezza lunghezza di di una una lista lista
length(L,N)
length(L,N) ”la”la listalista LL haha NN elementi”elementi”
lenght([], lenght([],00)).. length([_|L],N)
length([_|L],N) ::-- length(L,Nlength(L,N11),), N
N isis NN11 ++ 11..
Versione ricorsiva Versione ricorsiva
8 8
N
N isis NN11 ++ 11..
length
length11(L,N)(L,N) ::-- lengthlength11(L,(L, 00,, N)N).. lenght
lenght11([],([], ACC,ACC, ACC)ACC).. length
length11([_|L],ACC,N)([_|L],ACC,N)::-- ACCACC11 isis ACC+ACC+11,, length
length11(L,(L, ACCACC11,, N)N)..
Versione ricorsiva Versione ricorsiva
Versione iterativa
Versione iterativa
•• Concatenazione Concatenazione di di due due liste liste
append(L
append(L11,L,L22,L,L33)) “L“L33 e’e’ ilil risultatorisultato delladella concatenazioneconcatenazione di
di LL11 ee LL22””
append([],L,L) append([],L,L).. append([H|T],L
append([H|T],L22,[H|T,[H|T11])])::-- append(T,Lappend(T,L22,T,T11))..
OPERAZIONI SULLE LISTE OPERAZIONI SULLE LISTE
append([H|T],L
append([H|T],L22,[H|T,[H|T11])])::-- append(T,Lappend(T,L22,T,T11))..
:
:-- append([append([11,,22],[],[33,,44,,55],L)],L).. yes
yes LL == [[11,,22,,33,,44,,55]] :
:-- append([append([11,,22],L],L22,[,[11,,22,,44,,55])]).. yes
yes LL22 == [[44,,55]] :
:-- append([append([11,,33],[],[22,,44],[],[11,,22,,33,,44])])..
•• Evoluzione Evoluzione della della computazione computazione in in seguito seguito alla alla valutazione valutazione del del goal goal
:
:--append([append([11,,22],[],[33,,44,,55],L)],L)..
ESEMPIO ESEMPIO
1 2 3 4 5
H T
H T1 dove append([2],[3,4,5],T1) L2
10 10
•• Viene Viene generato generato ilil sottogoal sottogoal
::-- append([append([22],[],[33,,44,,55],T],T11)) 1H T1 dove append([2],[3,4,5],T1)
2 3 4 5
2 H T =[]
H T1’ dove append([],[3,4,5],T1’) L2
T1
•• Viene Viene generato generato ilil sottogoal sottogoal
::-- append([],[append([],[33,,44,,55],T],T11’)’)•• Utilizzando Utilizzando la la prima prima clausola clausola si si ha ha che che
T1T1’’ == [[33,,44,,55]]ESEMPIO ESEMPIO
H T1
2
T1’
1 [[11,,22,,33,,44,,55]]
H T1
3 4 5
ESEMPI ESEMPI
:- append(L1, L2, [a,b,c,d]).
yes L1=[] L2=[a,b,c,d];
L1=[a] L2=[b,c,d];
L1=[a,b] L2=[c,d];
L1=[a,b,c] L2=[d];
L1=[a,b,c,d] L2=[]
:- append(L1, [c,d], L).
12 12
:- append(L1, [c,d], L).
yes L1=[] L=[c,d];
L1=[_1] L=[_1,c,d];
L2=[_1,_2] L=[_1,_2,c,d];
(infinite soluzioni) :- append([a,b], L1, L).
yes L1=_1 L=[a,b | _1]
:- append(L1, L2, L3).
yes L1=[] L2=_1 L3=_1;
L1=[_1] L2=_2, L3=[_1 | _2];
L1=[_1,_2] L2=_3 L3=[_1,_2 | _3];
(infinite soluzioni)
OPERAZIONI SULLE LISTE OPERAZIONI SULLE LISTE
•• Cancellazione Cancellazione di di uno uno o o più più elementi elementi dalla dalla lista lista
delete
delete11(El,L,L(El,L,L11)) ”la”la listalista LL11 contienecontiene gligli elementielementi didi LL tranne
tranne ilil primoprimo terminetermine unificabileunificabile concon El”El”
delete
delete11(El,[],[])(El,[],[]).. delete
delete11(El,[El|T],T)(El,[El|T],T).. delete
delete11(El,[El|T],T)(El,[El|T],T).. delete
delete11(El,[H|T],[H|T(El,[H|T],[H|T11])])::-- deletedelete11(El,T,T(El,T,T11))..
delete(El,L,L1) ”la lista L1 contiene gli elementi di L delete(El,L,L1) ”la lista L1 contiene gli elementi di L
tranne
tranne tuttitutti i termini unificabili con El”i termini unificabili con El”
delete(El,[],[]).
delete(El,[],[]).
delete(El,[El|T],T1):
delete(El,[El|T],T1):-- delete(El,T,T1).delete(El,T,T1).
ATTENZIONE !!
ATTENZIONE !!
•• Le Le due due procedure procedure delete delete e e delete delete1 1 forniscono forniscono una una sola sola risposta risposta corretta
corretta ma ma non non sono sono corrette corrette in in fase fase di di backtracking backtracking..
:
:-- delete(a,[a,b,a,c],L)delete(a,[a,b,a,c],L).. yes
yes L=[b,c]L=[b,c];; L=[b,a,c]
L=[b,a,c];; L=[a,b,c]
L=[a,b,c];;
Unica soluzione corretta !!
14 14
L=[a,b,c]
L=[a,b,c];; L=[a,b,a,c]
L=[a,b,a,c];; no
no
•• Il Il problema problema è è legato legato alla alla mutua mutua esclusione esclusione tra tra la la seconda seconda e e la la terza terza clausola
clausola della della relazione relazione delete delete Se Se T T appartiene appartiene alla alla lista lista (per (per cui cui la
la seconda seconda clausola clausola di di delete delete ha ha successo), successo), allora allora la la terza terza clausola clausola non
non deve deve essere essere considerata considerata una una alternativa alternativa valida valida..
Questo
Questo problema problema verra’ verra’ risolto risolto dal dal CUT CUT
OPERAZIONI SULLE LISTE OPERAZIONI SULLE LISTE
•• Inversione Inversione di di una una lista lista
reverse(L,Lr)
reverse(L,Lr) ”la”la listalista LrLr contienecontiene gligli elementielementi didi LL in
in ordineordine inverso”inverso”
reverse([],[]) reverse([],[]).. reverse([H|T],Lr)
reverse([H|T],Lr)::-- reverse(T,Treverse(T,T22),), reverse([H|T],Lr)
reverse([H|T],Lr)::-- reverse(T,Treverse(T,T22),), append(T
append(T22,[H],Lr),[H],Lr)..
:
:-- reverse([],[])reverse([],[]).. yes
yes :
:-- reverse([reverse([11,,22],Lr)],Lr).. yes
yes LrLr == [[22,,11]]
ESEMPIO ESEMPIO
•• Evoluzione della computazione in seguito alla valutazione del goal Evoluzione della computazione in seguito alla valutazione del goal
:
:--reverse([1,2,3], Lr).reverse([1,2,3], Lr).
:-reverse([1,2,3], Lr)
:-reverse([2,3], L1),append(L1,[1],Lr) H=1, T=[2,3]
H=2, T=[3]
16 16 :-reverse([3], L2),append(L2,[2],L1), append(L1,[1],Lr)
:-reverse([],L3),append(L3,[3],L2),append(L2,[2],L1),append(L1,[1],Lr) H=2, T=[3]
H=3, T=[]
L3=[]
:-append([],[3],L2),append(L2,[2],L1),append(L1,[1],Lr) L2=[3]
:-append([3],[2],L1),append(L1,[1],Lr) L1=[3,2]
:-append([3,2],[1],Lr) Lr=[3,2,1]
OPERAZIONI SULLE LISTE OPERAZIONI SULLE LISTE
•• Inversione Inversione di di una una lista lista (Versione (Versione iterativa) iterativa)
reverse
reverse11(L,Lr)(L,Lr) ”la”la listalista LrLr contienecontiene gligli elementielementi didi LL in
in ordineordine inverso”inverso”
reverse
reverse11(L,Lr)(L,Lr) ::-- reversereverse11(L,[],Lr)(L,[],Lr).. reverse
reverse11([],([], ACC,ACC, ACC)ACC)..
Potevamo
Potevamo usareusare la
la appendappend reverse
reverse11([],([], ACC,ACC, ACC)ACC).. reverse
reverse11([H|T],ACC,Y)([H|T],ACC,Y)::-- reversereverse11(T,[H|ACC],Y)(T,[H|ACC],Y)..
•• La La lista lista L L da da invertire invertire viene viene diminuita diminuita ad ad ogni ogni passo passo di di un un elemento elemento e e tale
tale elemento elemento viene viene accumulato accumulato in in una una nuova nuova lista lista (in (in testa) testa)
–
– UnUn elementoelemento vieneviene accumulatoaccumulato davantidavanti all'elementoall'elemento cheche lolo precedevaprecedeva nellanella lista
lista originaria,originaria, ottenendoottenendo inin questoquesto modomodo l'inversionel'inversione.. QuandoQuando lala primaprima lista
lista èè vuota,vuota, l'accumulatorel'accumulatore contienecontiene lala listalista invertitainvertita
la
la appendappend
OPERAZIONI SUGLI INSIEMI OPERAZIONI SUGLI INSIEMI
•• Gli Gli insiemi insiemi possono possono essere essere rappresentati rappresentati come come liste liste di di oggetti oggetti (senza (senza ripetizioni)
ripetizioni)
•• Intersezione di due insiemi Intersezione di due insiemi
intersection(S
intersection(S11,S,S22,S,S33)) ”l’insieme”l’insieme SS33 contienecontiene gligli elementielementi appartenenti
appartenenti all’intersezioneall’intersezione didi SS11 ee SS22””
18 18
intersection([],S
intersection([],S22,[]),[]).. intersection([H|T],S
intersection([H|T],S22,[H|T,[H|T33])])::-- member(H,Smember(H,S22),), intersection(T,S
intersection(T,S22,T,T33)).. intersection([H|T],S2,S3):
intersection([H|T],S2,S3):-- intersection(T,S2,S3).intersection(T,S2,S3).
:
:-- intersection([a,b],intersection([a,b], [b,c],[b,c], S)S).. yes
yes S=[b]S=[b]
:
:-- intersection([a,b,c,d],Sintersection([a,b,c,d],S22,[a,c]),[a,c]).. yes
yes SS22=[a,c=[a,c || __11]]
ESEMPIO ESEMPIO
:
:-- intersection(S1,S2,[a,c]).intersection(S1,S2,[a,c]).
yes
yes S1=[a,c]S1=[a,c] S2=[a,c | _1];S2=[a,c | _1];
S1=[a,c,_2]
S1=[a,c,_2] S2=[a,c | _1];S2=[a,c | _1];
S1=[a,c,_2,_3] S2=[a,c | _1];
S1=[a,c,_2,_3] S2=[a,c | _1];
...
...
(infinite soluzioni) (infinite soluzioni) (infinite soluzioni) (infinite soluzioni) ...
...
:
:-- intersection([a,b,c],[b,c,d],S3).intersection([a,b,c],[b,c,d],S3).
yes
yes S3=[b,c];S3=[b,c];
S3=[b];
S3=[b];
S3=[c];
S3=[c];
S3=[];
S3=[];
no no
Unica soluzione corretta !!
Problema della mutua esclusione tra clausole
OPERAZIONI SUGLI INSIEMI OPERAZIONI SUGLI INSIEMI
•• Unione di due insiemi Unione di due insiemi
union(S
union(S11,S,S22,S,S33)) ”l’insieme”l’insieme SS33 contienecontiene gligli elementielementi appartenenti
appartenenti all’unioneall’unione didi SS11 ee SS22”” union([],
union([], SS22,, SS22)).. union([X|REST],S
union([X|REST],S22,S),S)::-- member(X,member(X, SS22),),
20 20
union(REST,
union(REST, SS22,, S)S).. union([X|REST],S
union([X|REST],S22,[X|S]),[X|S])::-- union(REST,union(REST, SS22,, S)S)..
