LbP Listen

Wiki-Quelltext dieser Seite.

<language>Prolog</language>
=== 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'', <tt>[]</tt>, oder ein Konstrukt aus einem Kopfelement (head) und einer Restliste (tail). In funktionsorientierten Sprachen ist <tt>cons</tt> der analoge Konstruktor für Listen.
Der dementsprechende Operator heißt hier ''head-tail-Separator'', geschrieben als senkrechter Strich <tt>|</tt>, und wirkt bidirektional, d.h. sowohl synthetisierend als auch analysierend.

<run id="4b8bd2d722e85">[X|Xs] = [1,2,3,4].</run>

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

<code id="4b8bd2d71b996">cons(X,Ys,[X|Ys]).</code>
<run id="4b8bd2d723657">cons(1,[2,3,4],Xs).</run>

Auf diese Weise entsteht die Liste <tt>[1,2,3,4]</tt>.

<run id="4b8bd2d723e33">write([1,2,3,4|[5,6]]).</run>

Das Ergebnis ist nicht etwa <tt>[1, 2, 3, [4, 5, 6]]</tt>. Das Komma zwischen <tt>X</tt> und <tt>Y</tt> wirkt vielmehr wie <tt>cons(X,Y)</tt> bzw. <tt>X|[Y]</tt>. Ausführlich würde obige Anfrage lauten

<run id="4b8bd2d724687">write([1|[2|[3|[4|[5|[6|[]]]]]]]).</run>

Unter Verwendung des head-tail-Separators kann man die obige (informelle) Listendefinition wie folgt ausdrücken.

<code id="4b8bd2d71c162">
islist([]).
islist([X|Xs]) :- islist(Xs).
</code>
<run id="4b8bd2d724e5b">islist([1,2,[3,4],5]).</run>

<tt>member/2</tt> ist bei einige Prolog-Implementierungen ein Systemprädikat. <tt>member(X,Xs)</tt> ist wahr, wenn <tt>X</tt> in Liste <tt>Xs</tt> enthalten ist. 

Wir definieren ein eigenes Prädikat <tt>member/2</tt>:
<code id="4b8bd2d71c908">
member(X,[X|Xs]).
member(X,[Y|Ys]) :- member(X,Ys).
</code>
<run id="4b8bd2d725629">member(3,[1,2,3,4]).</run> 

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 <tt>[1, 2, [3], 4]</tt>, nicht jedoch die Zahl <tt>3</tt>.

<run id="4b8bd2d725e03">member(3,[1,2,[3],4]).</run> 

hingegen gehört [3] zur Liste:
<run id="4b8bd2d7265c4">member([3],[1,2,[3],4]).</run>

Folgende Anfragen sind interessant:
<run id="4b8bd2d726dae">member(b,[a,b,c]).</run>
<run id="4b8bd2d7275d0">member(b,[a,s,c]).</run>
<run id="4b8bd2d727e5b">member(X,[a,b,c]).</run>

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 <tt>findall</tt> benutzt.

<run id="4b8bd2d728977">findall(X,member(X,[a,b,c]),Y).</run>

<run id="4b8bd2d7290c6">member(b,X).</run>

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 <tt>append/3</tt>:
<code id="4b8bd2d71d0cd">
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]):- append(Xs,Ys,Zs).
</code>
Stellen Sie die folgenden Anfragen:
<run id="4b8bd2d72988a">append([a,b],[c,d],L).</run>
<run id="4b8bd2d72a06f">append(L,[c,d],[a,b,c,d]).</run>
<run id="4b8bd2d72a82e">append([a,b],L,[a,b,c,d]).</run>
<run id="4b8bd2d72b041">append(L1,L2,[a,b,c,d]).</run>
<run id="4b8bd2d72bad2">findall(L1,append(L1,L2,[a,b,c,d]),L1).</run>

Die ''Bidirektionalität'' der Prädikatargumente von <tt>append</tt> ermöglichen eine hohe Flexibilität. Nicht jedes Prädikat hat diese Eigenschaft.

Ein häufig benötigtes Prädikat ist <tt>reverse/2</tt>, zur Listenumkehr. Unsere Definition lautet:
<code id="4b8bd2d71d8e9">
reverse([],[]).
reverse([X|Xs],Ys) :- reverse(Xs,Zs), append(Zs,[X],Ys).
</code>
<run id="4b8bd2d72c709">reverse([1,2,3,4],X).</run>

=== Übungsaufgaben ===
# Machen Sie sich im Manual mit den Systemprädikaten für die Arbeit mit Listen vertraut.
# Definieren Sie folgende einfache Prädikate: <tt>erstes_element/2</tt>, <tt>letztes_element/2</tt>, <tt>vorletztes_element/2</tt>, <tt>loesche/3</tt>, <tt>loesche1/3</tt>, <tt>kein_element/2</tt> und <tt>laenge/2</tt>, mit folgenden Bedeutungen:<br /><tt>erstes_element(X,Ls)</tt>: <tt>X</tt> ist erstes Element der Liste <tt>Ls</tt>.<br /><tt>letztes_element(X,Ls)</tt>: <tt>X</tt> ist letztes Element von <tt>Ls</tt><br/><tt>vorletztes_element(X,Ls)</tt>: <tt>X</tt> ist vorletztes Element von <tt>Ls</tt><br/><tt>element(X,Ls)</tt>: <tt>X</tt> ist Element der Liste <tt>Ls</tt><br/><tt>loesche(X,Ls,Ms)</tt>: <tt>Ms</tt> entsteht aus <tt>Ls</tt> durch Loeschen von <tt>X</tt><br/><tt>loesche1(X,Ls,Ms)</tt>: <tt>Ms</tt> entsteht aus <tt>Ls</tt> durch einmaliges Loeschen von <tt>X</tt><br/><tt>kein_element(X,Ls)</tt>: <tt>X</tt> ist kein Element von <tt>Ls</tt><br/><tt>laenge(Ls,N)</tt>: <tt>N</tt> ist die Laenge der Liste <tt>Ls</tt><br/>
# Definieren Sie <tt>zufallsliste/3</tt>, mit <tt>zufallsliste(N,M,Zs)</tt>, wobei die Zufallszahlenliste <tt>Zs</tt> genau <tt>N</tt> natürliche Zufallszahlen aus [0,<tt>M</tt>-1] enthalten soll.
# Definieren Sie <tt>quicksort/2</tt>, mit <tt>quicksort(X,Y)</tt>, wobei <tt>Y</tt> die sortierte Liste von <tt>X</tt> ist. <tt>X</tt> 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.

====Lösungen====

<code id="4b8bd2d71e082">
/* erstes_element(X,Ls) heisst: X ist erstes Element der Liste Ls*/
erstes_element(X,[X|Rs]).
</code>
<run id="4b8bd2d72cf67">erstes_element(X,[a,b,c,d]).</run>

<code id="4b8bd2d71e843">
/* letztes_element(X,Ls) heisst: X ist letztes Element von Ls */
letztes_element(X,[X]).
letztes_element(X,[K|Rs]):- letztes_element(X,Rs).
</code>
<run id="4b8bd2d72da20">letztes_element(X,[a,b,c,d]).</run>

<code id="4b8bd2d71f0e7">
/* vorletztes_element(X,Ls) heisst: X ist vorletztes Element von Ls */
vorletztes_element(X,[X,Y]).
vorletztes_element(X,[K|Rs]):- vorletztes_element(X,Rs).
</code>
<run id="4b8bd2d72e237">vorletztes_element(X,[a,b,c,d]).</run>

<code id="4b8bd2d71f7ff">
/* element(X,Ls) heisst: X ist Element der Liste Ls */
element(X,[X|Rs]).
element(X,[Y|Rs]):- element(X,Rs).
</code>
<run id="4b8bd2d72ea0c">element(c,[a,b,c,d]).</run>
<run id="4b8bd2d72f1d5">element(f,[a,b,c,d]).</run>
<run id="4b8bd2d72f9a2">element(X,[a,b,c,d]).</run>
<run id="4b8bd2d730175">findall(X,element(X,[a,b,c,d]),Xs).</run>

<code id="4b8bd2d71ffd0">
/* loesche(X,Ls,Ms) heisst: Ms entsteht aus Ls durch Loeschen von X*/
loesche(X,[],[]).
loesche(X,[X|Rs],Qs):- loesche(X,Rs,Qs).
loesche(X,[Y|Rs],[Y|Qs]):- X\=Y, loesche(X,Rs,Qs).
</code>
<run id="4b8bd2d730945">loesche(c,[a,b,c,d,c,g],Ls).</run>

<code id="4b8bd2d72079c">
/* loesche1(X,Ls,Ms) heisst: Ms entsteht aus Ls durch einmaliges Loeschen von X */
loesche1(X,[],[]).
loesche1(X,[X|Rs],Rs).
loesche1(X,[Y|Rs],[Y|Qs]):- X\=Y, loesche1(X,Rs,Qs).
</code>
<run id="4b8bd2d731113">loesche1(c,[a,b,c,d,c,g],Ls).</run>

<code id="4b8bd2d720f76">
/* kein_element(X,Ls) heisst: X ist kein Element von Ls */
kein_element(X,[]).
kein_element(X,[Y|Rs]):- X\=Y, kein_element(X,Rs).
</code>
<run id="4b8bd2d7318e3">kein_element(c,[a,b,d,e,f]).</run>

<code id="4b8bd2d72173a">
/* laenge(Ls,N) heisst: N ist die Laenge der Liste Ls */
laenge([],0).
laenge([X|Ls],N):- laenge(Ls,N1), N1 is N-1.
</code>
<run id="4b8bd2d7320b4">laenge([a,b,d,e,f],X).</run>

<code id="4b8bd2d721f1b">
/* zufallsliste */  /* eigentlich: Z is random(M) */
zufallsliste(0,M,[]).
zufallsliste(N,M,[Z|Zs]) :- N>0, N1 is N-1, Z is 123, zufallsliste(N1,M,Zs).
</code>
<run id="4b8bd2d732887">zufallsliste(10,100,Ls).</run>

<code id="4b8bd2d7226bc">
/* quicksort */
quicksort([],[]).
quicksort([X|Xs],Ys) :-
	zerlegung(Xs,X,Kleinere,Groessere),
	quicksort(Kleinere,Ks),
	quicksort(Groessere,Gs),
	append(Ks,[X|Gs],Ys).

zerlegung([],X,[],[]).
zerlegung([Z|Zs],X,[Z|Ks],Gs) :- Z =< X, zerlegung(Zs,X,Ks,Gs).
zerlegung([Z|Zs],X,Ks,[Z|Gs]) :- Z > X, zerlegung(Zs,X,Ks,Gs).

sortiere(Ls) :- zufallsliste(10,200,Xs), quicksort(Xs,Ls).
</code>
<run id="4b8bd2d733074">sortiere(Ls).</run>