SE/LS/L3
From WikiZMSI
Spis treści |
Listy w Prologu
Lista to ciąg uporządkowanych elementów. Elementy mogą być dowolnego typu. Listy można przedstawić w postaci drzewa. Lista jest strukturą o nazwie ".".
Przykłady list:
[ala] [ala,narty,ksiazki] [head,tail] [a,V,1,[c,s],p(X)] [1,2,3,4]
Sprawdzić w trybie zapytań następujące unifikacje:
[a,V,1,[c,s],p(X)] = [A,B,C,D,E]. [1,2,3,4] = [1|[2,3,4]]. [1,2,3,4] = [1,2|[3,4]]. [1,2,3,4] = [1,2,3|[4]]. [1,2,3,4] = [1,2,3,4,[]]. [1,2,3,4] = [1|2,3,4]. [Head|Tail] = [1,2,3,4]. [Head|Tail] = [[1,1,ala],2,3,4]. [Head|Tail] = [X+Y,x+y]. p([_,_,_,[_|X]]) = p([ala, ma, bardzo, [malego, burego, kotka]]). [a,[]] = [A,B|Rest]. [One] = [two|[]].
Operacje na listach
Sprawdzenie czy element jest na liście (2 argumenty).
Rozważmy następujący problem: Jak mogę sprawdzić, czy dany przedmiot jest na konkretnej liście? Na przykład chcę sprawdzić, czy przedmiot jabłka znajduje się na liście [gruszki, pomidory, jabłka, winogrona]. Jedną z możliwych metod jest, przechodzenie po kolei przez liście, aby sprawdzić, czy możemy znaleźć szukany przedmiot. Z pewnością przedmiot jest na liście jeżeli jest na liście pierwszy, co w Prologu zapiszemy:
element(Przedmiot,[Przedmiot|Reszta]).
W przeciwynym razie jeżeli coś nie jest na początku listy, to musimy sprawdzić, czy nie jest na początku pozostałej listy.
element(Przedmiot,[Inny|Reszta]) :- element[Przedmiot,Reszta].
- Procedure w całości można zapisać: X jest elementem listy L jeżeli X jest głową listy L lub X jest elementem ogona listy L.
element(X,[X|_]). element(X,[_|Ogon]) :- element(X,Ogon).
- Sprawdzić działanie procedury dla przykładów:
element(a,[b,c,[s,a],a]). element(a,[b,c,[s,a]]). element([s,a],[b,c,[s,a]]). element(X,[a,b,c]). element(a, X).
- Istnieje wbudowany predykat działający w podany sposób: member/2
Łączenie list (3 argumenty)
Jeżeli mamy dostępne dwie listy, to możemy połączyć je w jedną. Najprostszą procedurą jest dopisać na końcu listy pierwszej elementy listy drugiej, np [jabłka, gruszki] i [pomidory, papryka] dadzą [jabłka, gruszki,pomidory, papryka]
- Procedura: Jeżeli pierwszy element listy jest pusty [], to drugi i trzeci element muszą być takie same (L = L). Natomiast jeżeli pierwszy element nie jest pusty, to musi posiadać głowę i ogon i głowę dodaje się do elementu trzeciego (lista połączona) jako głowę.
polacz([],L,L). polacz([X|L1],L2,[X|L3]) :- polacz(L1,L2,L3).
- Sprawdzić działanie procedury dla przykładów:
polacz([b,c,[s,a],a],[a],X). polacz([a],[b],[a,b]). polacz(L1,L2,[b,c,[s,a]]).
Ostatni działa jak dekompozycja listy.
- Istnieje wbudowany predykat działający w podany sposób: append/3
Usuwanie z listy (3 argumenty)
Jeżeli elementy jest na liście to go usuwamy. Usuwamy tylko pierwsze wystąpienie poszukiwanego elementu.
- Procedura: Jeżeli X jest w głowie listy, to wynikiem będzie ogon listy. Natomiast jeżeli X jest w ogonie to rekurencyjnie przeszukaj ogon.
usun(X,[X|L1],L1). usun(X,[Y|L2],[Y|L3]) :- usun(X,L2,L3).
- Sprawdzić działanie procedury dla przykładów:
usun(a,[s,a],X). usun(a,[a,b,a,a],X).
Istnieje wiele rozwiązań
usun(a,L,[d,s,e]).
Dodaje element do listy!
- Istnieją wbudowane predykaty usuwające elementy: delete/3 i select/3. Sprawdzić różnicę. Jak użyć select/3 do dodawania elementu do listy?
Podlista z listy (2 argumenty)
- Procedura: Jeżeli S jest podlistą L, to L może być zdekomponowana na na dwie listy L1 i L2 i L2 może być zdekomponowana na S i L3.
podlista(S,L) :- append(L1,L2,L), append(S,L3,L2).
- Uwaga: L1 i L3 mogą być zmiennymi anonimowymi
- Sprawdzić działanie procedury dla przykładów:
podlista([a,b],[a,b,c,d]). podlista(X,[a,b,c,d]).
- Istnieje wbudowany predykat działający w podany sposób: sublist/2, ale tylko w gprologu
Inne
Sprawdzić dostępne wbudowane predykaty dotyczące list poleceniem: apropos(list).
Zadania na listach
- Lista ma zawierać miesiące. Zdefiniować predykat wyświetlający wszystkie miesiące przed i po podanym nazwą miesiącu. Należy wykorzystać append/3. Rozwiązanie
- Lista ma zawierać miesiące. Zdefiniować predykat wyświetlający jeden miesiąc przed i jeden po podanym nazwą miesiącu. Należy wykorzystać append/3. Rozwiązanie
- Dla podanej listy wyświetl tylko 3 początkowe elementy. Rozwiązanie
- Dla podanej listy wyświetl tylko 3 ostatnie elementy. Rozwiązanie
- Zdefiniować predykat element listy (member) za pomocą append/3. Rozwiązanie
- Zdefiniować predykaty: parzysta(Lista) i nieparzysta(Lista), które zwrócą wartość true, jeżeli argument jest odpowiednio listą z parzystą lub nieparzystą liczbą elementów. np. nieparzysta([a,b,c,d]). daje odpowiedź no, a parzysta([a,b,c,d]).daje odpowiedź yes. Rozwiązanie
- Zdefiniować relację odwrotna(Lista,Lista_odwrotna), zmieniająca kolejność elementów, np. odwrotna([a,b,c,d],[d,c,b,a]). Rozwiązanie
- Zdefiniować predykat palindrom(Lista). Lista jest palindromem, jeżeli czytając ją wspak uzyskamy taką samą kolejność elementów. Rozwiązanie
- Zdefiniować relację shift(Lista1, Lista2) przesuwającą pierwszy element lisy na jej koniec. Rozwiązanie
- Zdefiniować relację slownie(Lista1, lista2) podającą słowne odpowiedniki liczb zadanych listą, np. slownie([1,3,4],Y). Y=[jeden, trzy, cztery]. Wykorzystaj fakty slowo(1,jeden)., slowo(2,dwa). itd.. Rozwiązanie
- Zdefiniować predykat maxlista(Lista, Max) znajdującą największą wartość w liście liczbowej. Rozwiązanie
- Zdefiniować predykat sumalisty(Lista,Suma) obliczający sumę elementów listy, jeżeli są liczbami. Rozwiązanie
- Zdefiniować predykat lista_rosnaca(Lista), który daje odpowiedź yes jeżeli kolejność elementów jest niemalejąca. Rozwiązanie
Zadanie domowe
- Do przeczytania: W.F. Clocksin i C.S. Mellish. "Prolog. Programowanie." - Rozdział 3.
Zadania dodatkowe
1. Znajdź ostatni element z listy. Przykład:
?- ostatni(X,[a,b,c,d]). X = d
2. Znajdź przedostatni element z listy. Przykład:
?- przedostatni(X,[a,b,c,d]). X = c
3. Znajdź k-ty element listy. Przykład:
?- katyelement(X,[a,b,c,d,e],3). X = c
4. Znajdź elementy listy pierwszej, które nie występują w drugiej zadanej liście. Przykład:
?-diff([a,b,c,d],[b,d,e,f],[a,c]). Yes
5. Znajdź liczbę elementów w liście. Przykład:
?- ile([a,b,c,d,e],X). X = 5
