Listen

Die Werkzeuge

Eine Liste ist eine geordnete Sammlung endlich vieler Elemente. Diese können Atome sein (Texte in '' oder klein geschrieben), Zahlen und auch Listen. Die Listenelemente, durch Komma getrennt, werden in [] eingeschlossen und sind durch ihre Position in der Liste gekennzeichnet:

[2,4,8,6] [berta,anton,frieda] [2,peter,5,anton] [2,[4,1]5,[a,b,c]] (Elemente: 2, Liste [4,1], 5, Liste [a,b,c])

Durch den Selektor | lässt sich das erste Listenelement abspalten:

[4,2,6,1] = [A|R] liefert als A 4 und als R die Restliste [2,6,1] [x,y,w,v] = [_|R] liefert als R die Restliste [y,w,v]

Der Selektor kann genutzt werden, um am Listenanfang ein neues Element einzuhängen:

Ist A = ab und R = [2,3,4], so erzeugt L = [A|R] die Liste L = [ab,2,3,4].

Durch rekursive Prädikate lassen sich auch die übrigen Elemente erreichen, bzw. neue Elemente an beliebigen Positionen einfügen. SWI-Prolog stellt vordefinierte Prädikate zur Verfügung, mit denen sich eigene Prädikate ersetzen lassen (Auswahl):

append(A,B,C)
nth1(I,L,E)
select(E,L,R)

wahr, wenn Vereinigung der Listen A und B die Liste C ist
wahr, wenn E das I-te Element der Liste L ist
wahr, wenn E Element der Liste L ist und R die nachfolgende Restliste

Wenn einer der Parameter noch keinen konkreten Wert hat, versucht Prolog, dem Parameter einen Wert zuzuordnen, so dass das Prädikat wahr wird. Dies kann man nutzen, um Elemente an der gewünschten Position einzufügen oder auszulesen:

Beispiele: [A|_]=[1,2,3,4,5] liefert A = 1 [_|R]=[1,2,3,4,5] liefert R = [2,3,4,5]

Im folgenden soll mit einfachen Progrmmen gezeigt werden, wie man auch ohne die zusätzlichen Prädikate von SWI-Prolog verschiedene Aufgaben lösen kann.

Anwendungen

Element E am Listeanfang einfügen:
ins(E,L,[E|L]).

Element E am Listenende einfügen:
app(E,[],[E]).
app(E,[A|R],[A|S]):-app(E,R,S).

Element E suchen:
elem(E,[E|_]).
elem(E,[_|L]):-elem(E,L).

Element A durch N ersetzen:
chg(A,N,[A|R],[N|R]).
chg(A,N,[E|R],[E|S]):-chg(A,N,R,S).

chg(A,_,_,_).

Element E löschen:
del(_,[],[]).
del(E,[E|R],R).
del(E,[A|R],[A|S]):-del(E,R,S).

Sortieren:
srt([],[]).
srt([A|RA],[B|RB]):-srt(RA,[B|R]),B=<A,srt([A|R],RB).

srt([A|RA],[A|RB]):-srt(RA,RB).

aus E und Liste L neue Liste mit E am Anfang

wenn die Liste leer, dann neue Liste [E]
hat die Liste die Form [A|R], durch Anhängen von E an R neue Liste S,
     S mit A als Anfang ergibt dann die Ergebnisliste
ist E der Listenanfang, so ist elem wahr
andernfalls erstes Element fortlassen und E in der Restliste L suchen

ist A der Listenanfang, dann N statt A als neuen Listenanfang
hat die Liste die Form [E|R], A durch in R ersetzen zur neuen Liste S,
     S mit E als Anfang ergibt dann die Ergebnisliste
andernfalls A nicht in der Liste vorhanden, dann keine Aktion

ist die Liste leer, dann keine Aktion
ist E der Listenanfang, so ist die Restliste R das Ergebnis
hat die Liste die Form [A,R], durch Löschen von E aus R neue Liste S,
     S mit E als Anfang ergibt dann die Ergebnisliste

ist die Liste leer, dann keine Aktion
hat die Liste die Form [A|RA], so die Restliste RA zu [B|R] sortieren,
steht B in der Ordnung vor A, dann B durch A in der Restliste RA ersetzen
und die neue Restliste [A|] zu der Liste RB sortieren, Ergebnis [B|RB]
andernfalls ist A kleinstes Element, dann Restliste RA zu RB sortieren

Zum Verfahren beim Sortieren: Die Idee ist, das kleinste Element in der Liste zu finden und dieses an den Anfang der Liste zu tauschen. Gelingt dies, so kann man das Verfahren für die Restliste wiederholen, bis sie komplett sortiert ist.
Dazu spalte man das erste Listenelement A ab und sortiere die Restliste. Deren kleinstes Element B steht danach am Anfang der Restliste. Es gibt nun zwei Möglichkeiten:

B kommt in der Ordnung vor A, gehört also an den Anfang der Ausgangsliste. B ersetzt man dann in der Restliste durch A und sortiert diese erneut. Zusammen mit B am Anfang erhält man die Ergebnisliste. (2. Programmzeile)
B kommt in der Ordnung nach A. Dann kann A am Anfang verbleiben, und es ist nur die Restliste zu sortieren. (3. Programmzeile)

Vergleicht man das Programm mit entsprechenden Programmen in Java oder ähnlichen Sprachen, so ist bemerkenswert, in nur drei Zeilen ein Sortierprogramm zu formulieren! Ähnliches gilt auch für andere Problemstellungen im Vergleich von Prolog mit Java.
Das Programm findet man unter listen.pl.