[[
✎ pl:prolog:prolog_lab:listy1
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
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 is 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//
pl/prolog/prolog_lab/listy1.1237294908.txt.gz
· ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry