To jest stara wersja strony!
3 LAB: Praca z listami w Prologu
WPROWADZENIE
Temat: Notacja list
Lista to uporządkowany zbiór elementów. Elementem może być dowolna struktura danych w Prologu.
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ą
Listę 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 ;
Temat: Przynależność do listy
nalezy(X,[X|_]).
nalezy(X,[_|Yogon]) :-
nalezy(X,Yogon).
Temat: Liczenie elementów
dlugosc([],0).
dlugosc([_|Ogon],Dlug) :-
dlugosc(Ogon,X),
Dlug is X+1.
Temat: Sklejanie list
sklej([],X,X).
sklej([X|L1],L2,[X|L3]) :-
sklej(L1,L2,L3).
Temat: Dodawanie elementów
dodaj(X,L,[X|L]).
W praktyce nie byłby tu potrzebny dodatkowy predykat.
Temat: Usuwanie elementów
usun(X,[X|Reszta],Reszta).
usun(X,[Y|Ogon],[Y|Reszta]) :-
usun(X,Ogon,Reszta).
Temat: Zawieranie list
zawiera(S,L) :-
sklej(_,L2,L),
sklej(S,_,L2).
Temat: 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).
Temat: Odwracanie listy
odwroc([],[]).
odwroc([H|T],L) :-
odwroc(T,R),
sklej(R,[H],L).
Temat: 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([]).
ĆWICZENIA
3.1 Ćwiczenie: Notacja list
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 wybranego 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.
3.2 Ćwiczenie: Przynależność do listy
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.3 Ćwiczenie: Liczenie elementów
Dopisać predykat dlugosc
do pliku listy-1.pl
Sprawdzić i przemyśleć działanie poniższych:
?- dlugosc([a,b,c],X).
3.4 Ćwiczenie: Sklejanie list
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
.
3.5 Ćwiczenie: Dodawanie elementów
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).
3.6 Ćwiczenie: Usuwanie elementów
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]).
Uwaga: dopisać i przetestować predykat:
wstaw(X,L,Duza) :-
usun(X,Duza,L).
Uwaga: dopisać i przetestować predykat:
nalezy2(X,L) :-
usun(X,L,_).
3.7 Ćwiczenie: Zawieranie list
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]).
3.8 Ćwiczenie: Permutacje list
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).
3.9 Ćwiczenie: Odwracanie listy
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]).
3.10 Ćwiczenie: Listy a napisy
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.
3.11 Ćwiczenie: Zadania do zrealizowania
1. zadać cel powodujący usunięcie 3 ostatnich elementów listy L, w wyniku powstaje lista L1, użyć sklej
.
2. zadać cel powodujący usunięcie 3 pierwszych elementów listy L, w wyniku powstaje lista L1, użyć sklej
.
3. zadać cel powodujący usunięcie 3 pierwszych i ostatnich elementów listy L, w wyniku powstaje lista L2, użyć sklej
.
4. zdefiniować predykat ostatni1(E,L)
, gdzie E to ostatni element listy L, użyć sklej
(predykat nie jest rekurencyjny).
5. j.w., ostatni2(E,L)
, tylko bez sklej
(predykat jest rekurencyjny).
6. zdefiniować parę komplementarnych predykatów nieparzysta(L)
oraz parzysta(L)
wypisujących listy o odpowiednio nie/parzystej długości.
7. zdefiniować predykat palindrom(L)
, L jest palindromem, jeżeli czyta się tak samo od przodu i tyłu, np. [a,l,a]
, [m,a,d,a,m]
. (podpowiedź: można nie/użyć odwroc
.)
8. zdefiniować predykat przesun(L1,L2)
, gdzie L2, jest przesuniętą rotacyjnie o jeden element L1, np.:
?- przesun([1,2,3,4,5,6,7,8],X),przesun(X,Y),przesun(Y,Z).
X = [2, 3, 4, 5, 6, 7, 8, 1]
Y = [3, 4, 5, 6, 7, 8, 1, 2]
Z = [4, 5, 6, 7, 8, 1, 2, 3]
9. zdefiniować predykat przeloz(L1,L2)
, który zamienia listę liczb (max. 0-9), na listę słów:
?- przeloz([1,4,7],X).
X = [jeden, cztery, siedem] ;
?- przeloz(A,[dwa,osiem,zero]).
A = [2, 8, 0] ;
posługując się faktami:
znaczy(0,zero). znaczy(1,jeden).
znaczy(2,dwa). znaczy(3,trzy).
znaczy(4,cztery). znaczy(5,piec).
znaczy(6,szesc). znaczy(7,siedem).
znaczy(8,osiem). znaczy(9,dziewiec).
Podpowiedź: predykat ma być rekurencyjny.
10. zdefiniować predykat podzbior(L,Z)
, który sprawdza, czy Z zawiera się w L, oraz wypisuje wszystkie możliwe podzbiory L (jeżeli Z jest niewiadoma).
?- podzbior([a,b,c],[c]).
Yes
?- podzbior([a,b,c],[a,c]).
Yes
?- podzbior([a,b,c],X).
X = [a, b, c] ;
X = [a, b] ;
X = [a, c] ;
X = [a] ;
X = [b, c] ;
X = [b] ;
X = [c] ;
X = []
11. zdefiniować predykat podziel(L,L1,L2)
, który dzieli listę L, na dwa fragmenty L1 i L2, mniej więcej równej długości (z dokładnością do jednego el.), np.:
?- podziel([],X,Y).
X = []
Y = [] ;
?- podziel([1],X,Y).
X = [1]
Y = [] ;
?- podziel([1,2],X,Y).
X = [1]
Y = [2] ;
?- podziel([1,2,3],X,Y).
X = [1, 3]
Y = [2] ;
?- podziel([1,2,3,4],X,Y).
X = [1, 3]
Y = [2, 4] ;
?- podziel([1,2,3,4,5],X,Y).
X = [1, 3, 5]
Y = [2, 4] ;
?- podziel([1,2,3,4,5,6,7,8],X,Y).
X = [1, 3, 5, 7]
Y = [2, 4, 6, 8] ;
12. zdefiniować predykat splaszcz
, który zamienia dowolnie zagnieżdżoną listę, w listę płaską (której el. nie są listami). (podstawowe rozwiązanie działa bez nawrotów - nie należy naciskać ;
)
?- splaszcz([[a],b,c],X).
X = [a, b, c]
?- splaszcz([[a],[b,[d]],c],X).
X = [a, b, d, c]
?- splaszcz([a,b,c],X).
X = [a, b, c]
?- splaszcz(a,X).
X = [a]
Komentarze
Z braku lepszego miejsca tutaj studenci wpisują komentarze natury ogólnej do tego lab.
— Grzegorz J. Nalepa 2008/02/20 14:34
Efektywność odwracania list
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. (WF)
Bardzo cenna uwaga! Nie pokazujemy akumulatorów, bo mamy mało czasu. Nie zmienia to faktu, że to akurat warto by dodać do części
Jeśli chcesz wiedzieć więcej – GJN
Uwaga techniczna: akcja „niewidzialna ręka” była modna, ale teraz można się podpisywać :) –GJN