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.