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.