Kurs Inżynierii Wiedzy - Politechnika Krakowska
1
Ćwiczenia – Listy
1. Cel ćwiczenia
Celem tych laboratoriów jest zapoznanie się i nabycie, praktycznych umiejętności wykorzystania list
w języku PROLOG. Ważne jest, abyś przed wykonaniem dwiczeo laboratoryjnych zapoznał się
dokładnie z wykładem opisującym dane zagadnienia.
2. Listy
Listy to jedne z najpopularniejszych struktur danych. W PROLOGu jest to ciąg uporządkowanych
elementów – termów, stałych, zmiennych, struktur czy innych list – zawartych pomiędzy
kwadratowymi nawiasami (np. [a,b,c]).
W PROLOGu, jak w każdym typowym języku programowania, istnieje możliwośd tworzenia list
pustych. Lista taka składa się tylko i wyłącznie z pustych nawiasów (*+).
Jak wspomniano już w wykładach, każda „typowa” lista (poza listą pustą) składa się z „głowy” i z
„ogona”. Głowa i ogon takiej listy są argumentami funktora o nazwie (.), więc aby zapisad listę, z
jednym argumentem np. „a” można zapisad jako strukturę (a.*+).
Przykłady list:
Lista
Głowa
Ogon
[]
Brak
Brak
[a, b, c]
a
[b, c]
[[bury, kot], mruczy]
[bury,kot]
[mruczy]
[bury, [kot, mruczy]]
bury
[kot, mruczy]
[bury, [kot, mruczy], cicho]
bury
[[kot, mruczy], cicho]
[X+Y, x+y]
X+Y
[x+y]
2.1 Definicja listy z dowolnymi liczbami.
Zacznijmy od stworzenia prostej listy z dowolnymi liczbami. Otwieramy nasz edytor i wpisujemy
poniższą instrukcję:
liczby([4, 20, 19, 11, 2, 5, 10]).
Argumentem powyższego predykatu jest lista, której elementami są liczby
4,20,19,11,2,5,10.
2.2 Wyświetlanie elementów listy.
Mamy już zdefiniowaną prostą listę. Teraz musimy się nauczyd jak wykonywad na liście proste
operacje. Na początek wyświetlimy jej pierwszy element. Wpisujemy:
liczby([X|_]).
Kurs Inżynierii Wiedzy - Politechnika Krakowska
2
Program powinien nam odpowiedzied:
X = 4
1 Solution
Przeanalizujmy wpisaną linijkę kodu. Każda lista składa się z głowy i ogona, jak już zdążyliśmy sobie
przypomnied. Każdą listę możemy zapisad jako
L=([H|T]).
( list=([head|tail]). ) tak więc zapis:
liczby([X|_]).
oznacza: wyświetl głowę listy, czyli pierwszy jej element.
Musimy pamiętad, że elementy listy to nie tylko liczby, ale także atomy, ciągi znaków czy struktury.
Aby natomiast, wyświetlid wszystkie elementy naszej listy, oprócz pierwszego:
liczby([_|X]).
Analogicznie możemy wyświetlad:
liczby([X|Y]). – całą listę,
liczby([X,Y|_]). – dwa pierwsze elementy listy,
itp.
2.3 Wyświetlanie n-tego elementu listy.
Aby wyświetlid n-ty element naszej listy, trzeba zastosowad rekurencje. Poniższy sposób działa tak, że
obcina pierwszy element listy n razy. Jeżeli pozostanie już tylko jeden element, jest on wyświetlany,
koocząc działanie reguły. Operator
is
powoduje przypisanie zmiennej zadanej wartości.
nty_element([X|_], 1) :- write(X), nl.
nty_element([X|Y], N) :- N > 1, N1 is N - 1, nty_element(Y, N1).
Aby wyświetlid 5-ty element listy wystarczy wpisad:
liczby(X),nty_element(X,5).
2.4 Łączenie list.
Chcąc złączyd dwie listy należy do naszego programu dopisad dwie poniższe linijki kodu:
dolacz([], L, L).
dolacz([H|T], L, [H|U]) :- dolacz(T, L, U).
Reguły rekurencyjne wykonujące operacje na listach formułuj według następującego schematu:
wyraź wszystkie listy będące argumentami konkluzji reguły, w formie *H|T+,
nadaj takie same nazwy pierwszym elementom (H) list, których odpowiednie elementy
muszą byd jednakowe,
nadaj takie same nazwy pozostałym elementom (T) list, których odpowiednie elementy
muszą byd jednakowe,
Kurs Inżynierii Wiedzy - Politechnika Krakowska
3
sformułuj wymagane relacje pomiędzy pozostałymi elementami rozpatrywanych list,
dla list, dla których nie jest konieczne przedstawienie w formie *H|T+, uprośd ich zapis
stosując pojedynczą zmienną,
sformułuj predykat dla „skrajnego” wywołania reguły.
1
1
mgr inz. Jacek Ptaszny – „Struktury, listy i rekurencja w języku Prolog”