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ł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:
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:
cuboid
tak, żeby można było sprecyzować jego pozycję w przestrzenicuboids
, który przyjmuje listę współrzędnych i rysuje w nich sześciany o zadanej długości bokucuboids
należy zamodelować złożony obiekt ze świata Minecraftanimation.pl
należy wprawić krowę w ruch sinusoidalny, imitujący kota z filmuPytania:
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.
sklej_roznicowo/3
;sklej/3
predykatem sklej_roznicowo/3
w predykatach zaimplementowanych na zajęciach;sklej/3
nad sklej_roznicowo/3
;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