Listen (Prolog)
Aus Infostudium Wiki
Inhaltsverzeichnis |
Definition
- Abkürzungen:
nil [ ] cons(X,Y) [X | Y] cons(X, cons(Y, nil)) [X, Y] cons(X, cons(Y, R)) [X, Y | R]
- Schrittweiser Aufbau einer Liste durch Vorsetzen eines neuen Kopfelementes:
[hd | tl]
- Der rekursive Aufbau erlaubt sehr gut strukturierte rekursive Programme.
- Beispiel:
length([], 0). length([_ | R], L) :- length(R, LR), L is LR + 1.
- Grundprinzip:
- Behandle die leere Liste
- Trenne von einer nichtleeren das erste Element ab, und behandle zunächst die Restliste.
- Zeichenketten sind Listen einzelner Zeichen:
- "abcd" = [97, 98, 99, 100]
- Konkatenieren
concat([], L, L). concat([H|T], L, [H|NeueListe] ) :- concat(T,L,NeueListe).
Beispiele
a)
Das Prädikat loescheAlle(X,L1,L2) löscht aus einer Liste L1 alle Vorkommen von X und liefert als Ergebnis dieses Löschvorgangs die Liste L2 zurück. Hierbei dürfen Sie das vordefinierte Prädikat \= (für "ungleich") verwenden. Es gilt s \= t gdw. s=t nicht beweisbar ist.
loescheAlle(_,[],[]). % Abbruchbedingung loescheAlle(X,[X|Xs],Ys):- loescheAlle(X,Xs,Ys). loescheAlle(Y,[X|Xs],[X|Ys]):- Y \= X, loescheAlle(Y,Xs,Ys).
Die Anfrage ?- loescheAlle(1,[1,2,3,4,1,1,2,6,5],X). soll also als Ausgabe X = [2,3,4,2,6,5] liefern.
Erläuterung:
loescheAlle(_,[],[]). % Abbruchbedingung loescheAlle(X,[Y|Xs],Ys):- X==Y,loescheAlle(X,Xs,Ys). % Das gesuchte X stimmt mit dem Y-Element aus der ersten Liste überein. Also wird das % Ergebnis (die Liste Ys) nicht angetastet. Rechts wird nur der Rest der ersten Liste übernommen. % Die Bedingung wird rechts mit dem rekursiven Aufruf mit Hilfe des Kommas (,) zu einer Und-Verknüpfung % zusammengefügt. loescheAlle(X,[Y|Xs],[Y|Ys]):- X\=Y,loescheAlle(X,Xs,Ys). % Das gesuchte X stimmt nicht mit dem Y-Element überein. Also kann das Y aus der ersten Liste in die % zweite Liste übernommen werden. Nun muss man folgendermaßen denken: Wann trifft die linke Seite zu? % Wann ist also das Y aus der ersten Liste auch Y-Element der zweiten Liste? % Das trifft zu, wenn X ungleich Y ist. Dann muss wieder der rekursive Teil drangehangen werden. % Ziemlich verwirrend finde ich.
b)
Das Prädikat erzeugeMenge(L1,L2) wandelt eine Liste L1, in der Elemente beliebig oft auftreten dürfen, in eine Liste L2 um, in der jedes Element aus der ursprünglichen Liste genau einmal vorkommt (anschaulich bedeutet das, dass die Mengendarstellung von L1 in L2 gespeichert wird).
erzeugeMenge([],[]). erzeugeMenge([X|L1],[X|L2]):-loescheAlle(X,L1,L), erzeugeMenge(L,L2).
Die Anfrage ?- erzeugeMenge([1,2,3,4,1,1,2,6,5],X). soll also als Ausgabe X = [1,2,3,4,6,5] liefern.
c)
Alle 'a's aus einer Liste löschen:
streiche_a([], []). streiche_a([97 | T], S) :- streiche_a(T, S). streiche_a([X | T], [X | S]) :- X /= 97, streiche_a(T, S).
Begriffe
Konkatenation
(Verkettung, engl. concatenation)
Wieder ein Wort, mit dem man sich wichtig machen kann. Auf gut Deutsch: Listen zusammenschmeißen.
