Listen mit Prolog

Einführung von Listen

Eine Liste ist eine geordnete Folge von Elementen beliebiger Länge. Die Ordnung impliziert, dass es ein erstes, zweites, drittes usw. Element gibt. Die Elemente einer Liste können beliebige Terme sein: Konstanten, Variablen, Strukturen und sogar andere Listen. Im Unterschied zu imperativen Programmiersprachen können die Elemente einer Liste in Prolog unterschiedliche Datentypen aufweisen.

Beispiele für Listen:

[1,2,3]
[d,e,f,g]
[1,[a,b], Z, paula]
[’guten’,’Tag’,a,’11.30 Uhr’]
[vater(’Klaus’,’Schmidt’),hat,3,Soehne,und,4,’Toechter’].

Darstellung von Listen

Darstellung der Liste als (entarteter) Baum

Mit der Systemerweiterung zeichneterm.pl (Hinweise zur Installation) stehen die zwei Prädikate zeichne_term/0 und zeichne_term/1 zur Verfügung. Mit diesen Prädikaten kann jeder beliebiger Prolog-Term als Baum dargestellt werden.

Das letzte Beispiel der obigen Beispielliste wird z. B. wie in der rechten Abbildung dargestellt. Die Elemente der Liste treten im Baum als Blätter auf. Das Blatt [] signalisiert das Ende der Liste, entspricht daher in Pascal der Konstanten Nil. Als Funktor für Listen in Prolog wird ein . (Punkt) verwendet.

Punktschreibweise für Listen

Die Klammerschreibweise spielt in Prolog nur für die Ein- und Ausgabe eine Rolle. Intern benutzt Prolog die Punktschreibweise für Listen. Sie basiert auf der Idee alle Datenstrukturen auf Baumstrukturen zurückzuführen.

Mit dem Systemprädikat display können die Strukturen von Termen in Präfix-Schreibweise angezeigt werden:

?- display([vater('Klaus','Schmidt'),hat,3,Soehne,und,4,'Toechter']).
.(vater(Klaus, Schmidt),.(hat, .(3,.(_G23589,.(und,.(4,.(Toechter,[])))))))

Listenoperator

Mit der bisherigen Schreibweise von Listen lässt sich die Dynamik von Listen nicht beschreiben, da nur Listen fester Länge angegeben werden können. Daher wird die Notation um den Listenoperator "|" (<pipe>) erweitert. Mit ihm kann man aus einem Kopfelement und einer Restliste eine neue Liste zusammen setzen oder eine bestehende Liste in Kopfelement und Restliste aufteilen. Damit steht eine Notation zur Verfügung, mit der Listen beliebiger Länge rekursiv beschrieben werden können.

L = [Kopf|Restliste]

Es ist darauf zu achten, dass der Listenoperator unterschiedliche Objekte verbindet: links (vor dem Listenoperator bzw. an erster Stelle) steht ein einzelnes Element, rechts davon eine komplette Liste.

Liste	Kopf	Rumpf
[a,b,c]	a	[b,c]
[[die, maus], lief]	[die, maus]	[lief]
[die, [maus, lief]]	die	[[maus, lief]]
[die, [maus, lief], weg]	die	[[maus, lief], weg ]
[X + Y, x + y]	X + Y	[x + y]
[a]	a	[]
[]	nicht def.	nicht def.

Man kann den Listenoperator auch in erweiterter Form benutzen, in dem man nicht nur ein sondern gleich mehrere aufgezählte Elemente am Kopf der Liste anfügt bzw. abspaltet:

L = [K1,K2|Rs]

Beispiele zur Verwendung des Listenoperators

?- L=[a|[b,c]].
L = [a, b, c] ;

?- L=[gelb|[]].
L = [gelb] ;

?- X=[a,b,c],L=[a|X].
X = [a, b, c]
L = [a, a, b, c] ;

?- [[a,b],[c,d],[e,f]]=[K|Rs].
K = [a, b]
Rs = [[c, d], [e, f]] ;

?- [a,b,c,d]=[K1,K2|Rs].
K1 = a
K2 = b
Rs = [c, d] ;

?- [A|B] = [1,2,3,4].
A = 1,
B = [2, 3, 4];

?- [A|[B,C,D]] = [1,2,3,4].
A = 1,
B = 2,
C = 3,
D = 4;

Beispiel: Stackoperationen

Mit Hilfe des Listenoperators lassen sich z. B. die Stack-Operationen Push, Pop und ToS sehr einfach realisieren:

?- NS=[name('Klaus')|S].
NS = [name('Klaus')|_G317]
S = _G317 ;

?- S=[a,b,c,d], S=[_|NS].
S = [a, b, c, d]
NS = [b, c, d] ;

?- S=[a,b,c,d], S=[ToS|_].
S = [a, b, c, d]
ToS = a ;