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 = 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:

  • 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:

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. 8-)

Grzegorz J. Nalepa 2008/02/20 14:34

pl/prolog/prolog_lab/listy1.1256722794.txt.gz · ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0