% PCL1 WS2004/2005 Uebungen 9

% Hier findet ihr den Kode
% aus den Folien der Vorlesung "Rekursive Programmiertechniken"


% Linksrekursion
spiel(babuschka(Babuschka)):-
	spiel(Babuschka).
spiel(babuschka).


% Hyponymie
hypo_fakt(ding, objekt).
hypo_fakt(lebewesen, objekt).
hypo_fakt(tier, lebewesen).
hypo_fakt(pflanze, lebewesen).
hypo_fakt(insekt, tier).
hypo_fakt(wirbeltier, tier).
hypo_fakt(reptil, wirbeltier).
hypo_fakt(saeuger, wirbeltier).
hypo_fakt(mensch, saeuger).
hypo_fakt(hund, saeuger).
hypo_fakt(pudel, hund).
hypo_fakt(spitz, hund).
hypo_fakt(dackel, hund).

hypo(X, Y) :-
	hypo_fakt(X, Y).

hypo(X, Y) :-
	hypo_fakt(X, A),
	hypo(A, Y).

% Listen verketten	
append([], L, L).
append([X|L1], L2, [X|L3]) :-
	append(L1, L2, L3).

% Grammatikregeln als Wortlistenverkettung
% S --> NP VP
s(X) :-
	append(Y, Z, X),
	np(Y),
	vp(Z).

% NP --> Eigenname
np([fido]).

% VP --> Vintransitiv
vp([frisst]).

?- s([fido,frisst]).
?- s([frisst,frisst]).


% Listen umkehren "naiv"
naive_reverse([], []).
naive_reverse([X|Rest], Ergebnis) :-
	naive_reverse(Rest, RevRest),
	append(RevRest, [X], Ergebnis).

% Listen umkehren mit Akkumulator
reverse(Liste, UmgekehrteListe) :-
	reverse_akku(Liste, [], UmgekehrteListe).
	
reverse_akku([], Akku, Akku).
reverse_akku([X|Rest], Akku, Ergebnis):-
	reverse_akku(Rest, [X|Akku], Ergebnis).


% Listen flachklopfen
flatten([],[]).       % Leere Liste ist flach
flatten(X,[X]):-      % Terme in flache Listen packen,
	\+ is_list(X).     % die keine Listen sind
flatten([Kopf|Rest], FlacheListe):-
	flatten(Kopf, FlacherKopf),          % Kopf verflachen
	flatten(Rest, FlacherRest),          % Rest verflachen
	append(FlacherKopf, FlacherRest, FlacheListe). 
                                        % und verketten

% Abgeschwaechte Listentypueberpruefung
is_list([]).
is_list([_|_]).

?- flatten([[1,2],[],3], Liste).