Minimum und Maximum einer Elementliste mit Prolog ermitteln

Ich stecke gerade mitten in den Vorbereitungen für die Klausur im Fach Wissensverarbeitung nächste Woche, weshalb ich zur Zeit nur noch in Horn-Klauseln (gerne auch „umgekehrte allquantifizierte Implikationen“ genannt) denke 😉

Wenn man bereits „normale“ Programmiersprachen kennt, ist das Umdenken in die Logik von Prolog recht anstrengend. Man kann z.B. nicht mal eben einer Variablen einen Wert zuweisen, weil Prolog das einfach selbst macht (das nennt sich dann Unifikation). Außerdem lassen sich die meisten Probleme (siehe unten) nur durch Rekursion lösen. Aber genug der Theorie, hier kommen meine Beispiele zur Ermittlung von Minimum und Maximum mit Prolog.

Zuerst die „normale“ (also rekursive) Variante:

  1. Das Max-/Minimum einer Liste aus lediglich einem Element ist das Element selbst.
  2. Das Max-/Minimum einer Liste aus Kopfelement und Restliste ist das Kopfelement, wenn es auch Max-/Minimum der Restliste ist.
  3. Ansonsten ist das Max-/Minimum einer Liste aus Kopfelement und Restliste das Max-/Minimum der Restliste.
maximum([Kopfelement], Kopfelement).
maximum([Kopfelement|Restliste], Kopfelement) :- maximum(Restliste, Max), Kopfelement@>Max, !.
maximum([_|Restliste], Max) :- maximum(Restliste, Max).
%
minimum([Kopfelement], Kopfelement).
minimum([Kopfelement|Restliste], Kopfelement) :- minimum(Restliste, Min), Kopfelement@<Min, !.
minimum([_|Restliste], Min) :- minimum(Restliste, Min).

Und hier noch die nicht-rekursive Variante, die man sogar ohne Prolog-Kenntnisse verstehen könnte 😉 (member nimmt das erste Element aus der Liste).

maximum(Liste, Maximum) :-
	sort(Liste, SortierteListe),
	reverse(SortierteListe, InvertierteListe),
	member(Maximum, InvertierteListe), !.
%
minimum(Liste, Minimum) :-
	sort(Liste, SortierteListe),
	member(Minimum, SortierteListe), !.

Aufgerufen würde beides wie folgt:

maximum([c,a,b,g,z,s,a], Max).

In der Variablen Max (in Prolog sind alle Wörter mit großem Anfangsbuchstaben Variablen) stünde dann wie von Zauberhand z.

Über uns Stefan

Polyglot Clean Code Developer

2 Kommentare

  1. Hi Stefan,
    Ich habe deine (rekursive) Implementierung gerade mal übernommen und ein bisschen damit gespielt, dabei ist mir aufgefallen, dass bei einer Abfrage dieser Art: minimum([1,3,6,5],3) ich ein true erhalte; sollte hier nicht ein false ausgegeben werden, da doch die 3 eben nicht das kleinste Element ist? Vielleicht habe ich aber hier auch einfach was nicht so richtig verstanden. Freue mich schon auf die Auflösung!
    Viele Grüße,
    Johannes

  2. Hallo Johannes,

    das ist eine gute Frage. Ich habe die Funktion noch nie mit Konstanten ausprobiert, sondern immer nur mit Variablen. Leider habe ich auch keinen Prolog-Interpreter mehr laufen und mein letzter Einsatz ist 8 Jahre her. Daher kann ich dir leider nicht weiterhelfen :-/

    Ich weiß nur noch, dass „true“ auch heißt, dass es noch weitere Lösungen gibt (oder so). Hast du darauf mal ein Semikolon (;) eingegeben?

    Viele Grüße!
    Stefan

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax