|
|
pl:prolog:prolog_lab:listy1 [2010/03/17 18:22] ikaf |
pl:prolog:prolog_lab:listy1 [2019/06/27 15:50] |
====== 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> | |
===== -. Dzielenie list ===== | |
| |
<code prolog> | |
podziel(L,Idx,L1,L2):- | |
Idx >= 0, | |
dlugosc(L,Dlugosc), | |
Dlugosc1 = Idx, | |
Dlugosc2 is Dlugosc - Idx, | |
Dlugosc2 >= 0, | |
dlugosc(L1,Dlugosc1), | |
dlugosc(L2,Dlugosc2), | |
sklej(L1,L2,L),!. | |
</code> | |
| |
**Ćwiczenie** | |
| |
Dopisać predykat ''podziel'' do pliku //listy-1.pl// | |
| |
Sprawdzić i przemyśleć działanie poniższych: | |
| |
<code prolog> | |
?- podziel([a,b,c,d],4,L1,L2). | |
?- podziel([a,b,c,d],0,L1,L2). | |
?- podziel([a,b,c,d],3,L1,L2). | |
</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://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// | |
| |
===== 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// | |
| |
| |