Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:prolog_lab:listy1 [2014/03/17 15:43] msl [Listy różnicowe] Formatowania dalszy ciąg. |
pl:prolog:prolog_lab:listy1 [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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: | ||
| - | |||
| - | <code prolog> | ||
| - | [a,b,c] | ||
| - | [2,4,6,ala,ma,kota] | ||
| - | [] | ||
| - | </code> | ||
| - | |||
| - | 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.: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- [X|Y]=[a,b,c,d]. | ||
| - | |||
| - | X = a | ||
| - | Y = [b, c, d] ; | ||
| - | </code> | ||
| - | |||
| - | 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: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- [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 ; | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Proszę sprawdzić poniższe unifikacje: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- X=[a,b,c]. | ||
| - | ?- [X|Y]=[a,b,c]. | ||
| - | ?- [[a,b],c]=[X,Y]. | ||
| - | ?- [a(b),c(X)]=[Z,c(a)]. | ||
| - | ?- [X|Y]=[a]. | ||
| - | </code> | ||
| - | |||
| - | Wybieranie elementu: | ||
| - | |||
| - | <code prolog> | ||
| - | trzeci([A,B,C|Reszta],C). | ||
| - | </code> | ||
| - | |||
| - | Zdefiniować predykat porównujący 2 wybrane elementy listy, np. 3. i 4. | ||
| - | |||
| - | Przykład użycia: | ||
| - | <code prolog> | ||
| - | ?- porownaj([a,b,c,d]). | ||
| - | No | ||
| - | ?- porownaj([a,b,c,c]). | ||
| - | Yes | ||
| - | </code> | ||
| - | |||
| - | Zdefiniować predykat zamieniający 2 wybrane elementy listy, np. 3. i 4. | ||
| - | <code prolog> | ||
| - | ?- zamien([a,b,c,d],X). | ||
| - | X=[a,b,d,c] | ||
| - | Yes | ||
| - | </code> | ||
| - | |||
| - | ===== -. Przynależność do listy ===== | ||
| - | |||
| - | <code prolog> | ||
| - | nalezy(X,[X|_]). | ||
| - | nalezy(X,[_|Yogon]) :- | ||
| - | nalezy(X,Yogon). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Dopisać predykat ''nalezy'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- nalezy(c,[a,b,c,d]). | ||
| - | ?- nalezy(x,[a,b,c,d]). | ||
| - | ?- nalezy(X,[a,b,c,d]). | ||
| - | ?- nalezy(x,a). | ||
| - | ?- nalezy(X,a). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | ===== -. Liczenie elementów ===== | ||
| - | |||
| - | <code prolog> | ||
| - | dlugosc([],0). | ||
| - | dlugosc([_|Ogon],Dlug) :- | ||
| - | dlugosc(Ogon,X), | ||
| - | Dlug is X+1. | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Dopisać predykat ''dlugosc'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- dlugosc([a,b,c],X). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | ===== -. Rekurencyjna analiza list ===== | ||
| - | |||
| - | (źródło: [[http://cs.union.edu/~striegnk/learn-prolog-now/html/node35.html#sec.l4.rdal|LearnPrologNow]]) | ||
| - | |||
| - | <code prolog> | ||
| - | a2b([],[]). | ||
| - | a2b([a|Ta],[b|Tb]) :- | ||
| - | a2b(Ta,Tb). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Dopisać predykat ''a2b'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- 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). | ||
| - | </code> | ||
| - | |||
| - | Uwaga: ten predykat robi "coś ciekawego" tylko na listach zaczynających się od ''a'' i ''b''! | ||
| - | |||
| - | |||
| - | ===== -. Sklejanie list ===== | ||
| - | |||
| - | <code prolog> | ||
| - | sklej([],X,X). | ||
| - | sklej([X|L1],L2,[X|L3]) :- | ||
| - | sklej(L1,L2,L3). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Dopisać predykat ''sklej'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- 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]). | ||
| - | </code> | ||
| - | |||
| - | Uwaga: dopisać i przetestować predykat: | ||
| - | |||
| - | <code prolog> | ||
| - | nalezy1(X,L) :- | ||
| - | sklej(_,[X|_],L). | ||
| - | </code> | ||
| - | |||
| - | Zdefiniować predykat: | ||
| - | |||
| - | ostatni(Element,Lista). | ||
| - | |||
| - | Z użyciem i bez użycia ''sklej''. | ||
| - | |||
| - | |||
| - | ===== -. Dodawanie elementów ===== | ||
| - | |||
| - | <code prolog> | ||
| - | dodaj(X,L,[X|L]). | ||
| - | </code> | ||
| - | |||
| - | 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: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- dodaj(a,[c,d],X). | ||
| - | ?- dodaj([a,b],[c,d],X). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | ===== -. Usuwanie elementów ===== | ||
| - | |||
| - | <code prolog> | ||
| - | usun(X,[X|Reszta],Reszta). | ||
| - | usun(X,[Y|Ogon],[Y|Reszta]) :- | ||
| - | usun(X,Ogon,Reszta). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Dopisać predykat ''usun'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- 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]). | ||
| - | </code> | ||
| - | |||
| - | Proszę znajdywać wszystkie rozwiązania (;). | ||
| - | |||
| - | Uwaga: dopisać i przetestować predykat: | ||
| - | |||
| - | <code prolog> | ||
| - | wstaw(X,L,Duza) :- | ||
| - | usun(X,Duza,L). | ||
| - | </code> | ||
| - | |||
| - | Uwaga: dopisać i przetestować predykat: | ||
| - | |||
| - | <code prolog> | ||
| - | nalezy2(X,L) :- | ||
| - | usun(X,L,_). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | ===== -. Zawieranie list ===== | ||
| - | |||
| - | <code prolog> | ||
| - | zawiera(S,L) :- | ||
| - | sklej(_,L2,L), | ||
| - | sklej(S,_,L2). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Dopisać predykat ''zawiera'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- 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]). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | ===== -. Permutacje list ===== | ||
| - | |||
| - | <code prolog> | ||
| - | permutacja([],[]). | ||
| - | permutacja([X|L],P) :- | ||
| - | permutacja(L,L1), | ||
| - | wstaw(X,L1,P). | ||
| - | |||
| - | permutacja2([],[]). | ||
| - | permutacja2(L,[X|P]) :- | ||
| - | usun(X,L,L1), | ||
| - | permutacja2(L1,P). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Dopisać predykat ''permutacja'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- permutacja([a,b,c],X). | ||
| - | ?- permutacja2([a,b,c],X). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | ===== -. Odwracanie list ===== | ||
| - | |||
| - | <code prolog> | ||
| - | odwroc([],[]). | ||
| - | odwroc([H|T],L) :- | ||
| - | odwroc(T,R), | ||
| - | sklej(R,[H],L). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Dopisać predykat ''odwroc'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- odwroc([a,b,c,d],X). | ||
| - | ?- odwroc([a,b,c,d],[d,c,b,a]). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | ===== -. 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: | ||
| - | |||
| - | <code prolog> | ||
| - | wypisz([H|T]) :- | ||
| - | put(H), wypisz(T). | ||
| - | wypisz([]). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | 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ą. | ||
| - | <code prolog> | ||
| - | plural(Noun, PL) :- | ||
| - | name(Noun, L), | ||
| - | name(s,T), | ||
| - | append(L,T, NL), | ||
| - | name(PL, NL). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- 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). | ||
| - | </code> | ||
| - | |||
| - | Dopisać predykaty ''wypisz'' i ''plural'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- wypisz("ala ma kota"). | ||
| - | ?- permutacja("abc",X),wypisz(X),nl,fail. | ||
| - | ?- wstaw(" ", "abcdefgh",Z),wypisz(Z),nl,fail. | ||
| - | </code> | ||
| - | |||
| - | |||
| - | <code prolog> | ||
| - | ?- plural(day,PL). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | |||
| - | ===== Dla Zainteresowanych ===== | ||
| - | |||
| - | ==== 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: | ||
| - | <code prolog> | ||
| - | odwroc2(L,R) :- | ||
| - | odwr2(L,[],R). | ||
| - | odwr2([H|T],A,R) :- | ||
| - | odwr2(T,[H|A],R). | ||
| - | odwr2([],A,A). | ||
| - | </code> | ||
| - | |||
| - | 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 <code prolog>[a,b,c].</code> może być reprezentowana równoważnie przez wszystkie poniższe pary list: | ||
| - | <code prolog> | ||
| - | [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. | ||
| - | </code> | ||
| - | 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.'') | ||
| - | <code prolog> | ||
| - | sklej_roznicowo(L - End, End, L). | ||
| - | </code> | ||
| - | Poniżej przykład wywołania predykatu: | ||
| - | <code prolog> | ||
| - | ?:- sklej_roznicowo([a,b,c|End]-End,[d,e,f],Wynik). | ||
| - | End = [d, e, f], | ||
| - | Wynik = [a, b, c, d, e, f]. | ||
| - | </code> | ||
| - | |||
| - | Predykat ten różni się od tego implementowanego na zajęciach pod względem złożoności obliczeniowej; ''sklej_roznicowe'' 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: | ||
| - | |||
| - | <code prolog> | ||
| - | sklej_roznicowo(L - End, End - End2, L - End2). | ||
| - | </code> | ||
| - | Poniżej przykład wywołania predykatu: | ||
| - | <code prolog> | ||
| - | ?:- 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. | ||
| - | </code> | ||
| - | |||
| - | 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: == | ||
| - | |||
| - | * [[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]]. | ||
| - | |||
| - | ==Do przećwiczenia: == | ||
| - | |||
| - | * przepisać wybrany predykat z zajęć (poza ''sklej/3'') na wersję korzystającą z list różnicowych; | ||
| - | * zastanowić się, jakie przewagi ma ''sklej/3'' nad ''sklej_roznicowo/3''. | ||
| - | |||
| - | --- //[[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// | ||
