1 Karolina Supera Michał Krajewski

2 Struktura w formie drzewa Funktor jest węzłem Składniki struktur są gałęziami W strukturze możemy zagnieżdżać inne struktury Przykład : rodzice(karol, elżbieta, filip): rodzice karol elżbieta filip

3 Przykład: struktura: a+b*c czyli: +(a.*(b,c)) + a * b c

4 Listy – szczególny przypadek struktur Ciąg uporządkowanych elementów o dowolnej długości Kolejność jest ważna Elementami mogą być: stałe, zmienne, struktury, inne listy Lista pusta: [ ] Składowe listy (argumenty funktora) : głowa i ogon Ogon – koniec listy zapisywany jako pusta lista Lista zawierająca pojedynczy element a:.(a.[ ])

5 . a [ ]

6 Lista składająca się z atomów a,b,c.(a,.(b,.(c,[ ]))). a. b. c [ ]

7 Elementami listy mogą być dowolne wartości, w szczególności mogą być to listy.(.(a,b),.(c),d,[ ]) [["a","b"],["c"],"d", []] W powyższym przykładzie, mamy do czynienia z listą zawierającą cztery elementy – pierwszym jest dwuelementowa lista ["a","b"], drugim – jednoelementowa lista ["c"], trzecim – wartość "d", zaś czwartym – lista pusta [].

8 Przykładowo, predykat może zostać zdefiniowany jako: domain(X, ["maly", "duzy"]). domain(Y, ["czerwony", "zielony", "niebieski"]). domain(Z, ["kwadrat", "trojkat"]). pred(X, "czerwony", "trojkat"). pred("maly", Y, "kwadrat"). pred("maly", "niebieski", "trojkat").

9 Przykładowe wyświetlanie listy Definiowanie predykantów: p([1,2,3]). p([bury,kot,mruczy,[sobie,pod,nosem]]). Komenda : ?- p([X|Y]). Wynik działania programu : X = 1 Y = [2,3] ? ; X = bury Y = [kot,mruczy,[sobie,pod,nosem]] Yes

10 Bardziej czytelny zapis list Z poprzednich przykładów: [a] oraz [a,b,c] Głowa – pierwszy element, ogon – wszystko co pozostaje za pierwszym elementem ListaGłowaOgon [a, b, c]a[b, c] [ ](brak) [[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]

11 Lista z głową X i ogonem Y: [X|Y] Zapis jest związany z główną operacją list, czyli dzieleniem ich na głowę i ogon. X i Y jest rozdzielone pionową kreską. Np.: p([1,2,3]) X=1 Y=[2,3] Np.: p([bury, kot, mruczy, [sobie, pod, nosem]]). X=bury Y=[kot, mruczy, [sobie, pod, nosem]]

12 Przykład Definiowanie predykantów: lista([x,y,z]). lista([jan,lubi,ryby]). Komenda : ?- lista([X|Y]). Wynik działania programu : X = x Y = [y,z] ? ; X = jan Y = [lubi,ryby] Yes

13 Przykład Definiowanie predykantów: lista2([a,b,c]). lista2([2,4,6,ala,ma,kota]) Komenda : ?- lista2([X|Y]). Wynik działania programu : X = a Y = [b,c] ? ; X = 2 Y = [4,6,ala,ma,kota] Yes

14 Dekompozycja i strukturalizacja list jest realizowana głównie przez mechanizm unifikacji, a co za tym idzie notacja jest jej podstawą. Na przykład: Komenda : ?- [X,Y|Z]=[a,b,c,d]. Wynik działania programu : X = a Y = b Z = [c,d] Yes Komenda : ?- [X,Y,a]=[Z,b,Z]. Wynik działania programu : X = a Y = b Z = a Yes

15 Przeszukiwania rekurencyjne Przykładowa lista imion: [adam, kamil, paweł, sylwia, anna, magda] Chcemy sprawdzić czy dane imię znajduje się w liście: W Prologu najpierw sprawdzamy czy interesujące nas imię znajduje się w głowie listy. Jeśli tak, mamy już odpowiedź. Jeśli nie, sprawdzamy czy imię występuje w ogonie listy. Za każdym razem sprawdzamy głowę ogona listy. Gdy dojdziemy do listy pustej – przeszukiwanie kończy się negatywnie.

16 Jak zapisać to w prologu? Związek obiektu i listy: przynależność. Predykat (funktor) : member(X,Y), jest spełniony wtedy, gdy X należy do listy Y. Musimy sprawdzić dwa warunki : -X naeży do listy, jeśli jest jej głową: member(X,[X|_]). - X należy do listy, jeśli należy do jej ogona: member(X,[_|Y]) :- member(X,Y). _ (podłoga) – zmienna anonimowa (nie potrzebna)

17 Przykład Komenda : ?- nalezy(X,a). Wynik działania programu : No Komenda : ?- nalezy(X,[a,b,c,d]). Wynik działania programu : X = a ? ; X = b ? ; X = c ? ; X = d ? yes

18 Przykład Komenda : ?- nalezy(d,[a,b,c,d,e,f,g]). Wynik działania programu : Yes Komenda : ?- nalezy(2, [3,a,4,f]). Wynik działania programu : No

19 Odwzorowania Przechodzimy przez kolejne składniki starej struktury tworząc jednocześnie składniki struktury nowej. Ty jesteś komputerem Ja nie jestem komputerem Aby wygenerować taki dialog należy : 1. Wczytać zdanie podane przez użytkownika 2. Zmienić wszystkie formy drugiej osoby na pierwszą 3. zmienić Ty na Ja nie Przykład

20 Odwzorowania Zdefiniowanie predykatu : zmien(X,Y) gdzie X i Y to listy Wywołanie: ?- zmien([czy, mowisz, po, francusku],X) Wynik: X=[nie, mowie, po, niemiecku]. Zmiana pustej listy daje listę pustą: zmien([ ],[ ]).

21 Liczenie elementów listy Zdefiniowanie : dlugosc([],0). dlugosc([_|Ogon],Dlug) :- dlugosc(Ogon,X), Dlug is X+1. Wywołanie: ?- dlugosc([a,b,c,d],X). Wynik: X = 4 Yes

22 Łączenie struktur Wywołanie: ?- append([a,b,c],[1,2,3],L3). Wynik: L3 = [a,b,c,1,2,3] yes

23 Łączenie list Zdefiniowanie sklej([],X,X). sklej([X|L1],L2,[X|L3]) :-sklej(L1,L2,L3). Wywołanie: ?- sklej([a,b],[c,d],X). Wynik: X = [a,b,c,d] yes

24 Wyświetlanie elementów przed i po Zdefiniowanie sklej([],X,X). sklej([X|L1],L2,[X|L3]) :-sklej(L1,L2,L3). Wywołanie: ?- sklej(Przed,[5|Po],[1,2,3,4,5,6,7,8,9]). Wynik: Po = [6,7,8,9] Przed = [1,2,3,4] ? Yes

25 Dodawanie elementów Zdefiniowanie dodaj(X,L,[X|L]). Wywołanie: ?- dodaj(a,[c,d],X). Wynik: X = [a,c,d] Yes

26 Usuwanie elementów Zdefiniowanie usun(X,[X|Reszta],Reszta). usun(X,[Y|Ogon],[Y|Reszta]) :-usun(X,Ogon,Reszta). Wywołanie: ?- usun(c,[a,b,c,d],X). Wynik: X = [a,b,d] ? Yes

27 Odwracanie list Zdefiniowanie odwroc([],[]). odwroc([H|T],L) :- odwroc(T,R), sklej(R,[H],L) Wywołanie: ?- odwroc([a,b,c,d],X). Wynik: X = [d,c,b,a] Yes

28 Porównanie rekurencyjne Zdefiniowanie zuzycie_nie_gorsze(Dobre,Zle) :- Progowa is (Dobre + Zle) / 40, Najgorsze is Zle + Progowa, Dobre < Najgorsze. Wywołanie: ?- zuzycie_nie_gorsze(10.5, 10.7). Wynik: Yes Wywołanie: ?- zuzycie_nie_gorsze(10.7, 10.1) Wynik: No

29 Karolina Supera Michał Krajewski

30 Generowanie wielu rozwiązań Generowanie wielu rozwiązań zapytania na podstawie zbioru faktów, gdy wiele faktów pasuje do tego zapytania. Prolog nie zapamiętuje zwracanych wyników i ich nie zapamiętuje. Fakty: ojciec(X,Y) oznaczające że Y jest ojcem X: ojciec(maria, jerzy). ojciec(jan, jerzy). ojciec(zuzanna, henryk). ojciec(jerzy, edward). Zapytanie: ?- ojciec(X,Y).

31 Istnieje wiele odpowiedzi, na żądanie średnikiem kolejnych rozwiązań otrzymamy: Wynik: X=maria, Y=jerzy; X=jan, Y=jerzy X=zuzanna, Y=henryk X=jerzy, Y=edward Kto jest ojcem: ?- ojciec(_,X). Wynik: X=jerzy; X=jerzy; X=henryk; X=edward;

32 Jednym z dzieci X jest Y, definicja: dziecko(X,Y) :- ojciec(Y,X) Zapytanie: ?- dziecko(X,Y) X jest ojcem: ojciec(X) :-ojciec(_,X). Zapytanie: ?- ojciec(X).

33 Jeśli mieszamy fakty i reguły, możliwe rozwiązania pojawiają się w takiej kolejności, w jakiej prezentowane są dane. Tak więc możemy zapisać, ze adam jest osobą, że osobą jest wszytsko posiadajace matkę, i że ewa jest osobą. Poza tym różni ludzie mogą mieć różne matki: osoba(adam). osoba(X) :- matka(X,Y). osoba(ewa). matka(kain,ewa). matka(abel,ewa). matka(jabal,ada). matka(tubilkain,sybilla).

34 Zapytanie: ?- osoba(X). Wynik: X=adam; X=kain; X=abel; X=jabl; X=tubilkain; X=ewa;

35 Odcięcia Pozwala nakazać interpreterowi Prologu, by nie uwzględniał wcześniejszych możliwości wyboru podczas nawracania. Program działa szybciej, gdyż nie musi niepotrzebnie spełniać celów, których wynik jest już znany, i który nie wnosi do rozwiązania nic nowego. Program zajmuje mniej pamięci komputera, gdyż pamięć jest zużywana oszczędniej z uwagi na to, ze nie trzeba na później zapisywać punktów nawracania.

36 Przykład Definicja: suma_do(1,1) :- !. suma_do(N,Razem) :- N1 is N - 1, suma_do(N1,Razem1), Razem is Razem1 + N. Zapytanie: ?- suma_do(5,X). Wynik: X = 15 Yes Zapytanie ?- suma_do(4,X). Wynik: X = 10 ? ; X = 10 ? ; X = 10 ? ; X = 10 ? yes

37 Zapytanie: ?- suma_do(5,X). Wynik: X = 15 ? Yes Zapytanie: ?- suma_do(1,X). Wynik: X = 1 ? yes