% -*-prolog-*-
%
% P1 Übungen WS2004/2005
% Musterlösung Blatt 7 (Hans Meine)
%
%---------------------------------------------------------------------
% 1. Datenaggregation
%---------------------------------------------------------------------
%
% Beispieldaten von Aufgabenblatt:
spiel(4,kiel,magdeburg,30,28).
spiel(4,lemgo,essen,27,23).
spiel(4,minden,nordhorn,32,28).
spiel(5,solingen,schwerin,29,32).
spiel(5,nordhorn,lemgo,20,21).
spiel(5,eisenach,wetzlar,28,34).
% (a) sum(+Liste,?Summe)
% berechnet die arithmetische Summe der Elemente einer Liste
sum([], 0).
sum([Kopf|Rest], Summe) :-
sum(Rest, Restsumme),
Summe is Kopf + Restsumme.
% (b) tore(?Mannschaft,?Treffer,?Gegentreffer)
% bestimmt eigene und gegenerische Tore berechnet, unabhängig
% davon, ob das Spiel zu Hause oder auswärts stattfand.
tore(Mannschaft, Treffer, Gegentreffer) :- % Heimspiel
spiel(_, Mannschaft, _, Treffer, Gegentreffer).
tore(Mannschaft, Treffer, Gegentreffer) :- % Auswärtsspiel
spiel(_, _, Mannschaft, Gegentreffer, Treffer).
% (c) tor_verhaeltnis(+Mannschaft, ?Treffer, ?Gegentreffer)
% berechnet Summe aller Tore bzw. Gegentore in allen Spielen der
% Mannschaft, indem alle Ergebnisse in Listen gesammelt und mit
% dem sum/2 aus (a) aufaddiert werden:
tor_verhaeltnis_1(Mannschaft, Treffer, Gegentreffer) :-
findall(Tore, tore(Mannschaft, Tore, _), Trefferliste),
sum(Trefferliste, Treffer),
findall(Gegentore, tore(Mannschaft, _, Gegentore), Gegentrefferliste),
sum(Gegentrefferliste, Gegentreffer).
% (Wie das + im dokumentierten Prädikatskopf schon andeutet, muß
% Mannschaft instanziiert werden, damit findall nur die Spiele
% einer Mannschaft findet.)
%
% Da (d) so ähnlich gelöst werden kann, bilden wir noch ein
% Hilfsprädikat:
% trefferlisten(+Mannschaft, ?Trefferliste, ?Gegentrefferliste)
% bildet die Listen aller Treffer beziehungsweise aller Gegentreffer:
trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste) :-
findall(Tore, tore(Mannschaft, Tore, _), Trefferliste),
findall(Gegentore, tore(Mannschaft, _, Gegentore), Gegentrefferliste).
% ..damit kann tor_verhaeltnis/3 etwas kürzer formuliert werden:
tor_verhaeltnis(Mannschaft, Treffer, Gegentreffer) :-
trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste),
sum(Trefferliste, Treffer),
sum(Gegentrefferliste, Gegentreffer).
% (d) tore_durchschnitt(+Mannschaft,
% ?[[Treffer_Durchschnitt]], ?[[Gegentreffer_Durchschnitt]])
% berechnet die durchschnittliche Zahl von Treffern und
% Gegentreffern pro Spiel einer Mannschaft (unter Benutzung des
% eben definierten trefferlisten/3-Prädikats und des eingebauten
% length/2 für Listen):
tore_durchschnitt(Mannschaft, [[Treffer_Durchschnitt]], [[Gegentreffer_Durchschnitt]]) :-
trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste),
sum(Trefferliste, Treffer),
sum(Gegentrefferliste, Gegentreffer),
length(Trefferliste, [[AnzahlSpiele]]),
[[Treffer_Durchschnitt]] is Treffer / [[AnzahlSpiele]],
[[Gegentreffer_Durchschnitt]] is Gegentreffer / [[AnzahlSpiele]].
% (e) punkte(+Mannschaft, ?Plus, ?Minus)
% berechnet die in einem Spiel von einer Mannschaft erzielten
% Tabellenpunkte, unabhängig davon, ob das Spiel zu Hause oder
% auswä rts stattfand:
punkte(Mannschaft, 2, 0) :-
tore(Mannschaft, Treffer, Gegentreffer),
Treffer > Gegentreffer.
punkte(Mannschaft, 1, 1) :-
tore(Mannschaft, [[Unentschieden_Treffer]], [[Unentschieden_Treffer]]).
punkte(Mannschaft, 0, 2) :-
tore(Mannschaft, Treffer, Gegentreffer),
Treffer < Gegentreffer.
% (f) punkte_verhaeltnis(+Mannschaft, ?Plus, ?Minus)
% errechnet das das Punkteverhältnis aus allen Spielen einer
% Mannschaft.
punkte_verhaeltnis(Mannschaft, Plus, Minus) :-
findall(Plus, punkte(Mannschaft, Plus, _), Pluspunkte),
sum(Pluspunkte, Plus),
findall(Minus, punkte(Mannschaft, _, Minus), Minuspunkte),
sum(Minuspunkte, Minus).
% (g) Man müßte tore/3 und punkte/3 um jeweils eine Argumentstelle für
% den Spieltag und/oder Spieltyp (heimspiel/auswaerts) erweitern,
% ebenso für alle darauf aufbauenden Prädikate, die zur Auswertung
% benötigt werden, und anschließend die findall-Aufrufe in diesen
% Prädikaten dementsprechend um die Bedingungen erweitern, z.B.
punkte_verhaeltnis_spieltyp(Mannschaft, Plus, Minus, Spieltyp) :-
findall(Plus, punkte(Mannschaft, Plus, _, Spieltyp), Pluspunkte),
sum(Pluspunkte, Plus),
findall(Minus, punkte(Mannschaft, _, Minus, Spieltyp), Minuspunkte),
sum(Minuspunkte, Minus).
% wobei punkte/4 aus sechs Regeln der folgenden Form besteht:
punkte(Mannschaft, 2, 0, heimspiel) :-
spiel(_, Mannschaft, _, Treffer, Gegentreffer),
Treffer > Gegentreffer.
punkte(Mannschaft, 2, 0, auswaerts) :-
spiel(_, _, Mannschaft, Gegentreffer, Treffer),
Treffer > Gegentreffer.
% Die Eingrenzung auf einen Saisonteil kann besonders elegant
% erfolgen, wenn man ein Hilfsprädikat definiert wie:
zeitraum(Tag, erste_saisonhaelfte) :- Tag < 18.
zeitraum(Tag, zweite_saisonhaelfte) :- Tag >= 18.
zeitraum(_, ganze_saison).
% damit können dann Anfragen nach beliebigen Zeiträumen ermöglicht
% werden, wie folgt skizziert:
punkte_verhaeltnis_zeitraum(Mannschaft, Plus, Minus, Zeitraum) :-
findall(Plus, (punkte_tag(Mannschaft, Plus, _, Plustag),
zeitraum(Plustag, Zeitraum)), Pluspunkte),
sum(Pluspunkte, Plus),
findall(Minus, (punkte_tag(Mannschaft, Minus, _, Minustag),
zeitraum(Minustag, Zeitraum)), Minuspunkte),
sum(Minuspunkte, Minus).
%---------------------------------------------------------------------
% 2. Umkodieren
%---------------------------------------------------------------------
% schlage_wort_nach(?Deutsch, ?Englisch, ?Woerterbuch)
% sucht Deutsch[[/Englisch]] Wortpaar in Woerterbuch (einer Liste von
% "Paaren", wobei letzteres lt. Aufgabenblatt Listen mit zwei
% Elementen sind).
schlage_wort_nach(Deutsch, Englisch, [[Deutsch, Englisch]|_]).
schlage_wort_nach(Deutsch, Englisch, [_|Woerterbuch]) :-
schlage_wort_nach(Deutsch, Englisch, Woerterbuch).
% schlage_wort_nach(?Deutsch, ?Englisch)
% benutzt ein vorgegebenes Woerterbuch, um ein Wort nachzuschlagen
schlage_wort_nach(Deutsch, Englisch) :-
schlage_wort_nach(Deutsch, Englisch,
[[hund,dog], [mann,man], [frau,woman], [katze,cat],
[die,the], [der,the], [schlaeft,sleeps]]).
% uebersetzung(?Deutsch, ?Englisch)
% kann in beiden Richtungen auf primitive Weise übersetzen, ruft
% einfach auf rekursive Weise auf jedem Wort schlage_wort_nach/2 auf.
uebersetzung([], []).
uebersetzung([[[DeutschesWort]]|[[RestDeutsch]]],
[[[EnglischesWort]]|[[RestEnglisch]]]) :-
schlage_wort_nach([[DeutschesWort]], [[EnglischesWort]]),
uebersetzung([[RestDeutsch]], [[RestEnglisch]]).
% Tests zeigen was passiert, wenn mehrer Wörter gleich übersetzt sind;
% es werden einfach alle Alternativen ausgegeben:
% ?- uebersetzung(Deutsch, [the, dog, sleeps]).
% Deutsch = [die, hund, schlaeft] ;
% Deutsch = [der, hund, schlaeft] ;
% No
% Wenn man unbekannte Wörter behandeln will, kann man natuerlich
% einfach einen Fakt hinzufügen, der das Wort unübersetzt läßt:
schlage_wort_nach(Wort, Wort, []).
% Jetzt funktioniert zwar die folgende Anfrage:
% ?- uebersetzung([der, hund, schlaeft, gut], X).
% X = [the, dog, sleeps, gut]
% aber alternative Anfragen führen zu Unglück:
% X = [the, dog, sleeps, gut] ;
% X = [the, dog, schlaeft, gut] ;
% X = [the, hund, sleeps, gut] ;
% X = [the, hund, schlaeft, gut] ;
% ...
%---------------------------------------------------------------------
% 3. Listenmanipulation
%---------------------------------------------------------------------
% (a) Schreiben Sie zwei Prädikate prefix/2 und suffix/2, die
% überprüfen, ob eine Liste Anfangs- bzw. Endstück einer zweiten
% Liste ist.
prefix([], _).
prefix([E|R], [E|X]) :- prefix(R, X).
suffix(X, X).
suffix(S, [_|X]) :- suffix(S, X).
% Anfragen, bei denen nur der Präfix[[/Suffix]] instanziiert sind,
% terminieren, aber geben nur eine Lösung, bei der die gesamte
% Restliste durch eine Variable dargestellt wird:
% ?- prefix([a,b,c],X).
% X = [a, b, c|_G232] ;
% No
% (b) Implementieren Sie eine Variante von prefix/2 bzw. suffix/2, bei
% denen die leere Liste nicht zur Lösungsmenge gehört.
% Hierfür muß lediglich der Rekursionsabschluß dementsprechend
% geändert werden:
prefix_nonempty([E], [E|_]).
prefix_nonempty([E|R], [E|X]) :- prefix_nonempty(R, X).
suffix_nonempty([E|R], [E|R]).
suffix_nonempty(S, [_|X]) :- suffix_nonempty(S, X).
% (c) Implementieren Sie eine weitere Variante der beiden Prädikate,
% die ausschließlich echte Präfixe bzw. Suffixe ermittelt. Echt
% sei ein Präfix bzw. Suffix einer Liste, wenn es ungleich der
% Liste selbst ist (vgl. Teilmenge <-> echte Teilmenge).
% Hierfür muß wiederum lediglich der Rekursionsabschluß so
% geändert werden, daß die Liste selbst mindestens ein Element
% mehr als der Präfix[[/Suffix]] hat (hier als Varianten der Prädikate
% aus (b), analog auch für die Originale aus (a) machbar):
real_prefix([E], [E,_|_]).
real_prefix([E|R], [E|X]) :- real_prefix(R, X).
real_suffix([E|R], [_,E|R]).
real_suffix(S, [_|X]) :- real_suffix(S, X).
% (d) Vergleichen Sie Unterschiede und Gemeinsamkeiten zwischen den
% Prädikaten prefix/2, suffix/2 und append/3. Wie lassen sich die
% Gemeinsamkeiten bei der Definition der Prädikate ausnutzen?
% Die Beziehungen können am einfachsten durch die folgenden
% Prädikatsdefinitionen ausgedrückt werden:
prefix_by_append(Prefix, List) :-
append(Prefix, _, List).
suffix_by_append(Suffix, List) :-
append(_, Suffix, List).
% Diese Prädikatsdefinitionen verhalten sich in jeder Hinsicht wie
% die einfachsten Prädikate aus (a).
%---------------------------------------------------------------------
% 4. Häufigkeitswörterbuch
%---------------------------------------------------------------------
haeufigkeiten(Text, Haeufigkeiten) :-
% zuerst benutzen wir flatten, weil uns die verschachtelte
% Struktur der Text-Liste nicht interessiert, im Gegenteil bei der
% Rekursion sogar stört:
flatten(Text, Wortliste),
% anschließend sortieren wir alle Woerter, damit unsere
% Zählaufgabe sich darauf beschränkt, Sequenzen von direkt
% aufeinanderfolgenden Wörtern zu zählen:
msort(Wortliste, Woerter),
% jetzt brauchen wir ein Hilfsprädikat, um rekursiv die Liste
% durchzugehen und die Worthäufigkeiten zu bestimmen:
zaehle_woerter(Woerter, [[Haeufigkeiten_Roh]]),
% anschließend ist das Ergebnis noch nach den Wörtern sortiert,
% nicht wie gewünscht zuerst nach den Häufigkeiten, aber das ist
% schnell erledigt:
sort([[Haeufigkeiten_Roh]], Haeufigkeiten).
% zaehle_woerter/2 bekommt die sortierte Liste der Wörter und soll
% Sequenzen von gleichen Wörtern zählen. Hierfür verwenden wir ein
% weiteres Hilfsprädikat, das alle aufeinanderfolgenden Vorkommnisse
% des gleichen Wortes zusammenfaßt und rufen dieses rekursiv für jedes
% neue Wort auf. Mit den Ergebnissen des Hilfsprädikats bauen wir die
% Liste mit den Häufigkeiten auf:
zaehle_woerter([], []).
zaehle_woerter(Woerter, [[Anzahl, Wort]|Haeufigkeiten]) :-
zaehle_wort(Woerter, Wort, Anzahl, Restwoerter),
zaehle_woerter(Restwoerter, Haeufigkeiten).
% zaehle_wort(Wortliste, Wort, Anzahl, Restliste)
% nimmt das erste Wort aus der Wortliste und zählt die folgenden
% Vorkommnisse des gleichen Wortes. Restliste wird mit dem Suffix der
% Wortliste unifiziert, der bleibt wenn alle Vorkommnisse von <Wort>
% entfernt wurden.
% Rekursionsabschluß (nötig, weil die folgenden Regeln nur auf Listen
% mit mindestens zwei Elementen angewendet werden können)
zaehle_wort([Wort], Wort, 1, []).
% Rekursionsabschluß / Zählen beenden, wenn man auf ein anderes Wort
% trifft (und _nur_ dann):
zaehle_wort([Wort,[[NaechstesWort]]|Woerter], Wort, 1, [[[NaechstesWort]]|Woerter]) :-
Wort \= [[NaechstesWort]].
% Rekursion falls Wort noch mehrfach in der Liste - ein Vorkommnis
% wegnehmen und nach diesem Wort weitersuchen/zählen, rekursiv Anzahl
% um einen erhöhen.
zaehle_wort([Wort,Wort|Woerter], Wort, Anzahl, [[RestWoerter]]) :-
zaehle_wort([Wort|Woerter], Wort, Nochanzahl, [[RestWoerter]]),
Anzahl is Nochanzahl + 1.
% Test der Prädikate anhand des "Textes" vom Aufgabenblatt mit Hilfe
% der angegebenen Definition
portray(X) :- write_term(X,[max_depth(30)]).
% und formatiert:
% ?- haeufigkeiten(
% | [[wenn, hinter, fliegen, fliegen, fliegen, fliegen, fliegen, nach],
% | [blaukraut, bleibt, blaukraut, und, brautkleid, bleibt, brautkleid],
% | [wenn, du, denkst, du, denkst, denkst, du, nur, du, denkst]],
% | Haeufigkeiten).
%
% Haeufigkeiten = [[1, hinter],
% [1, nach],
% [1, nur],
% [1, und],
% [2, blaukraut],
% [2, bleibt],
% [2, brautkleid],
% [2, wenn],
% [4, denkst],
% [4, du],
% [5, fliegen]] ;
%
% No