Prolog

Logisch Programmeren/Prolog 2006-7 Jori Mur Center for Language and Cognition (CLCG) Rijksuniversiteit Groningen

[email protected]

1

Overzicht • generatiegenoot/2 • Lijsten

Logisch Programmeren 2006-7

2

Huiswerkopgave % % truus % / \ % griet trina % / \ | % marie klara maart % | | % hiske sasha %


3

Huiswerkopgave moeder(hiske,marie). moeder(marie,griet). moeder(klara,griet). moeder(griet,truus). moeder(trina,truus). moeder(maart,trina). moeder(sasha,maart).


4

Huiswerkopgave Twee voor de hand liggende base cases:

generatiegenoot(X,X). of

generatiegenoot(X,Y):- moeder(X,Z), moeder(Y,Z).


5

Huiswerkopgave Recursieve clause in beide gevallen:

generatiegenoot(X,Y):- moeder(X,X1), moeder(Y,Y1), generatiegenoot(X1,Y1).


6

Huiswerkopgave versie 1 generatiegenoot(X,X). generatiegenoot(X,Y):- moeder(X,X1), moeder(Y,Y1), generatiegenoot(X1,Y1).


7

Huiswerkopgave versie 1 ?- generatiegenoot(truus,Y). Y = truus ?- generatiegenoot(klara,Y). Y = klara; Y = marie; Y = marie; Y = klara; Y = klara; Y = maart ?- generatiegenoot(X,klara). Y = klara; Y = marie; Y = marie; Y = klara; Y = klara; Y = maart


8

Huiswerkopgave versie 1 ?- generatiegenoot(X,Y). Y = X; X = hiske, Y = hiske; X = hiske, Y = hiske; X = hiske, Y = hiske; X = hiske, Y = sasha; X = enz... (27 total)


9

Huiswerkopgave versie 2 generatiegenoot(X,Y):- moeder(X,Z), moeder(Y,Z). generatiegenoot(X,Y):- moeder(X,X1), moeder(Y,Y1), generatiegenoot(X1,Y1).


10

Huiswerkopgave versie 2 ?- generatiegenoot(truus,Y). no ?- generatiegenoot(klara,Y). Y = marie; Y = marie; Y = klara; Y = klara; Y = maart ?- generatiegenoot(X,klara). Y = marie; Y = marie; Y = klara; Y = klara; Y = maart


11

Huiswerkopgave versie 2 ?- generatiegenoot(X,Y). X = hiske, Y = hiske; X = hiske, Y = hiske; X = hiske, Y = hiske; X = hiske, Y = sasha; X = enz... (26 total)


12

Huiswerkopgave Alternatieve goal-volgorde:

generatiegenoot(X,Y):- moeder(X,Z), moeder(Y,Z). generatiegenoot(X,Y):- generatiegenoot(X1,Y1), moeder(X,X1), moeder(Y,Y1). Slaagt wanneer verwacht, maar faalt niet. Komt in lus op bijv.

generatiegenoot(sasha,marie). Logisch Programmeren 2006-7

13

Huiswerkopgave Dezelfde oplossing op verschillende manieren bewezen kan je voorkomen door te zorgen dat er geen overlap is tussen de cases:

generatiegenoot(X,Y):- moeder(X,Z), moeder(Y,Z). generatiegenoot(X,Y):- moeder(X,X1), moeder(Y,Y1), X1 \= Y1, generatiegenoot(X1,Y1).


14

Lijsten • Vorig week successorfunctie als recursieve datastructuur. • s(s(s(s(0)))) • s/1 • willekeurig lange reeksen, en daarmee willekeurig grote getallen.


15

Lijsten • we kunnen ook meerplaatsige recursieve datastrukturen maken. Bijv:

• ./2 heeft een willekeurige term als eerste argument en een term van eigen type als tweede

• de 0 van s/1 heet hier [] • .(a,.(b,.(c,[]))) • willekeurig lange lijsten van elementen. • zeer veel gebruikt in Prolog-praktijk (itt successor-functie). Logisch Programmeren 2006-7

16

Definitie lijst lijst([]). lijst(.(_Head,Tail)) :- lijst(Tail).


17

Speciale Notatie Lijsten zijn dermate populair in Prolog dat er een speciale notatie voor

[] voor de lege lijst, [Head|Tail] ipv .(Head,Tail), en [a,b,c] voor de lijst met precies de bestaat:

elementen a,b en c.

.(a,.(b,.(c,[]))) == == == ==

[a,b,c] [a|[b,c]] [a,b|[c]] [a,b,c|[]]

Een goed lees- en schrijfbare notatie, maar voor Prolog is het gewoon ./2 Logisch Programmeren 2006-7

18

Definitie in speciale notatie lijst([]). lijst([_Head|Tail]) :- lijst(Tail).


19

Lijsten [a,b,X,d(e,f)] [a,[b,X],d(e,f)] [a,b,c,d,[]] [a,b,c,d|[]] [a,b,c|d] [a,b,c|[d]]

bevat bevat bevat bevat

4 3 5 4

elementen elementen elementen elementen

is niet goed gedefinieerd is wel goed gedefinieerd.


20

Matching en Lijsten Met matching kan je specifieke elementen van een lijst vinden:

?- [_,_,X|_] = [a,b,c,d,e,f]. X = c ?- [_,_,_|X] = [a,b,c,d,e,f]. X = [d,e,f] ?- [_,[_,_,_|Y]|_] = [a,[b,c,d,e,f]]. Y = [e,f] ?- [_,_,_,_] = [a,[b,c,d,e,f]]. no


21

Member member/2 is waar als het eerste argument een element is van het tweede argument:

member(X,[X|_]). member(X,[_|Y]) :- member(X,Y). Member kan gebruikt worden om te testen, maar ook om Prolog om een element van die lijst te vragen.


22

Allemaal 1-en, Deelverzameling % allemaalenen/1 ?LijstvanEenen allemaalenen([1]). allemaalenen([1|X]):- allemaalenen(X). % deelverzameling/2 +DeelVz +Vz deelverzameling([],Y). deelverzameling([X|Y],Z):- member(X,Z), deelverzameling(Y,Z).


23

Vertaal vertaling(X,Y,V,U) is waar als alle voorkomens van X in V, Y in U zijn, en V en U verder identiek.

vertaling(a,e,[b,l,a,b,l,a],U). U = [b,l,e,b,l,e].


24

Vertaal vertaling(_,_,[],[]). vertaling(X,Y,[X|Vt],[Y|Ut]):vertaling(X,Y,Vt,Ut).


25

Vertaal vertaling(_,_,[],[]). vertaling(X,Y,[X|Vt],[Y|Ut]):vertaling(X,Y,Vt,Ut). vertaling(X,Y,[Vh|Vt],[Vh|Ut]):X \== Vh, vertaling(X,Y,Vt,Ut).


Prolog

Recommend Documents