Lista to uporządkowany zbiór elementów. Elementem może być dowolna struktura w Prologu (czyli term).

Listę zapisujemy:

[a,b,c]
[2,4,6,ala,ma,kota]
[]

Każda lista składa się z:

• głowy (ang. head), która jest zawsze 1. elementem listy, oraz
• ogona (ang. tail), który jest zawsze listą

Głowę od ogona rozdzielamy operatorem | (pionowa kreska), np.:

?- [X|Y]=[a,b,c,d].
 
X = a
Y = [b, c, d] ;

Dekompozycja i strukturalizacja list jest realizowana głównie przez mechanizm unifikacji, a co za tym idzie w.w. notacja jest jej podstawą. Na przykład:

?- [X,Y|Z]=[a,b,c,d].
 
X = a
Y = b
Z = [c, d] ;
 
?- [X,Y,a]=[Z,b,Z].
 
X = a
Y = b
Z = a ;

Ćwiczenie

Proszę sprawdzić poniższe unifikacje:

?- X=[a,b,c].
?- [X|Y]=[a,b,c].
?- [[a,b],c]=[X,Y].
?- [a(b),c(X)]=[Z,c(a)].
?- [X|Y]=[a].

Wybieranie elementu:

trzeci([A,B,C|Reszta],C).

Zdefiniować predykat porównujący 2 wybrane elementy listy, np. 3. i 4.

Przykład użycia:

?- porownaj([a,b,c,d]).
No
?- porownaj([a,b,c,c]).
Yes

Zdefiniować predykat zamieniający 2 wybrane elementy listy, np. 3. i 4.

?- zamien([a,b,c,d],X).
X=[a,b,d,c]
Yes

nalezy(X,[X|_]).
nalezy(X,[_|Yogon]) :-
	nalezy(X,Yogon).

Ćwiczenie

Dopisać predykat nalezy do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

?- nalezy(c,[a,b,c,d]).
?- nalezy(x,[a,b,c,d]).
?- nalezy(X,[a,b,c,d]).
?- nalezy(x,a).
?- nalezy(X,a).

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

Ćwiczenie

Dopisać predykat dlugosc do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

  ?- dlugosc([a,b,c],X).

(źródło: LearnPrologNow)

a2b([],[]).
a2b([a|Ta],[b|Tb]) :- 
   a2b(Ta,Tb).

Ćwiczenie

Dopisać predykat a2b do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

  ?- a2b([a,a,a],[b,b,b]).
  ?- a2b([a,a,a,a],[b,b,b]).
  ?- a2b([a,s,d],[b,s,d]).
 
  ?- a2b([a,a,a,a],X).
  ?- a2b(X,[b,b]).
  ?- a2b(X,Y).

Uwaga: ten predykat robi „coś ciekawego” tylko na listach zaczynających się od a i b!

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

Ćwiczenie

Dopisać predykat sklej do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

?- sklej([a,b],[c,d],X).
?- sklej([a,b],X,[c,d]).
?- sklej([a,b],X,[a,b,c,d]).
 
?- sklej(A,B,[a,b,c,d,e]).
 
?- sklej([1,2,3],[a,b,c],X).
?- sklej([1,2,3],[a(e),b(f),c(d,g)],X).
 
?- sklej(Przed,[5|Po],[1,2,3,4,5,6,7,8,9]).
?- sklej(_,[A,5,B|_],[1,2,3,4,5,6,7,8,9]).
?- sklej(A,[x,x,x|_],[a,b,x,x,c,x,x,x,d,e]).

Uwaga: dopisać i przetestować predykat:

nalezy1(X,L) :-
	sklej(_,[X|_],L).

Zdefiniować predykat:

ostatni(Element,Lista).

Z użyciem i bez użycia sklej.

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

W praktyce nie byłby tu potrzebny dodatkowy predykat.

Ćwiczenie

Dopisać predykat dodaj do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

?- dodaj(a,[c,d],X).
?- dodaj([a,b],[c,d],X).

usun(X,[X|Reszta],Reszta).
usun(X,[Y|Ogon],[Y|Reszta]) :-
	usun(X,Ogon,Reszta).

Ćwiczenie

Dopisać predykat usun do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

?- usun(a,[a,b,a,c,a,a],X).
?- usun(a,[a,b,c,d],X).
?- usun(c,[a,b,c,d],X).
?- usun(c,X,[a,b,c,d]).
 
?- usun(1,X,[a,b,c,d]).

Proszę znajdywać wszystkie rozwiązania (;).

Uwaga: dopisać i przetestować predykat:

wstaw(X,L,Duza) :-
	usun(X,Duza,L).

Uwaga: dopisać i przetestować predykat:

nalezy2(X,L) :-
	usun(X,L,_).

zawiera(S,L) :-
	sklej(_,L2,L),
	sklej(S,_,L2).

Ćwiczenie

Dopisać predykat zawiera do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

?- zawiera(a,[a,b,c]).
?- zawiera([a],[a,b,c]).
?- zawiera(X,[a,b,c]).
?- zawiera([X],[a,b,c]).
?- zawiera([X,Y],[a,b,c]).
?- zawiera([X,Y,Z],[a,b,c]).

permutacja([],[]).
permutacja([X|L],P) :-
	permutacja(L,L1),
	wstaw(X,L1,P).
 
permutacja2([],[]).
permutacja2(L,[X|P]) :-
	usun(X,L,L1),
	permutacja2(L1,P).

Ćwiczenie

Dopisać predykat permutacja do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

?- permutacja([a,b,c],X).
?- permutacja2([a,b,c],X).

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

Ćwiczenie

Dopisać predykat odwroc do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

?- odwroc([a,b,c,d],X).
?- odwroc([a,b,c,d],[d,c,b,a]).

Napis w Prologu może być reprezentowany przez:

• atom - jest trudny w obróbce,
• listę kodów ASCII znaków,
• listę jednoliterowych atomów.

Reprezentacja przy pomocy listy zwiększa możliwości przetwarzania.

Przydatny predykat:

wypisz([H|T]) :-
	put(H), wypisz(T).
wypisz([]).

Inna sytuacja: Przykład wykorzystania wbudowanych predykatów name i append do przekształcania napisów. Predykat plural(Noun, Pl) - przekształca rzeczownik regularny języka angielskiego z liczby pojedynczej na liczbę mnogą.

plural(Noun, PL) :- 
	name(Noun, L), 
	name(s,T), 
	append(L,T, NL), 
	name(PL, NL).

Ćwiczenie

Sprawdzić i przemyśleć działanie poniższych:

?- write('ala').
?- write('ala ma kota').
?- write("ala").
?- write("ala ma kota").
?- X = 'a', put(X).
?- X = 'ala', put(X).
?- X = "a", put(X).
?- put(65),put(66),put(67).

Dopisać predykaty wypisz i plural do pliku listy-1.pl

Sprawdzić i przemyśleć działanie poniższych:

?- wypisz("ala ma kota").
?- permutacja("abc",X),wypisz(X),nl,fail.
?- wstaw(" ", "abcdefgh",Z),wypisz(Z),nl,fail.

?- plural(day,PL).

• Predykat podany w sekcji odwracanie list, tzw. naiwny, używa predykatu sklej, co powoduje jego nieefektywność. Innym rozwiązaniem jest użycie tzw. akumulatora, w którym przechowujemy budowaną na bieżąco listę. Opis procedury: tutaj

W kolejnych krokach predykat ten buduje listę Accumulator:

  List: [a,b,c,d]  Accumulator: []
  List: [b,c,d]    Accumulator: [a]
  List: [c,d]      Accumulator: [b,a]
  List: [d]        Accumulator: [c,b,a]
  List: []         Accumulator: [d,c,b,a]

Klauzule wyglądają następująco:

odwroc2(L,R) :-
     odwr2(L,[],R).
odwr2([H|T],A,R) :-
     odwr2(T,[H|A],R).
odwr2([],A,A).

Rezultat: Znaczna poprawa efektywności. Przykładowo dla 8-elementowej listy predykat wykorzystujący sklej wykonuje 90 kroków, zaś używający akumulatora - 20. — Weronika Furmańska 2008/10/29 13:33

Dużą bolączką operacji na listach w Prologu (jak też w innych językach programowania, które wymuszają przechodzenie po elementach listy od lewej do prawej, np. Haskell) jest nieefektywność operacji działających na końcu listy. Sztandarowym przykładem takiej operacji jest łączenie dwóch list, vel. predykat sklej/3 implementowany na tych laboratoriach — rezolucja musi w nim przejść kolejno po wszystkich elementach pierwszej listy; złożoność czasowa jest zatem liniowa i przy częstym sklejaniu list znacząco spowalnia działanie programu.

Standardowym rozwiązaniem problemu są listy różnicowe (ang. difference lists), które reprezentują jedną listę jako różnicę między dwiema listami, np. lista

[a,b,c].

może być reprezentowana równoważnie przez wszystkie poniższe pary list:

[a,b,c,d,e],[d,e].
[a,b,c,d,e,f],[d,e,f].
[a,b,c],[].
[a,b,c|[d,e,f,g]],[d,e,f,g].
[a,b,c|[]],[].
[a,b,c|End],End.

Szczególnie interesująca jest ostatnia linijka ze względu na swoją ogólność. Kążdą listę [L] można przedstawić jako parę [L|End],End. Kiedy End jest zmienną bez przypisanej wartości, listę o takiej postaci nazywam otwartą (ang. open list). Z proceduralnego punktu widzenia zmienna End jest „wskaźnikiem” na koniec listy L; unifikując z End inną listę, wstawiamy jej elementy na koniec listy L. Poniżej przedstawiony jest predykat sklej_roznicowo/3, który wykonuje tę operację (uwaga: operator '-' służy tutaj jedynie grupowaniu argumentów; parę [L|End], End zapiszemy jako [L|End] - End.)

sklej_roznicowo(L - End, L2, L) :- 
	End = L2.

Poniżej przykład wywołania predykatu:

?:- sklej_roznicowo([a,b,c|End]-End, [d,e,f|End2]-End2, Wynik).
End = [d, e, f|End2],
Wynik = [a, b, c, d, e, f|End2]-End2.

Predykat ten różni się od tego implementowanego na zajęciach pod względem złożoności obliczeniowa; sklej roznicowe wykonuje zawsze jedynie jedną unifikację, ma więc stałą złożoność obliczeniową. Idąc dalej, jeżeli ustalimy, że argumentami sklej_roznicowo mogą być jedynie listy różnicowe w postaci par L - End, możemy go przepisać do poniższej, interesującej postaci:

sklej_roznicowo(L - End, End - End2, L - End2). 

Poniżej przykład wywołania predykatu:

?:- sklej_roznicowo([a,b,c|End]-End,[d,e,f|End2]-End2,Wynik).
End = [d, e, f|End2],
Wynik = [a, b, c, d, e, f|End2]-End2.

Podczas wywołania Prolog unifikuje koniec pierwszej listy z drugą listą, zapamiętując przy tym koniec drugiej listy — dzięki temu lista wynikowa Wynik w parze z End2 stanowi kolejną listę różnicową, do której łatwo dołożyć kolejne elementy.

Do poczytania:

• Lista różnicowa na en.wikipeda,
• Lista różnicowa w Prologu na en.wikibooks,
• Pytanie o listy różnicowe na Stackoverflow,
• Otwarte i różnicowe listy w ambitnym kursie Prologa

Do przećwiczenia: przepisać wybrany predykat z zajęć (poza sklej/3) na wersję korzystającą z list różnicowych.

— Mateusz Ślażyński 2014/03/17 13:58

Z braku lepszego miejsca tutaj studenci wpisują komentarze natury ogólnej do tego lab.

— Grzegorz J. Nalepa 2008/02/20 14:34