To jest stara wersja strony!
LAB: Praca z listami w Prologu (cz. 1)
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]).
No
?- porownaj([a,b,c,c]).
Yes
Zdefiniować predykat zamieniający 2 wybrane elementy listy, np. 3. i 4.
?- zamien([a,b,c,d],X).
X=[a,b,d,c]
Yes
2. 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).
3. 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).
4. Rekurencyjna analiza list
(ź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
!
5. 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
.
6. 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).
7. 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,_).
8. 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]).
9. 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).
10. 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]).
11. Dzielenie list
podziel(L,Idx,L1,L2):-
Idx >= 0,
dlugosc(L,Dlugosc),
Dlugosc1 is Idx,
Dlugosc2 is Dlugosc - Idx,
Dlugosc2 >= 0,
dlugosc(L1,Dlugosc1),
dlugosc(L2,Dlugosc2),
sklej(L1,L2,L),!.
Ćwiczenie
Dopisać predykat podziel
do pliku listy-1.pl
Sprawdzić i przemyśleć działanie poniższych:
?- podziel([a,b,c,d],4,L1,L2).
?- podziel([a,b,c,d],0,L1,L2).
?- podziel([a,b,c,d],3,L1,L2).
12. Listy a napisy
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([]).
Ć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ć predykat wypisz
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.
Dla Zainteresowanych
Efektywność odwracania list
Predykat podany w sekcji
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:
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. — Weronika Furmańska 2008/10/29 13:33
Komentarze
Z braku lepszego miejsca tutaj studenci wpisują komentarze natury ogólnej do tego lab.
— Grzegorz J. Nalepa 2008/02/20 14:34