/*Was ist eine Liste?
z.B. 
[a,b,c,d] (in Notation mit Restlistenoperator [a|[b,c,d]]
[] (leere Liste)
*/

/*Einfachste Prädikate: Kopf und Rest einer Liste*/
kopf(K,[K|_]).
rest(R,[_|R]).

/*
Rekursion über Listen
element/2 (= member/2)
Beispielabfragen: ?- element(a,[b,c,a]). ergibt YES
				  ?- element(X,[b,c,a]). ergibt X = b YES;X = c YES etc.
*/

%einfacher Fall: X ist Element einer Liste mit X als Kopf
element(X,[X|_]).

%Rekursion: Wenn X nicht im Kopf ist, muss es im Rest sein
element(X,[_|R]) :-
				element(X,R).
				
%verkette zwei Listen
%Beispiel: ?- verkette([a,b],[c,d],L). ergibt L=[a,b,c,d]
%Dazu muss man die erste Liste bis zum Ende durchgehen, 
% und die zweite Liste ans Ende kopieren

% A) Abbruchbedingung: die leere Liste mit Liste L verkettet ist eben L 
verkette([],L,L).

% B) Rekursion: gehe Element für Element zum Ende der ersten Liste
%               und kopiere den Kopf
%               dabei jeweils in die Ergebnisliste
verkette([K|R],L,[K|R1]) :-
				verkette(R,L,R1).



%Ein Element kann in einer Liste gestrichen werden, wenn es der Kopf ist
%Ergebnis ist die kopflose Liste (der Rest)

streiche(Kopf,[Kopf|Rest],Rest).


%Ist das Element nicht am Kopf, kopiere diesen in die Ergebnisliste.
%Versuche das Element im Rest zu streichen und damit den Rest der
%Ergebnisliste zu produzieren

streiche(X,[Kopf|Rest],[Kopf|Rest1]) :-
				streiche(X,Rest,Rest1).
				
				
insert(X,L,[X|L]).

insert(X,[K|R],[K|R1]) :-
		insert(X,R,R1).
				

permutation1([],[]).
permutation1(L,[K|R]) :-
		streiche(K,L,L1),
		permutation(L1,R).
		
permutation2([],[]).
permutation2([K|R],L) :-
	permutation2(R,L1),
	insert(K,L1,L).


%Streiche jedes zweite und weitere Vorkommen eines Terms in einer Liste
%Bespiel uniq([a,b,c,a,b],L) ergibt YES, L = [a,b,c]

uniq([],[]).
uniq([Kopf|Rest],[Kopf|Rest1]) :-
							loesche_alle(Kopf,Rest,NeuerRest),
							uniq(NeuerRest,Rest1).

%Loesche alle Vorkommen eines Terms in einer Liste

loesche_alle(_,[],[]).
loesche_alle(Kopf,[Kopf|Rest],Liste) :-
								!,
								loesche_alle(Kopf,Rest,Liste).
								
loesche_alle(Kopf,[X|Rest],[X|Rest1]) :-
								loesche_alle(Kopf,Rest,Rest1).