Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:prolog_lab:listy1 [2009/03/03 23:23] ikaf link corrected sequel |
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: | ||
| - | |||
| - | trzeci([A,B,C|Reszta],C). | ||
| - | |||
| - | Zdefiniować predykat porównujący 2 wybrane elementy listy, np. 3. i 4. | ||
| - | |||
| - | Zdefiniować predykat zamieniający 2 wybrane elementy listy, np. 3. i 4. | ||
| - | |||
| - | |||
| - | ===== -. 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" 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> | ||
| - | |||
| - | 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> | ||
| - | |||
| - | |||
| - | **Ć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ć predykat ''wypisz'' 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> | ||
| - | |||
| - | |||
| - | ===== 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://www.coli.uni-saarland.de/~kris/learn-prolog-now/html/node51.html#subsec.l6.reverse.acc | ||
| - | 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// | ||
| - | |||
| - | ===== 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// | ||
