Listenoperationen

Für die Arbeit mit Listen gibt es einige grundlegende Listenoperationen. Diese sollen hier etwas genauer vorgestellt werden. Diese Regeln werden teilweise rekursiv formuliert und können deshalb mit beliebig langen Listen operieren.

Erstes Element einer Liste

erstes_element(X,Ls) ist erfüllt, wenn X mit dem ersten Element der Liste Ls instanziert wurde. Mit Hilfe der eingeführten Kopf-Rumpf-Schreibweise ist die Definition erfreulich knapp:

% erstes_element(X,Ls) -- X ist erstes Element der Liste Ls
erstes_element(X, [X|_] ).

?- erstes_element(X,[’guten Tag’,’schöne Welt’]).
X= ’guten Tag';
no

Letztes Element einer Liste

Ist das letzte Element einer Liste gesucht, bietet sich das Prinzip der Rekursion an, da wir nicht wissen, wie lang die Liste ist:

• Das letzte Element einer einelementigen Liste ist das Element selbst (Rekursionsanfang).
• Das letzte Element einer mehrelementigen Liste ist das letzte Element des Rumpfes (Rekursionsfall).

% letztes_element(X|Ls) -- X ist das letzte Element der Liste Ls
letztes_element(X,[X]).
letztes_element(X,[_|Rumpf]):-
  letztes_element(X, Rumpf).

?- letztes_element(X,[a,s,d,f,g]).
X = g;
no

? letztes_element(X,[1,2,[3,4],[5,6]]).
X = [5, 6];
no

Element einer Liste

Nun müsste man auch eine grundlegende Beziehung element definieren, die erfüllt ist, wenn ein Element in einer Liste enthalten ist. Aus dies lässt sich am besten über eine Rekursion lösen:

• Als Rekursionsanfang nehmen wir den einfachen Fall, dass X das erste Element der Liste Ls ist.
• Alle anderen Fälle führen wir auf diesen rekursiv zurück, indem wir X im Rumpf suchen.

% element(X,Ls) -- X ist Element der Liste Ls
element(X, [X|_]).
element(X, [_|Rumpf]) :-
  element(X, Rumpf).

?- element(3, [1,2,3,4]).
yes

?- element(X, [3,1,2,3,4]).
X=3;
X=1;
X=2;
X=3;
X=4;
no

Länge einer Liste

Als nächstes bestimmen wir die Länge einer Liste ... natürlich mit Hilfe einer Rekursion:

• Die Länge der leeren Liste ist Null.
• Die Länge einer nicht leeren Liste ist um 1 größer als die Länge ihres Rumpfes.

% laenge(Ls,N) -- N ist die Länge der Liste Ls
laenge([], 0).
laenge([_|Rumpf], N) :-
  laenge(Rumpf, NRumpf),
  N is NRumpf + 1.

?- laenge([1,2,e,r,’ende’],Anz).
Anz = 5;
no

Verketten von Listen

Das Prädikat verkettet(L1,L2,L3) soll erfüllt sein, wenn L3 durch Aneinanderreihung von L1 und L2 entsteht. Ein einfaches Anhängen der Elemente von L2 an L3 ist leider nicht möglich, so dass wir auch hier wieder auf eine rekursive Idee zurückgreifen müssen. Als Rekursionsanfang kann folgendes definiert werden:

• Wird die leere Liste [] mit einer beliebigen Liste Ls verkettet, so erhält man Ls.

Den Rekursionsabstieg erreicht man, wenn jeweils der Rumpf der Liste L1 mit der Liste L2 verkettet wird. Dies kann durch die folgende Skizze veranschaulicht werden:

Damit kann die Regel formuliert werden:

• Wird eine nicht leere Liste L1 = [K1|Rumpf1] mit einer zweiten Liste L2 verkettet, so ist das Ergebnis diejenige Liste L3, deren Kopf mit dem Kopf K1 der Liste L1 übereinstimmt und deren Rumpf die Verkettung Rumpf1 mit der Liste L2 ist.

Damit lässt sich folgendes Prolog-Prädikat ableiten:

% verketten(L1,L2,L3) -- L3 entsteht durch Verkettung von L1 und L2
verketten([],L,L).
verketten([K1|Rs1],L2,[K1|Rs3]) :-
  verketten(Rs1,L2,Rs3).

Zur Veranschaulichung der Arbeitsweise des verketten-Prädikats ein Beispiel:

?- spur(verketten([a,b],[c,a],L)).
verketten([a, b], [c, a], [a|_G484])
   verketten([b], [c, a], [b|_G505])
      verketten([], [c, a], [c, a])

L = [a, b, c, a] ;

no

Es ist zu erkennen, der rekursive Aufruf jeweils mit einer um den Kopf verkürzten Liste L1 erfolgt. Beim dritten Aufruf entspricht die Liste L1 der leeren Liste [], damit greift die erste Klausel des Prädikats und L3 wird mit [c,a] instanziert. Danach werden die jeweiligen Köpfe von L1 in den unterschiedlichen Rekursionstiefen als Kopf der Ergebnisliste gesetzt.

Das Prädikat verketten besitzt eine Menge von "Fähigkeiten", z. B. kann eine vorgegebene Liste in alle möglichen Teillisten zerlegt werden:

?- verketten(L1,L2,[1,2,3,4]).

L1 = [],
L2 = [1, 2, 3, 4] ;

L1 = [1],
L2 = [2, 3, 4] ;

L1 = [1, 2],
L2 = [3, 4] ;

L1 = [1, 2, 3],
L2 = [4] ;

L1 = [1, 2, 3, 4],
L2 = [] ;

no