% Praedikat istEineListe(L): (selbsterklaerend!)

istEineListe([]).
istEineListe([_|L]) :- istEineListe(L).


% Praedikat enthaltenIn(E, L):
% Die Liste L enthaelt mindestens ein Vorkommen des Elements E.

enthaltenIn(E, [E|_]).
enthaltenIn(E, [_|L]) :- 
	enthaltenIn(E, L).


% Praedikat verkettung(X, Y, Z):
% Die Liste Z ist die Verkettung (Katenation) der beiden Listen X und Y.

verkettung([], Y, Y).
verkettung([E|X], Y, [E|Z]) :-
	verkettung(X, Y, Z).


% Praedikat ohneEins(E,Y,Z):
% Die Liste Z ist um genau ein Element kuerzer als Z, und dieses
% Element unifiziert mit E ('Z ist Y ohne ein Vorkommen von E').

ohneEins(E, [E|L],  L).
ohneEins(E, [EE|Y], [EE|Z]) :-
	ohneEins(E, Y, Z).  


% Praedikat gleichlangeListen(X, Y):
% X und Y sind Listen gleicher Laenge. 

gleichlangeListen([], []).
gleichlangeListen([_|X], [_|Y]) :-
	gleichlangeListen(X, Y).


% Praedikat permList(X,Y):
% Die Liste Y ist eine Permutation der Liste X.

permList([], []).
permList([E|X], YY) :-
	gleichlangeListen([E|X], YY), 
	ohneEins(E, YY, Y), 
	permList(X, Y).
	

% Praedikat geordnet(L):
% Die Liste L ist aufsteigend sortiert.
% Wegen des Vergleichsoperators sollten die Elemente der liste L
% unifiziert sein. 

geordnet([]).
geordnet([_]).
geordnet([A,B|L]) :-
	A<B, geordnet([B|L]).
  % ACHTUNG: Ohne die folgende Klausel koennen Listen, in denen ein
  %          Element mehrfach auftritt, nie "geordnet" sein.
geordnet([A,B|L]) :-
	A=B, geordnet([B|L]).

% Praedikat sortiert(X, Y): Y ist eine geordnete Version von X. 
% Benutzt das "generate-and-test" Paradigmas (sehr langsam!!!).

sortiert(X, Y) :-
	permList(X, Y),
	geordnet(Y).


% Praedikat nichtEnthaltenIn(E, L):
% Das Element E taucht nicht in der liste L auf. 
% E sollte unifiziert sein.

nichtEnthaltenIn(_, []). 
nichtEnthaltenIn(E, [F|L]) :-
	E<F, nichtEnthaltenIn(E,L).
nichtEnthaltenIn(E, [F|L]) :-
	E>F, nichtEnthaltenIn(E,L).