Listen in Prolog

Listen sind endliche Folgen von Elementen. Jedes Element einer Liste besteht aus einem Inhalt und einem Zeiger auf das nächste Element der Liste (bzw. die Restliste). Die Inhalte der Elemente einer Liste können gleichen oder verschiedenen Typs sein.

Der Aufbau einer Liste kann rekursiv beschrieben werden:
Eine Liste ist entweder leer oder sie besteht aus einem Kopfelement und einer (Rest)Liste.

In Prolog werden Listen in eckigen Klammern geschrieben.
(z. B. L=[1,2,3,4] )

Mit dem Listenoperator | kann eine Liste in Kopf und Rest zerlegt werden.
[K|R]=[1,2,3,4] liefert K = 1 und R = [2,3,4]
[K|R]=[[1,2],[3,4]] liefert K =[1,2] und R = [[3,4]]

Das Systemprädikat display(L) zeigt die Struktur einer Liste an.

Weitere Systemprädikate sind:
member(E,L). % E ist Element von L.
append(L1,L2,L) % L = L1 + L2
sort(L,SL). % SL ist die sortierte Liste von L.

Listen eignen sich besonders zur dynamische Datenspeicherung, da Anzahl und Typ ihrer Elemente vorher nicht festehen muss. Sie lassen sich natürlich auch in objektorientierten Sprachen definieren, sind dort aber nicht so einfach zu nutzen wie in Prolog.

Als Beispiele für Listen können Adressbücher, Telefonverzeichnisse, Lexika, Wörterbücher, Wegbeschreibungen angegeben werden.

Fallstudie member

Das Systemprädikat member kann durch ein eigenes Prädikat element selbst implementiert werden.

1. Verbale Beschreibung:
trivialer Fall: E ist Element einer Liste, wenn E der Kopf der Liste ist.
sonst: E ist Element der Liste, wenn es nicht der Kopf ist aber Element der Restliste ist.

2. Formulierung in Prolog:
element(E,L):-L=[K|R], K=E.
element(E,L):-L=[K|R], K\=E,element(E,R).

3. Vereinfachung des Prädikates:
element(E,[E|_]):-!.
element(E,[_|R]):-element(E,R).

1. Vergleichen Sie die Wirkung der Prädikate member und element beim Aufruf mit den Parametern 2 und [2,3,4,3,2].

2. Entwickeln Sie folgende Prädikate: letztes(E,L) / umgedreht(UL,L) / count(L,N)
Orientieren Sie sich an der oben gegebenen Schrittfolge.

Systemprädikat append

Im nächsten Beispiel soll das Anhängen einer Liste L2 an eine Liste L1 untersucht werden.
Trivial ist der Fall, wenn L1 die leere Liste ist. Dann ist die neue Liste gleich der Liste L2.
In allen anderen Fällen wird L1 in seinen Kopf K und die Restliste R zerlegt , L2 an R angehängt und K davorgesetzt.

3. Veranschaulichen Sie die Wirkung des Prädikats an einer Modellliste und programmieren Sie das Systemprädikat append selbst.

Aufbau von Listen zur Datenspeicherung:

Im nächsten Beispiel sollen Kombinationen von 3 verschiedenen Personen aus einer Menge von n Personen gebildet werden.

comb(L,C):-count(L,3),L=C.
comb(L,C):-person(P),not(member(P,L),comb([P|L],C).

4. Beschreiben Sie die Arbeitsweise des Prädikats.

5. Testen Sie das Prädikat. Welche Lösungen werden als erste / letztebei folgender Datenbasis gefunden?
person(alf).
person(bodo).
person(carol).
person(dago).

6. Wieviele Lösungen gibt es insgesamt? Begründen Sie!

7. Erweitern Sie das Prädikat auf eine Auswahl von K Personen.

Listen als Mengen

8. Definieren Sie den Begriff Menge!

9. Welche der folgenden Listen sind auch Mengen?
[1,2,3,2,1] / [1,2,3,4,5,6]

10. Entwickeln Sie ein Prädikat menge/2, das eine Liste in eine Menge umwandelt.