SDA SE Wiki

Software Engineering for Smart Data Analytics & Smart Data Analytics for Software Engineering

User Tools

Site Tools


Ein Prolog-Beispiel

Vorab ein Hinweis: Diese Implementation des Sortierens ist natürlich gnadenlos ineffektiv (sogar der schlechtestmögliche Sortieralgorithmus). Tatsächlich würde man das Sortieren anders implementieren, aber zur Demonstration machen wir es erst mal so.

Wenn wir eine Sortieroperation in einer klassischen, imperativen Programmiersprache ansehen, kann man auf sehr viele unterschiedliche Algorithmen kommen, die unterschiedliche Güte haben. Im Kern allerdings machen sie alle das selbe: Eine Permutation erzeugen, die die Eigenschaft hat, sortiert zu sein.

In Prolog könnte man das beispielsweise so ausdrücken:

sortList(Unsortiert, Sortiert) :- permutation(Unsortiert,Sortiert), sortiert(Sortiert).

Was nichts anderes besagt als: Y ist die sortierte Liste von X, wenn Y eine Permutation von X ist, und sortiert ist. permutation ist in SWI-Prolog bereits vorgegeben, so das wir uns darüber keine Gedanken mehr machen müßen, aber wann ist eine Liste sortiert? Die leere Liste () ist es auf jeden Fall, also:

sortiert([]).

Das sagt aus, das die leere Liste immer sortiert ist, unabhängig von weiteren Bedingungen.

Aber was ist mit nicht-leeren Listen? Listen mit einem Element sind es auch auf jeden Fall, also:

sortiert([_]).

Gut, nun haben wir die Trivialfälle abgearbeitet, was ist mit Listen bei denen es wirklich interessant ist? Die sind sortiert, wenn das erste Element kleiner oder gleich dem Zweiten ist, und, die Liste ab dem Zweiten auch sortiert ist. Also:

sortiert([A|[B|T]]) :- A =< B, sortiert([B|T]).

Genauer Gelesen: Eine Liste, die mit A beginnt, und mit einer Liste weiter geht, die mit einem B beginnt, und mit einem T weitergeht, ist sortiert, falls A kleiner oder gleich B ist, und die Liste, die mit B beginnt, und mit T weiter geht, sortiert ist. Genau das was wir ja eigendlich wollten.

Hier treffen wir zum ersten mal auf die Prolog-typische Listenkonstruktion [H|T]. Diese besagt das eine Liste (mit umschloßen) ein Erstes Element hat (Head), und eine Restliste (Tail). T kann durchaus die Leere Liste sein, wenn die momentane Liste nur ein Element hat, aber in unserem Beispiel grade beschäftigen wir uns nur mit Listen, die 2 Elemente haben (weil wir die Fälle 1 Element oder 0 Elemente ja schon behandelt haben).

Prolog-Fakten haben immer die Form: Rechte Seite ⇒ Linke Seite, also “Wenn Rechts erfüllt ist, dann auch Links”.

research/jtransformer/prologbeispiel.txt · Last modified: 2018/05/09 01:59 (external edit)

SEWiki, © 2019