Prolog – przetwarzanie list

Maciej Krzywonos
Łukasz Dajcz

Prolog – reprezentacja list

Lista jest dowolnym ciągiem obiektów

zapisywanych w postaci:

[element_1,element_2,...,element_n]

Prolog - reprezentacja list

Lista jest reprezentowana w postaci

struktury drzewa:

Prolog - reprezentacja list

Budowa listy:

• głowa – wskazuje początek listy

• ogon – wskazuje na pozostałe elementy

listy

Prolog – właściwości list

Właściwości list:
• Głowa listy może być dowolną strukturą

języka prolog

• Ogon listy jest zawsze listą
• Lista jest strukturą rekurencyjną - jeśli

ogon listy nie jest pusty to też jest listą

Prolog – właściwości list

W języku Prolog listy mogą być zapisywany w sposób

bezpośrednio odzwierciedlającym ich budowę:

[Head | Tail]

, gdzie:

Head – ciąg dowolnych elemntów
Tail – lista elemntów, np.:

[Man, Audi, BMW]=[Man|[Audi, BMW]]=[Man, Audi|[BMW]]

Elementem składowym listy może być inna lista

Prolog-przykłady list

Przykładowe listy:

Samochody = [Audi, Mercedes]
Autobusy = [Volvo, Solaris]
Pojazdy = [pociagi, Samochody, Autobusy]
Lista = [pociagi, autobusy, [samoloty, statki]]

przetwarzanie list - dodawanie
elementu

Operacja dodawania elementu do listy.

Element dodawany jest na początek listy (element jest

głową listy), np.:

add(element_1,Lista, [element_1|Lista])

przetwarzanie list - member

Operacje sprawdzająca czy dany element należy do listy:

member(A,Lista)

powinno być prawdziwe jeśli a jest

elementem listy Lista

member (b,[a,b,c]). - prawda
member(b,[a,[b,c]]). - falsz
member([b,c],[a,[b,c]]). -prawda
member([a|_],[b,d,[a,f,g,a,h,i]]). - prawda

implementacja:

member(X,[X|Ogon]).
member(X,[Glowa|Ogon]):-member(X,Ogon).

Łączenie list

Operacja łączenia list:

conc(Lista_1,Lista_2,Lista_3).

– łączy listę lista_1 z

lista_2, połączone listy znajdują się w liście trzeciej
(lista_3), np.:

conc ([a,c],[b,g],W)
W=[a,c,b,g]
conc([Man, Star],[Audi, BMW],W)
W=[Man,Star,Audi,BMW]

`

Zapis łączenia list w języku Prolog:

conc([],Lista,Lista).
conc([H|T1],L2,[H|T2]):- conc(T1,L2,T2).

Łączenie list

Zastosowanie operacji łączenia list:
Dekompozycja list, np.:

conc(Lista_1, Lista_2,[s,i,k]).
Lista_1=[]
Lista_2=[s,i,k];

Lista_1=[s]
Lista_2=[i,k];

Łączenie list

Lista_1=[s,i]
Lista_2=[k];

Lista_1=[s,i,k]
Lista_2=[];

Łączenie list

Operacja szukania podlist, np.:

?- conc(Przed,[sr|Po],[pon,wt,sr,czw,pt,sob,nd]).

Przed = [pon,wt]
Po = [czw,pt,sob,nd]

Szukanie poprzednika i następnika:

?- conc(_, [Przed,sr,Po|_],[pon,wt,sr,czw,pt,sob,nd]).

Przed=wt
Po=czw

Łączenie list

Usuwanie podlisty za pomocą operacji conc,np.:

?- Lista_1 = [a,b,z,z,c,z,z,z,d,e],conc(Lista_2,

[z,z,z|_],Lista_1)

Lista_1 = [a,b,z,z,c,z,z,z,d,e]
Lista_2 = [a,b,z,z,c]

Szukanie podlisty

Operacja sublist(S,L) – lista S należy do listy L, jeśli lista L

składa się z dwóch list L1 i L2, a lista L2 jest połączeniem

list S i L3.

sublist(S,L):- conc(L1,L2,L), conc(S,L3,L2).
np.:

?- sublist(S,[c,d,a]).
S=[];
S=[c];
S=[c,d];
S=[c,d,a];
S=[d];

Permutacje elementów listy

Operacja generowania permutacji listy jest realizowana za

pomocą polecenia permut (lista_1, lista_2). Jest ona
prawdziwa jeśli lista lista_2 jest permutacją listy
lista_1,np.:

?- permut([1,2,3],Lista).
Lista=[1,2,3];
Lista=[1,3,2];
Lista=[2,1,3];
.
.
.

Permutacja elementów listy

Najpierw usuwamy element, na pozostałej reszcie
dokonujemy permutacji i wstawiamy element na początek

implementacja:

permutacja([],[]).
permutacja(L,[X|P]) :- del(X,L,L1) , permutacja(L1,P).

Operacje delete

Operacja usuwania elementu z listy.

del(element_1, Lista_1, Lista_2)

jest prawdziwe jeśli

lista lista_2 jest równa liście lista_1 pomniejszona o
element element_1. Położenie elementu element_1 jest
dowolne.

Zapis w Prologu:

del(X,[X|Ogon], Ogon).
del(X,[H|Ogon],[H|Ogon1]):-del(X,Ogon,Ogon1).

Prolog – przetwarzanie list

Operacja del c.d.
Wstawianie elementu do listy za pomocą operacji del, np.:

?-del(a,Lista,[1,2,3]).

Lista=[a,1,2,3];
Lista=[1,a,2,3];
Lista=[1,2,a,3];

Lista=[1,2,3,a];

Prolog – przetwarzanie list

Operacja del c.d.
Operacja del(element, lista_1,lista_2) usuwa tylko jedno

wystąpienie element z listy lista_1, np.:

?- del(w,[w,q,w,w],Lista).
Lista=[q,w,w];
Lista=[w,q,w];
Lista=[w,q,w];

Odwracanie listy

Możemy odwrócić kolejność elementów listy

odwroc([a,b,c],W).
W = [c, b, a].

lub:

odwroc(W,[a,b,c]).
W = [c, b, a]
implementacja:

odwroc([],[]).
odwroc([H|T],L) :- odwroc(T,R ), conc(R,[H],L).

Obliczanie długości listy

Możemy obliczyć długość listy:

?- dlugosc([a,b,c],Wynik).
Wynik = 3.

implementacja:

dlugosc([],0).
dlugosc([_|Ogon],Dlug) :- dlugosc(Ogon,X) , Dlug is

X+1.

Prolog - listy

Koniec