====== LAB: Praca z listami w Prologu (cz. 1) ======
===== -. Notacja list =====
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
===== -. Przynależność do listy =====
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).
===== -. Liczenie elementów =====
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).
===== -. Rekurencyjna analiza list =====
(źródło: [[http://cs.union.edu/~striegnk/learn-prolog-now/html/node35.html#sec.l4.rdal|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''!
===== -. Sklejanie list =====
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''.
===== -. Dodawanie elementów =====
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).
===== -. Usuwanie elementów =====
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,_).
===== -. Zawieranie list =====
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]).
===== -. Permutacje list =====
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).
===== -. Odwracanie list =====
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]).
===== -. Listy a napisy =====
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).
===== Dla Zainteresowanych =====
==== Minecraft ====
Zastanówmy się nad próbą implementacji prostej gry typu [[http://pl.wikipedia.org/wiki/Minecraft|Minecraft]]. Kluczowym elementem gry jest silnik wokselowy, który odpowiada za renderowania ogromnego świata przy użyciu prostych klocków zwanych [[http://pl.wikipedia.org/wiki/Woksel|wokselami]]. Zaczniemy od rysowania przykładowego woksela. Proszę uruchomić program {{:pl:prolog:prolog_lab:cuboid.pl|}} (wymagane XPCE) i przeanalizować jego działanie.
?- cuboid(2,2,2).
Następnie proszę zapoznać się z kodem odpowiadającym za animację {{:pl:prolog:prolog_lab:animation.pl|}}:
?- sm.
Zadania:
- Przerobić predykat ''cuboid'' tak, żeby można było sprecyzować jego pozycję w przestrzeni
- Napisać predykat ''cuboids'', który przyjmuje listę współrzędnych i rysuje w nich sześciany o zadanej długości boku
- Przy pomocy predykatu ''cuboids'' należy zamodelować [[http://i.ytimg.com/vi/u1bX8kEy0pg/maxresdefault.jpg?|złożony obiekt ze świata Minecraft]]
- Bazując na kodzie z ''animation.pl'' należy wprawić krowę w ruch sinusoidalny, imitujący [[https://www.youtube.com/watch?v=QH2-TGUlwu4|kota z filmu]]
- [Dla odważnych] dodać do animacji [[https://archive.org/details/nyannyannyan|dźwięk]] podobny do tego z [[https://www.youtube.com/watch?v=QH2-TGUlwu4|filmu]]
Pytania:
- Czy rozsądne jest rysowanie wszystkich klocków? Jak wykryć, które klocki są widoczne z perspektywy gracza? Pomocny może okazać się [[http://et1337.com/2015/02/18/the-poor-mans-voxel-engine/#|link]]
- Czy możliwe jest zrobienie w podobny sposób imitacji poniższego [[http://goo.gl/YroZm|filmu]]?
==== Efektywność odwracania list ====
* Predykat podany w sekcji [[#odwracanie_list|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: [[http://cs.union.edu/~striegnk/learn-prolog-now/html/node51.html#subsec.l6.reverse.acc|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. --- //[[ikaf@student.agh.edu.pl|Weronika Furmańska]] 2008/10/29 13:33//
==== Listy różnicowe ====
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.
== Do przećwiczenia: ==
* 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.
== Do poczytania: ==
* [[http://en.wikipedia.org/wiki/Difference_list|Lista różnicowa na en.wikipeda]];
* [[http://en.wikibooks.org/wiki/Prolog/Difference_Lists|Lista różnicowa w Prologu na en.wikibooks]];
* [[http://stackoverflow.com/a/20441480|Pytanie o listy różnicowe na Stackoverflow]];
* [[http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html|Otwarte i różnicowe listy w ambitnym kursie Prologa]].
--- //[[mateusz.slazynski@agh.edu.pl|Mateusz Ślażyński]] 2014/03/17 13:58//
===== Komentarze =====
Z braku lepszego miejsca tutaj studenci wpisują komentarze natury ogólnej do tego lab. 8-)
--- //[[gjn@agh.edu.pl|Grzegorz J. Nalepa]] 2008/02/20 14:34//