6: Listenprädikate

Vier Prädikate zur rekursiven Listenverarbeitung demonstrieren Basistechniken für beliebig komplexe Operationen auf Listen:

% member/2 Zugriff auf Listenelemente.
member(Element,List).
% append/3 Konkatenation von Listen.
append(List1,List2,Konkatlist).
% delete/3 Löschen/Einfügen in Listen.
delete(Element,List,ListDeleted).
% reverse/2 Umkehren von Listen.
reverse(List,ListReversed).

append/3 deklarativ

append([],L,L).
append([H|T1],L2,[H|T3]) :-
    append(T1,L2,T3).

• Die Konkatenation einer Liste L an die leere Liste liefert L als Ergebnis.
• Wenn die Konkatenation der Listen L1 und L2 die Liste L3 ergibt, dann ergibt die Konkatenation der um ein zusätzliches Kopfelement H erweiterten List L1 mit L2 die um denselben Kopf erweiterte Liste L3.

? - append([1 ,2 ,3] ,[4 ,5 ,6] ,L).
Call : (7) append([1 ,2 ,3] , [4 ,5 ,6] , _G2304) ?
Call : (8) append([2 ,3] , [4 ,5 ,6] , _G2392) ?
Call : (9) append([3] , [4 ,5 ,6] , _G2395) ?
Call : (10) append([] , [4 ,5 ,6] , _G2398) ?
Exit : (10) append([] , [4 ,5 ,6] , [4 ,5 ,6]) ?
Exit : (9) append([3] , [4 ,5 ,6] , [3 ,4 ,5 ,6]) ?
Exit : (8) append([2 ,3] , [4 ,5 ,6] , [2 ,3 ,4 ,5 ,6]) ?
Exit : (7) append([1 ,2 ,3] , [4 ,5 ,6] , [1 ,2 ,3 ,4 ,5 ,6]) ?
L = [1 ,2 ,3 ,4 ,5 ,6] ;

prefix/2, suffix/2, sublist/2

% Präfixe der Liste [a,b,c,d]: [],[a],[a,b],[a,b,c],[a,b,c,d]
prefix(P,L) :- append(P,_,L).
% Suffixe der Liste [a,b,c,d]: [],[d],[c,d],[b,c,d],[a,b,c,d]
suffix(S,L) :- append(_,S,L).
% Sublisten der Liste [a,b,c]: [],[a],[a,b],[a,b,c],[b],[b,c],[c]
sublist(SL, L) :- prefix(P,L), suffix(SL,P).

Konkatenation von Listen: append/3

% append/3
% append(L1,L2,L3)
% L3 is the result of concatenating L1 and L2
% L1 o L2 = L3
append([],L,L).
append([H|T1],L2,[H|T3]) :-
    append(T1,L2,T3).
?- append([1,2,3],[4,5,6],[1,2,3,4,5,6]).
true.
?- append([1,2,3],[4,5,6],L).
L = [1,2,3,4,5,6].
?- append(L,[4,5,6],[1,2,3,4,5,6]).
L = [1,2,3].
?- append([1,2,3],L,[1,2,3,4,5,6]).
L = [4,5,6].

Verwendung von append/3

% testen, ob eine Liste die Konkatenation von zwei Listen ist:
% append(+,+,+):
append([a,b,c],[x,y,z],[a,b,c,x,y,z]).
% zwei Listen konkatenieren:
% append(+,+,-):
append([a,b,c],[x,y,z],L).
% Listen zerlegen: append(-,-,+), append(-,+,+), append(+,-,+):
append(X,Y,[a,b,c]).
append(X,[b,c,d],[a,b,c,d]).
append([a,b],X,[a,b,c,d]).

Besonderheiten von append/3

Mit dem Prädikat append/3 können sehr unterschiedliche Funktionen
implementiert werden. Dennoch muss man beachten, dass

• bei jedem Aufruf von append/3 die Liste im ersten Argument komplett abgearbeitet werden muss.
• aufgrund der kompletten Listenabarbeitung Programme mit vielen Aufrufen von append/3 sehr schnell ineffizient werden können.

Man sollte also bei der Verwendung von append/3 in rekursiven
Prädikaten vorsichtig sein.

Löschen eines Elements: delete/3

% delete/3
% delete(Term,Liste1,Liste2)
delete(X,[X|T],T).
delete(X,[H|T1],[H|T2]):-
   delete(X,T1,T2).

delete/3 setzt einen Term und zwei Listen derart in Beziehung, daß Liste2 das Ergebnis des einmaligen Löschens von Term an einer beliebigen Position in Liste1 repräsentiert.

?- delete(b,[a,b,c],[a,c]).
true.
?- delete(c,[a,b,c],X). X=[a,b]
?- delete(X,[a,b,c,d],[a,b,d]).
X = c
?- delete(1,X,[a,b,c]).
X = [1, a, b, c] ;
X = [a, 1, b, c] ;
X = [a, b, 1, c] ;
X = [a, b, c, 1] . 

reverse/2 mit Akkumulator

% reverse/2
% reverse(Liste,UmgekehrteListe)
reverse(L,RL):- reverse(L,[],RL).
% reverse/3
% reverse(Liste,Akkumulator,UmgekehrteListe)
reverse([],RL,RL).
reverse([H|T],RT,RL):-
reverse(T,[H|RT],RL).

Deklarative Idee:

• Die Elemente der ersten Liste werden nacheinander auf einen neuen Stapel gelegt (den Akkumulator, der als leere Liste startet).
• In jedem Schritt schrumpft die erste Liste und wächst der Akkumulator um ein Element.
• Die Elemente aus der ersten Liste geraten im Akkumulator in umgekehrte Reihenfolge (das erste Element kommt als erstes in den Akkumulator und damit an dessen letzten Platz).
• Wenn die erste Liste leer ist, liefert der Akkumulator das Ergebnis

Listenverarbeitung mit Akkumulatorliste

• Tail des Akkumulators steht im Kopf der Regel;
• Zerlegung der Akkumulatorliste erfolgt im rekursiven Aufruf;
• Akkumulatorliste wird mit Rekursion länger

p(...[H|T],TAcc,...):-
...,
p(...,T,[H|TAcc],...),
...

Umdrehen von Listen: naiverev/2 (naive Definition)

Zwei Listen sind zueinander revers, wenn die eine Liste gleich der anderen ist, wenn man die Reihenfolge der Elemente umdreht.

naiverev([],[]).
naiverev([H|T],R) :-
    naiverev(T,RevT),
    append(RevT,[H],R).

Deklarative Idee: Die Umkehrung einer nichtleeren Liste [H|T] ergibt sich, indem man an die Umkehrung von T eine Liste mit dem Kopf H als einzigem Element konkateniert.

?- naiverev([a,b,c],[c,b,a]). true. ?-naiverev([1,[2,3]],X). X=[[2,3],1]. ?-naiverev(X,[a,b,c]). X=[c,b,a]. ?-naiverev([],X). X=[].

Warum naives reverse?

Das naive naiverev/2 wird naiv genannt, weil das zu lösende Problem
eigentlich mit linearer Laufzeit gelöst werden könnte.
Das naive naiverev/2 benötigt jedoch durch den Einsatz von append/3
kubische Laufzeit.

reverse/2 prozedural

? - reverse([a,b,c,d] ,X).
Call : (7) reverse([a,b,c,d] , _G2273) ?
Call : (8) reverse([a,b,c,d] ,[] , _G2273) ?
Call : (9) reverse( [b,c,d] ,[a] , _G2273) ?
Call : (10) reverse( [c,d] ,[b,a] , _G2273) ?
Call : (11) reverse( [d] ,[c,b,a] , _G2273) ?
Call : (12) reverse( [] ,[d,c,b,a] , _G2273) ?
Exit : (12) reverse( [] ,[d,c,b,a] ,[d,c,b,a]) ?
Exit : (11) reverse( [d] ,[c,b,a] , [d,c,b,a]) ?
Exit : (10) reverse( [c,d] ,[b,a] , [d,c,b,a]) ?
Exit : (9) reverse( [b,c,d] ,[a] , [d,c,b,a]) ?
Exit : (8) reverse([a,b,c,d] ,[] , [d,c,b,a]) ?
Exit : (7) reverse([a,b,c,d] , [d,c,b,a]) ?
X = [d,c,b,a]

Differenzlisten

• Eine Differenzliste ist ein Paar von Listen (L1,L2), wobei L2 ein Suffix von L1 repräsentiert.
• Die Elemente der Differenzliste sind die nach Abzug von Suffix L2 verbleibenden Elemente in L1.

Vorteil von Differenzlisten: Konkatenation in einem Schritt

% append_dl/3
% append_dl(DiffList1, DiffList2, DiffList3)
append_dl((A,B),(B,C),(A,C)).

Arbeitsweise von append_dl/3:

?- D1 = ([1 ,2 ,3| T1] ,T1),
D2 = ([4 ,5 ,6| T2],T2),
append_dl(D1 ,D2 ,D3).
D3 = ([1 ,2 ,3 ,4 ,5 ,6| T2] ,T2)
?- append_dl( D1 , D2 , D3 ) .
?- append_dl(([1 ,2 ,3| T1],T1),([4 ,5 ,6| T2],T2), D3 ) .
?- append_dl(( A , B),( B , C),(A,C)).
A = [1 ,2 ,3| T1]
B = T1 = [4 ,5 ,6| T2]
C = T2 => A = [1 ,2 ,3|[4 ,5 ,6| T2 ]] = [1 ,2 ,3 ,4 ,5 ,6| T2] => D3 = (A,C) = ([1 ,2 ,3 ,4 ,5 ,6| T2],T2)

Video über Differenzlisten am Beispiel von append_dl/3.

Beispiel: [1,2,3] als Differenzliste

% [1,2,3] als Differenzliste:
([1,2,3],[])
([1,2,3,4],[4])
([1,2,3,4,5],[4,5])
([1,2,3,4,5,6],[4,5,6])
([1,2,3,4,5,6,7],[4,5,6,7])
...
([1,2,3|T],T)
([1,2,3,a|T],[a|T])
([1,2,3,a,b|T],[a,b|T])
...

Wiederholung:

Aufgaben zu Wiederholung von Listen in Prolog, inklusive der Lösung: