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]).
false
?- porownaj([a,b,c,c]).
true

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

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

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).

Zastanówmy się nad próbą implementacji prostej gry typu Minecraft. Kluczowym elementem gry jest silnik wokselowy, który odpowiada za renderowania ogromnego świata przy użyciu prostych klocków zwanych wokselami. Zaczniemy od rysowania przykładowego woksela. Proszę uruchomić program cuboid.pl (wymagane XPCE) i przeanalizować jego działanie.

?- cuboid(2,2,2).

Następnie proszę zapoznać się z kodem odpowiadającym za animację animation.pl:

?- sm.

Zadania:

1. Przerobić predykat cuboid tak, żeby można było sprecyzować jego pozycję w przestrzeni
2. Napisać predykat cuboids, który przyjmuje listę współrzędnych i rysuje w nich sześciany o zadanej długości boku
3. Przy pomocy predykatu cuboids należy zamodelować złożony obiekt ze świata Minecraft
4. Bazując na kodzie z animation.pl należy wprawić krowę w ruch sinusoidalny, imitujący kota z filmu
5. [Dla odważnych] dodać do animacji dźwięk podobny do tego z filmu

Pytania:

1. Czy rozsądne jest rysowanie wszystkich klocków? Jak wykryć, które klocki są widoczne z perspektywy gracza? Pomocny może okazać się link
2. Czy możliwe jest zrobienie w podobny sposób imitacji poniższego filmu?

• 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. Różnicę rozumiemy jako odjęcie elementów z drugiej listy od końca pierwszej listy, 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ść. Każdą listę [L] można przedstawić jako parę [L|End],End. Kiedy End jest zmienną bez przypisanej wartości, listę o takiej postaci nazywamy 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, End, L).

Poniżej przykład wywołania predykatu:

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

Predykat ten różni się od tego implementowanego na zajęciach pod względem złożoności obliczeniowej; sklej_roznicowo nigdy nie wchodzi w rekurencję, wykonuje 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.

• przetestować predykat sklej_roznicowo/3;
• spróbować zastąpić predykat sklej/3 predykatem sklej_roznicowo/3 w predykatach zaimplementowanych na zajęciach;
• zastanowić się, jakie przewagi ma sklej/3 nad sklej_roznicowo/3;
• przepisać wybrany predykat z zajęć (poza sklej/3) na wersję korzystającą z list różnicowych.

• 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.

— 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