% Beispiele fuer Rekursion in PROLOG

% mitglied(+Element, +Liste)
% entspricht Systemprädikat member
mitglied(X, [X|_]).
mitglied(X, [_|Y]):-
  mitglied(X, Y).

% laenge(+Liste, -Laenge)
% entspricht Systemprädikat length
laenge([], 0).
laenge([_|Y], N):-
  laenge(Y, N1),
  N is N1 + 1.

% schreibListe(+Liste)
schreibListe([]).
schreibListe([Kopf|Restliste]):-
  writeln(Kopf),
  schreibListe(Restliste).
    
% gleich(+Liste1, +Liste2)
gleich([], []).
gleich([X|R1], [X|R2]):-
  gleich(R1, R2).

% praefix(+Liste1, +Liste2)
praefix([], _L).
praefix([X|R1], [X|R2]):-
  praefix(R1, R2).

% suffix(+Liste1, +Liste2)
suffix(L, L).
suffix(L, [_|R]):-
  suffix(L, R).
  
% sortiert(+Liste)
sortiert([]).
sortiert([_]).
sortiert([K1, K2|R]):-
  K1 =< K2,
  sortiert([K2|R]).

% Anzahl eines Elementes in einer Liste
% gezaehlt(+Element, +Liste, -Anzahl)
% gezaehlt mit Kopf-Rest-Methode
gezaehlt(_X, [], 0).
gezaehlt(X, [X|Rest], N):-
  gezaehlt(X, Rest, N1),
  N is N1 + 1.
gezaehlt(X, [_|Rest], N):-
  gezaehlt(X, Rest, N).

% gezaehlt mit Akkumulatortechnik
gezaehltA(X, L, N):-
  gezaehltA(X, L, 0, N).
gezaehltA(_X, [], N, N).
gezaehltA(X, [X|Rest], N0, N):-
  N1 is N0 + 1,
  gezaehltA(X, Rest, N1, N).
gezaehltA(X, [_|Rest], N0, N):-
  gezaehltA(X, Rest, N0, N).

% Erhoehen der Zahlen in einer Zahlenliste
% inc(+Liste1, -Liste2)
inc([], []).
inc([X|Rest1], [Y|Rest2]):-
  Y is X + 1,
  inc(Rest1, Rest2).

% Element an den Anfang der Liste setzen
% push(+Element, +Liste1, -Liste2)
push(X, L, [X|L]).

% Element an das Ende der Liste setzen
% enter(+Element, +Liste1, -Liste2)
enter(X, [], [X]).
enter(X, [Kopf|Rest1], [Kopf|Rest2]):-
  enter(X, Rest1, Rest2).

% Alle Elemente verdoppeln
% doppel(+Liste1, -Liste2)
% erweiterter Gebrauch des Listenoperators mit zwei Kopfelementen
doppel([], []).
doppel([X|Rest1], [X, X|Rest2]):-
  doppel(Rest1, Rest2).

% Element komplett aus einer Liste entfernen
% remove(+Element, +Liste1, -Liste2)
remove(_, [], []).
remove(X, [X|Rest1], Rest2):-
  remove(X, Rest1, Rest2).
remove(X, [Y|Rest1], [Y|Rest2]):-
  X \== Y,
  remove(X, Rest1, Rest2).

% Negative Zahlen aus einer Liste entfernen
% negative_raus(+Liste1, -Liste2)
negative_raus([], []).
negative_raus([X|Rest1], Rest2):- 
  X =< 0, 
  negative_raus(Rest1, Rest2).
negative_raus([X|Rest1], [X|Rest2]):- 
  X >= 0, 
  negative_raus(Rest1, Rest2).
  
% Ersetzen eines Elementes in einer Liste
% subst(Alt, Neu, Liste1, Liste2):-
subst(Alt, Neu, [Alt|Liste1], [Neu|Liste2]):- !,
  subst(Alt, Neu, Liste1, Liste2).
subst(Alt, Neu, [K|R1], [K|R2]):- !,
  subst(Alt, Neu, R1, R2).
subst(_, _, [], []).

% Rueckgabe des letzten Elementes einer Liste
% letztes(+Liste, -Element)
letztes([E], E).
letztes([_|R], E):-
  letztes(R, E).
  
% liste2menge(+Liste, -Menge).
liste2menge(L, M):-
  L=[K|R],
  member(K, R), !,
  liste2menge(R, M).
liste2menge(L, M):-
  L=[K|R],
  liste2menge(R, M1),
  M = [K|M1].
liste2menge([], []).

% palindrom(+Liste)
palindrom([]).
palindrom([_]).
palindrom([K|R]):-
  append(R1, [K], R),
  palindrom(R1).

% permutation(+Liste1, -Liste2)
permutationListe(L1, [K|R]):-
  auswaehlen(K, L1, L2),
  permutationListe(L2, R).
permutationListe([], []).

auswaehlen(E, [E|R], R).
auswaehlen(E, [K|L1], [K|L2]):-
  auswaehlen(E, L1, L2).

% anhaengen(+Liste1, +Liste2, -Liste3)
% entspricht Systemprädikat append
anhaengen([], L, L).
anhaengen([X|L1], L2, [X|L3]):-
  anhaengen(L1, L2, L3).
  
% ist_Liste(+Liste)
ist_Liste([]).
ist_Liste([_Kopf|Restliste]):-
  ist_Liste(Restliste).


% plaetten(+Liste1, -Liste2)
% Terminationsfall
plaetten([], []).

% Das Kopfelement der Liste ist selbst eine Liste
plaetten([X|L1], L2):- 
  X = [_|_],  !,
  plaetten(X, Y), 
  plaetten(L1, L), 
  append(Y, L, L2).

% wie vor, nur dass das Kopfelement die leere Liste ist
plaetten([X|L1], L2):-
  X = [], !,
  plaetten(L1, L2).

% das Kopfelement ist keine Liste
plaetten([X|L1], L2):- 
  plaetten(L1, L), 
  append([X], L, L2).
                  
% uebersetzen(+Liste1, -Liste2)
uebersetzen([], []).
uebersetzen([X|L1], [Y|L2]):- 
  bedeutung(X, Y), 
  uebersetzen(L1, L2).
 
bedeutung(the, der).     
bedeutung(man, mann). 
bedeutung(woman, frau).  
bedeutung(knows, kennt). 
bedeutung(well, gut).
bedeutung(dog,hund).
bedeutung(suck,saugen).
bedeutung(X, X).


% Labyrinth
% Aufruf: sucheWeg(a, []).

sucheWeg(X, L):-
  telefonIn(X),
  writeln('Telefon gefunden!'),
  write('Weg: '), writeln(L).

sucheWeg(X, L):-
  tuer(X, Y),
  not(member(Y, L)),
  sucheWeg(Y, [Y|L]).

% zweite Regel nur nötig, insofern die Türfakten nicht verdoppelt werden
sucheWeg(X, L):-
  tuer(Y, X),
  not(member(Y, L)),
  sucheWeg(Y, [Y|L]).

telefonIn(g).

tuer(a, b).
tuer(b, e).
tuer(b, c).
tuer(d, e).
tuer(c, d).
tuer(e, f).
tuer(g, e).