Akkumulatormethode

Umkehren einer Liste - Version 1

Ziel ist es, ein Prädikat umkehren/2 festzulegen, mit dem man die Reihenfolge der Elemente einer Liste umkehren kann.

Es gibt verschiedene Ansätze zur Festlegung des umkehren-Prädikats. Der erste hier gezeigte Ansatz benutzt das Hilfsprädikat mit_letztem_element/3.

Regel 1:
[] umgekehrt ergibt []. 
Regel 2:
[K|R] umgekehrt ergibt die Liste L, 
  wenn R umgekehrt die Liste U ergibt und
  wenn U mit zusätzlichem letzten Element K die Liste L ergibt.

Hier eine Umsetzung in Prolog.

mit_letztem_element([], E, [E]).
mit_letztem_element([K|R], E, [K|L]) :- mit_letztem_element(R, E, L).
umkehren([], []).
umkehren([K|R], L) :- umkehren(R, U), mit_letztem_element(U, K, L).

Umkehren einer Liste - Version 2

Man kann das umkehren-Prädikat auch mit der sog. Akkumulatormethode festlegen. Hierbei wird eine Hilfsliste A bei der Verarbeitung der umzukehrenden Liste schrittweise aufgebaut. Zu Beginn ist die Liste A die leere Liste []. Wenn die gesamte umzukehrende Liste verarbeitet ist, enthält A die gewünschte umgekehrte Liste. Beachte, dass dieser Ansatz ein Hilfsprädikat umkehren_mit_akkumulator/3 benutzt.

umkehren(L, U) :-
  umkehren_mit_akkumulator(L, [], U).
umkehren_mit_akkumulator([], A, A).
umkehren_mit_akkumulator([K|R], A, U) :-
  umkehren_mit_akkumulator(R, [K|A], U).

Aufgabe 1

Teste die gezeigten Wissensbasen.
Nutze die Trace-Funktion, um dir die Funktion der "Akkumulator"-Liste zu verdeutlichen.