Rekursive Verarbeitung von Listen
Beispiel - Zusammenfügen von Listen
Ziel ist es, ein Prädikat zusammenfuegen/3
festzulegen, mit dem man zwei Listen
durch Hintereinanderreihung der Listenelemente zu einer Liste zusammenfügen kann.
Der folgende Dialog zeigt das gewünschte Verhalten des
zusammenfuegen
-Prädikats anhand einiger Anfragebeispiele auf.
?- zusammenfuegen([a, b], [c, d, e], L).
L = [a, b, c, d, e] ;
false.
?- zusammenfuegen([], [a, c, d], L).
L = [a, c, d] ;
false.
?- zusammenfuegen(A, B, [a, b, c]).
A = [],
B = [a, b, c] ;
A = [a],
B = [b, c] ;
A = [a, b],
B = [c] ;
A = [a, b, c],
B = [] ;
false.
Zur Festlegung des zusammenfuegen
-Prädikats benutzen wir Rekursion,
indem wir das Problem "Zusammenfügen von Listen" auf eine entsprechendes Problem (in verkleinerter Form)
zurückführen. Die Idee soll zunächst in Worten beschrieben werden.
Regel 1: [] und L zusammengefügt ergibt l. Regel 2: [K|R] und L zusammengefügt ergibt [K|N], wenn R und L zusammengefügt die Liste N ergibt.
Diese informell beschriebenen Regeln lassen sich in Prolog z.B. so umsetzen.
zusammenfuegen([], L, L).
zusammenfuegen([K|R], L, [K|N]) :- zusammenfuegen(R, L, N).
Veranschaulichung als Bildgalerie- Prädikatsnamen gekürzt zu zf
.
Aufgabe 1
Teste die gezeigte Wissensbasis zum zusammenfuegen
-Prädikat.
Beispiel - Elementbeziehung
Ziel ist es, ein Prädikat element/2
festzulegen, mit dem man überprüfen
kann, ob ein Element in einer Liste vorkommt. Der folgende Dialog zeigt das gewünschte Verhalten des
element
-Prädikats anhand einiger Anfragebeispiele auf.
?- element(b, [a, b, c, d]).
true.
?- element(e, [a, b, c, d]).
false.
?- element(E, [a, b, c, d]).
E = a ;
E = b ;
E = c ;
E = d ;
false.
Zur Festlegung des element
-Prädikats benutzen wir Rekursion,
indem wir das Problem "ist Element von" auf eine entsprechendes Problem (in verkleinerter Form)
zurückführen. Die Idee soll zunächst in Worten beschrieben werden.
Regel 1: E ist Element von L, wenn L aus dem Kopfelement K und der Restliste R besteht und wenn E gleich dem Kopfelement K ist. Regel 2: E ist Element von L, wenn L aus dem Kopfelement K und der Restliste R besteht und wenn E ungleich dem Kopfelement K ist und wenn E Element der Restliste R ist.
Diese Regeln lassen sich in Prolog z.B. so umsetzen.
element(E, L) :- L = [K|R], E = K.
element(E, L) :- L = [K|R], E \== K, element(E, R).
Es geht auch kürzer:
element(E, [E|R]).
element(E, [K|R]) :- element(E, R).
Aufgabe 2
Teste die gezeigte Wissensbasis zum element
-Prädikat.
Aufgabe 3
Entwickle Fakten und Regeln zu einem letztes_element
-Prädikat.
letztes_element([E], ?).
letztes_element([K|R], E) :- ?.
Aufgabe 4
Entwickle Fakten und Regeln zu einem mit_letztem_element
-Prädikat.
Regel 1: Eine Liste bestehend aus der leeren Liste [] und dem letzten Element E ergibt die Liste [E]. Regel 2: Eine Liste bestehend aus [K|R] und dem letztem Element E ergibt eine Liste [K|L], wenn die Liste bestehend aus R und dem letzten Element E die Liste L ergibt.