Prolog eLearning
Tutorial

4: Listen

Zu den Aufgaben Folien ansehen Musterlösungen herunterladen
  • Listen sind sehr mächtige Datenstrukturen in Prolog.
  • Listen sind endliche Sequenzen von Elementen: 
% Liste mit atomaren Elementen:
[mia, vincent, jules, mia]
% Liste mit verschiedenen Termen als Elemente: [mia, 2, mother(jules), X, 1.7]
% leere Liste:
[]
% Listenelemente koennen Listen sein:
[mia, [[3,4,paul], mother(jules)], X]
  • Listen können verschachtelt sein (Listen können Listen als Elemente haben)
  • Die Reihenfolge der Elemente ist wichtig [a,b,c] = [b,a,c] (Unterschied zu Mengen).
  • Dasselbe Element kann mehrfach in einer Liste vorkommen (Unterschied zu Mengen).

Listenzerlegung in Prolog

  • Prolog hat einen eingebauten Operator ‘|’ (Listenkonstruktor) mit dem man eine Liste in Kopf (head) und Rest (tail) zerlegen kann.
  • Der Kopf ist das erste Element der Liste.
  • Der Rest ist die Restliste. 
?- [Head|Tail] = [mia, vincent, jules, mia].
Head = mia,
Tail = [vincent, jules, mia].
  • Eine leere Liste hat keinen Head und lässt sich somit nicht zerlegen: 
?- [Head|Tail] = [].
false.
  • Man kann mit ‘|’ auch mehr als ein Element am Anfang abtrennen: 
?- [First,Second|Tail] = [mia, vincent, jules, mia].
First = mia,
Second = vincent,
Tail = [jules, mia].

Prädikat:member/2

member/2 ist ein rekursiv definiertes Prädikat, das überprüft, ob ein Element (ein Term) in einer Liste vorkommt: 

% member/2, member(Term,List)
member(X,[X|_]).
member(X,[_|T]) :-
    member(X,T).
  • Der Fakt member(X,[X|_]). besagt, dass etwas ein Element einer Liste ist, wenn es das erste Element (der Head) der Liste ist.
  • Die Regel member(X,[_|T]):- member(X,T). besagt, dass etwas ein Element einer Liste ist, wenn es ein Element der Restliste (des Tails) ist.
  • Jedes Element einer Liste ist entweder erstes Element oder ein Element im Tail.
  • Vorsicht: member/2 ist ein in der Library lists vordefiniertes Prädikat, das von manchen Prologimplementierungen automatisch geladen wird. Verwenden sie daher besser einen anderen Namen, z.B. my_member/2.

Vorteile der deklarativen Programmierung

Die deklarative Logik von member/2 erfasst verschiedene Fälle, für die in prozeduralen Sprachen separate Prozeduren geschrieben werden müssten: 

% Ist 1 in Liste [1,2,3]?
?- member(1,[1,2,3]).
% In welchen Listen ist 1?
?- member(1,L).
% Welche X sind in [1,2,3]?
?- member(X,[1,2,3]).
% In welchen Listen ist X?
?- member(X,L).

Interne rekursive Listenrepräsentation

Prolog behandelt nichtleere Listen intern als zweistellige zusammengesetzte Terme mit Funktor ’[|]’. 

?- [a,b]=’[|]’(a,’[|]’(b,[])).
true.

Nichtleere Listen werden dabei in Kopf und Rest zerlegt.

Der Rest ist entweder die leere oder wiederum eine nichtleere Liste.

’[|]’(a, [])
’[|]’(a, ’[|]’(b, []))
’[|]’(a, ’[|]’(b, ’[|]’(c, []))) 		[a | []]
[a | [b | []]]
[a | [b | [c | []]]] 		[a]
[a,b]
[a,b,c]

Listen können als binäre Bäume aufgefasst werden:

Unifikation / Matching von Listen

Zwei Listen sind unifizierbar,

  • wenn sie dieselbe Länge haben und
  • wenn die korrespondierenden Listenelemente unifizierbar sind. 
?- [a,b,X]=[Y,b,3].
X = 3, Y=a
?- [[a,b,c],b,3]=[Y,b,3]. Y = [a, b, c]
?- [a,b,c] = X. % Variablen koennen mit Listen unifiziert werden. X=[a,b,c]
?- [a,b,X,c]=[Y,b,3].
false.
?- [a,c,3]=[Y,b,3].
false.
  • Die Länge einer Lister ist die Zahl ihrer Elemente.

Anonyme Variable

  • Die Variable ‘_’ ist die anonyme Variable in Prolog.
  • Sie kommt immer dann zum Einsatz, wenn ein Wert zwar variabel sein soll, später aber nicht mehr benötigt wird.
  • Die anonyme Variabel erhöht die Lesbarkeit der Programme.
  • Anders als bei anderen Variablen ist jedes Vorkommen der anonymen Variabel unabhängig von den anderen. Sie kann also immer wieder anders initialisiert werden: 
isst_gerne(X,X) = isst_gerne(a,b).
false.
isst_gerne(_,_) = isst_gerne(a,b).
true.

Hinweis: Variablen wie _X, die mit einem Unterstrich beginnen sind nicht anonym, sie führen aber im Gegensatz zu anderen Variablen beim Konsultieren einer Wissensbasis nicht zu der Warnung: „singleton variables:“.

Beispielanfrage:member/2 

?- member(c,[a,b,c,d]).
% Die erste Klausel passt nicht, aber die zweite. Weiter geht es mit:
member(c,[b,c,d]).
% Und wieder passt nur die rekursive Klausel und es geht weiter mit:
member(c,[c,d]).
% Jetzt passt die erste Klausel (c ist das erste Element der Liste). Wir bekommen:
?- member(c,[a,b,c,d]).
true.   
?- member(c,[a,b]).
% Die erste Klausel passt nicht, aber die zweite. Weiter geht es mit:
member(c,[b]).
% Und wieder passt nur die rekursive Klausel und es geht weiter mit:
member(c,[]).
% Jetzt passt keine der beiden Klauseln, da die Liste leer ist. Wir bekommen:
?- member(c,[a,b]).
false.

rekursive Listenverarbeitung an einem Beispiel

Die Definition von Prädikaten, die Listen rekursiv verarbeiten, gehört zu den zentralen Aufgaben in der Prologprogrammierung.

Beispiel: Prädikat a2b/2, das zwei Listen L1 und L2 nimmt und genau dann zutrifft, wenn beide Listen gleich lang sind und L1 nur aus a’s und L2 nur aus b’s besteht.

Vorgehensweise: Zunächst sollte man sich möglichst verschiedene positive und negative Beispiele für die Belegungen der Variablen L1 und L2 überlegen: 

% negative Beispiele
?- a2b([a,c,a],[b,b,b]). % L1 besteht nicht nur aus a’s
false.
?- a2b([a,a,a],[b,c,b]). % L2 besteht nicht nur aus b’s
false.
?- a2b([a,a],[b,b,b]). % L1 ist kuerzer als L2
false.
?- a2b([a,a,a],[b,b]). % L1 ist laenger als L2
false.
?- a2b(t,[b,b]). % L1 ist keine Liste
false.
?- a2b([a,a],t). % L2 ist keine Liste
false.

Ausgehend von dieser Aufstellung möglicher Anfragen ist es oft relativ einfach, die Ankerklausel zu formulieren: der Fall mit den einfachsten Listen, die zu einem true führen.

a2b([],[]).

Anschließend benötigt man noch die rekursive Klausel: zwei Listen erfüllen die Bedingung des Prädikats a2b/2, wenn die erste Liste mit einem a beginnt und die zweite mit einem b und die Restlisten die Bedingung a2b/2 erfüllen: 

a2b([],[]).
a2b([a|T1],[b|T2]):-
    a2b(T1,T2).

Abschließend sollte man immer die Prädikatsdefinition mit den zuvor aufgestellten Positiv- und Negativbeispielen testen.