LbP Listen
Aus ProgrammingWiki
Die Liste als strukturierter Datentyp
In Prolog gibt es kein strenges Typkonzept für Daten. Die durch die Unifikation geforderte Art der Übereinstimmung erzwingt in erster Linie eine Strukturgleichheit. Die einzelnen Bestandteile einer Strukur können prinzipiell beliebige Typen sein. Listen sind spezielle Strukturen, die in der Logik-orientierten (ebenso wie in der funktionsorientierten) Programmierung eine fundamentale Rolle spielen.
Eine Liste ist entweder die leere Liste, [], oder ein Konstrukt aus einem Kopfelement (head) und einer Restliste (tail). In funktionsorientierten Sprachen ist cons der analoge Konstruktor für Listen. Der dementsprechende Operator heißt hier head-tail-Separator, geschrieben als senkrechter Strich |, und wirkt bidirektional, d.h. sowohl synthetisierend als auch analysierend.
liefert die Zahl 1 als head und die entsprechende Restliste als tail. Die einzelnen Listenelemente werden durch Kommata untereinander getrennt. Das entspricht der Analysewirkung. Ein Beispiel für die Synthese ist
Auf diese Weise entsteht die Liste [1,2,3,4].
Das Ergebnis ist nicht etwa [1, 2, 3, [4, 5, 6]]. Das Komma zwischen X und Y wirkt vielmehr wie cons(X,Y) bzw. X|[Y]. Ausführlich würde obige Anfrage lauten
Unter Verwendung des head-tail-Separators kann man die obige (informelle) Listendefinition wie folgt ausdrücken.
member/2 ist bei einige Prolog-Implementierungen ein Systemprädikat. member(X,Xs) ist wahr, wenn X in Liste Xs enthalten ist.
Wir definieren ein eigenes Prädikat member/2:
Liste können verschachtelt werden. Dies entspricht ja gerade ihre rekursiven Natur. Dabei ist zu beachten, dass die Suche des entsprechenden Elements in der gegebenen Liste nicht rekursiv in deren Teillisten fortgesetzt wird. Die Liste [3] ist ein Element der Liste [1, 2, [3], 4], nicht jedoch die Zahl 3.
hingegen gehört [3] zur Liste:
Folgende Anfragen sind interessant:
Auf die letzte Anfrage antwortet Prolog nur mit der zuerst gefundenen Lösung. Es gibt insgesamt 3. Man kann sie ermitteln, wenn man (beispielsweise) das Metaprädikat findall benutzt.
Dies sagt uns, dass es unendlich viele Lösungen gibt. Diese erhält man durch Instanziierung obigen Ausdrucks, mit einer beliebigen Liste.
Im nächsten Beispiel definieren wir ein append/3:
Stellen Sie die folgenden Anfragen:
Die Bidirektionalität der Prädikatargumente von append ermöglichen eine hohe Flexibilität. Nicht jedes Prädikat hat diese Eigenschaft.
Ein häufig benötigtes Prädikat ist reverse/2, zur Listenumkehr. Unsere Definition lautet:
Übungsaufgaben
- Machen Sie sich im Manual mit den Systemprädikaten für die Arbeit mit Listen vertraut.
- Definieren Sie folgende einfache Prädikate: erstes_element/2, letztes_element/2, vorletztes_element/2, loesche/3, loesche1/3, kein_element/2 und laenge/2, mit folgenden Bedeutungen:
erstes_element(X,Ls): X ist erstes Element der Liste Ls.
letztes_element(X,Ls): X ist letztes Element von Ls
vorletztes_element(X,Ls): X ist vorletztes Element von Ls
element(X,Ls): X ist Element der Liste Ls
loesche(X,Ls,Ms): Ms entsteht aus Ls durch Loeschen von X
loesche1(X,Ls,Ms): Ms entsteht aus Ls durch einmaliges Loeschen von X
kein_element(X,Ls): X ist kein Element von Ls
laenge(Ls,N): N ist die Laenge der Liste Ls
- Definieren Sie zufallsliste/3, mit zufallsliste(N,M,Zs), wobei die Zufallszahlenliste Zs genau N natürliche Zufallszahlen aus [0,M-1] enthalten soll.
- Definieren Sie quicksort/2, mit quicksort(X,Y), wobei Y die sortierte Liste von X ist. X enthalte natürliche Zahlen. Die Sortierung erfolge nach der Ordnungsrelation <. Wenden Sie das Prädikat zur Sortierung auf eine 100-elementige Zufallsliste aus [0,200] an.
