✎ pl:prolog:prolog_lab:listy1 [aiWiki]

Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== 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.

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//