Aufgabe 1 (1)

Bestimmen Sie jeweils den allgemeinsten Typ der folgenden Haskell-Ausdrücke:

[tail,init,reverse] :: [[a] -> [a]]

not . any (<3) :: (Num a, Ord a) => [a] -> Bool

(length "haskell", Left 4) :: Num a => (Int, Either a b)

[map reverse, filter (=="falco")] :: [[String] -> [String]]

let x = id in map x :: [a] -> [a]

[even x | (x,y) <- zip [1..5] [6..10]] :: [Bool]

Aufgabe 1 (2)

Bestimmen Sie jeweils den allgemeinsten Typ der folgenden Haskell-Funktionen:

second :: [a] -> a
second xs = head (tail xs)

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

double :: (Num a) => a -> a
double x = x*2

palindrome :: Eq a => [a] -> Bool
palindrome xs = reverse xs == xs

twice :: (a -> a) -> a -> a
twice f x = f (f x)

Aufgabe 2 (1)

Zeigen Sie, wie die Listenkomprehension

[f x | x <- xs, p x]

mapfilter :: (a -> b) -> (a -> Bool) -> [a] -> [b]
mapfilter f p xs = map f (filter p xs)

Aufgabe 2 (2)

Drücken Sie die Funktionen map und filter mit Hilfe von foldr aus.

map f = foldr (\x xs -> (f x):xs) []

filter p = foldr (\x xs -> if p x then x:xs else xs) []

Aufgabe 2 (3)

Definieren Sie mit Hilfe von foldl eine Funktion

pack :: [Integer] -> Integer

Beispiel:

pack [3,1,0,7] == 3107

Lösung 2 (3)

pack :: [Integer] -> Integer
pack = foldl (\i v -> 10*i + v) 0

Aufgabe 3 (1)

Im Folgenden sollen KO-Turniere, wie sie etwa bei den Fußballwelt- und -europameisterschaften ausgetragen werden, mit Hilfe des folgenden Haskell Datentyps modelliert werden:

type Ergebnis = (Int, Int)

data KOTurnier = Team Name
               | Match KOTurnier KOTurnier Ergebnis
    deriving (Eq, Show)

Das Ergebnis stellt das Torergebnis des Matches dar. Da es sich um ein KO-Turnier handelt, können Sie in allen folgenden Aufgaben davon ausgehen, dass die Mannschaften ein Spiel nie mit gleicher Torezahl beenden.

Aufgabe 3 (3)

Definieren Sie explizit rekursiv eine Funktion tore :: KOTurnier -> Int, die die Summe aller im Turnier geschossenen Tore zurückgibt!

tore :: KOTurnier -> Int
tore (Match m1 m2 (t1,t2)) = tore m1 + tore m2 + t1 + t2
tore (Team _) = 0

Aufgabe 3 (4)

Definieren Sie explizit rekursiv eine Funktion sieger :: KOTurnier -> String, die den Namen des Gesamtsiegers eines Turniers zurückgibt!

sieger :: KOTurnier -> String
sieger (Team name) = name
sieger (Match m1 m2 (t1,t2)) | t1 > t2   = sieger m1
                             | otherwise = sieger m2

Aufgabe 3 (5)

Definieren Sie explizit rekursiv eine Funktion toraermstesSpiel :: KOTurnier -> (String, String, Int), die die beiden beteiligten Mannschaften des torärmsten Spiels des gesamten Turniers sowie die Summe der im Spiel gefallenen Tore als Tupel zurückgibt!

Lösung 3 (5)

toraermstesSpiel :: KOTurnier -> (String, String, Int)
toraermstesSpiel = tS

tS :: KOTurnier -> (String, String, Int)
tS (Team _) = ("", "", 1000)
tS (Match m1 m2 (t1,t2)) | t < m1t && t < m2t 
                           = (sieger m1, sieger m2, t)
                         | m1t < t && m1t < m2t 
                           = tS m1
                         | otherwise 
                           = tS m2
    where t = t1+t2
          (m1s1, m1s2, m1t) = tS m1
          (m2s1, m2s2, m2t) = tS m2

Aufgabe 3 (6)

Definieren Sie für den algebraischen Datentyp KOTurnier eine foldKOTurnier- Funktion und geben Sie den Typ dieser Funktion an!

foldKOTurnier :: (String -> a) -> 
												           (a -> a -> (Int,Int) -> a) -> 
												           KOTurnier -> a

foldKOTurnier tf mf = m
  where m (Team name) = tf name
        m (Match m1 m2 tore) = mf (m m1) (m m2) tore

Aufgabe 3 (7)

Geben Sie die Funktionen tore' und sieger' mittels foldKOTurnier an!

tore' = foldKOTurnier (\_ -> 0)
                  (\l r (t1,t2) -> l + r + t1 + t2)

sieger' = foldKOTurnier id
                  (\l r (t1,t2) -> if t1 > t2 then l else r)

Aufgabe 4 (1)

(Klausur SS2009)
Sind folgende Prolog-Termpaare unifizierbar? Geben Sie ggf. die jeweiligen Variablenbindungen an bzw. begründen Sie, warum die Unifikation nicht erfolgreich ist.

p(g(X,Y),a,f(X)) und p(g(Z,Z),Z,f(b))
   Nein: X=Z, Y=Z, Z=a und f(a) und f(b) sind nicht unifizierbar.

p([], X, Y) und p(S, [T|S], T)
   Ja: S=[], X=[T], Y=T.

q([[X|Y],f(a)]) und q([Z, f(X)|Y])
   Ja: Z=[a], X=a, Y=[].

Aufgabe 4 (2)

(Klausur SS2010)
Sind folgende Prolog-Termpaare unifizierbar? Geben Sie ggf. die jeweiligen Variablenbindungen an bzw. begründen Sie, warum die Unifikation nicht erfolgreich ist.

f(X,g(h)) und f(g(h),X)
   Ja: X=g(h).

f(f(f(a),b),X) und f(f(Y),b,X)
   Nein: Zweites f ist links zwei-, rechts einstellig.

f(g(X,Y)) und f(g(Y,a))
   Ja: X=Y, Y=a.

f(g(X,h(a)),b) und f(g(Y,X),Y)
   Nein: X=Y, Y=h(a) und Y=b ist ein Widerspruch.

Aufgabe 5 (1)

(Klausur SS2010-2)
Schreiben Sie ein Prolog-Programm für ein Prädikat flatten(L,R) mit der folgenden Bedeutung: für eine Liste L, die eine Liste von Listen ist, enthält die Liste R alle Elemente der Listen in L.

Beispiel:

?- flatten( [ [1,2], [3,4] ], R).
R = [1,2,3,4].

Lösung 5 (1)

Beispiel:

?- flatten( [ [1,2], [3,4] ], R).
R = [1,2,3,4].

Lösung:

flatten([], []).
flatten([[]|Ls], R) :- flatten(Ls, R).
flatten([[El|L1s]|Ls], [El|R]) :- flatten([L1s|Ls], R).

Aufgabe 5 (2)

(Klausur SS2010-2)
Schreiben Sie ein Prolog-Programm für ein Prädikat samesum(L1, L2, L, S) mit der folgenden Bedeutung: Die Liste L ist die Konkatenation der Listen L1 und L2, so dass die Summe aller Zahlen in der Liste L1 gleich der Summe aller Zahlen in der Liste L2 ist und S diese Summe ist.

?- samesum(L1, L2, [1,2,3], S).
L1 = [1,2], L2 = [3], S = 3 ;
false.

?- samesum(L1, L2, [1,0,0,1], S).
L1 = [1], L2 = [0, 0, 1], S = 1 ;
L1 = [1, 0], L2 = [0, 1], S = 1 ;
L1 = [1, 0, 0], L2 = [1], S = 1 ;
false.

Lösung 5 (2)

Beispiel:

?- samesum(L1, L2, [1,2,3], S).
L1 = [1,2], L2 = [3], S = 3 ;
false.

Lösung:

samesum(L1, L2, L, S) :- append(L1, L2, L), 
                           sum(L1, S1), sum(L2, S2), 
                           S1 =:= S2, S is S1.

sum([], 0).
sum([X|Xs], R) :- sum(Xs, R1), R is R1+X.

Aufgabe 5 (3)

In dieser Aufgabe betrachten wir Listen natürlicher Zahlen.

1. Definieren Sie ein Prädikat sorted(X) mit der Bedeutung: X ist eine aufsteigend sortierte Liste.
2. Definieren Sie ein Prädikat permut(X,Y) mit der Bedeutung: Y ist eine Permutation der Liste X. Dabei heißt Y eine Permutation von X, wenn sich Y durch Vertauschen der Reihenfolge der Elemente aus X gewinnen lässt.
3. Definieren Sie mit Hilfe dieser Prädikate ein Prädikat sortlist(X,Y) mit der Bedeutung: Y ist die Sortierung der Liste X.

Lösung 5 (3)

sorted([]).
sorted([_]).
sorted([A,B|Ls]) :- A =< B, sorted([B|Ls]).


permut([X|Xs], Ys) :- count(X, [X|Xs], Xcount), 
                            count(X, Ys, Ycount), 
                            Xcount =:= Ycount.
count(_, [], 0).
count(X, [X|Xs], R) :- count(X, Xs, R1), R is R1+1.
count(X, [Y|Ys], R) :- X \= Y, count(X, Ys, R).

sortList(X, Y) :- permut(X, Y), sorted(Y).

Aufgabe 5 (4)

Definieren Sie in Prolog ein Prädikat teilstueck(L,T) mit der Bedeutung: Die Liste T ist ein Teilstück der Liste L. Dies ist genau dann der Fall, wenn alle Elemente von T in der gleichen Reihenfolge in L auftreten, ohne von anderen Elementen unterbrochen zu werden.

Beispiel: [1,2,3] ist ein Teilstück von [0,1,2,3,4,5], aber weder Teilstück von [0,1,2,77,3] noch von [1,2] oder [5,4,3,2,1].

Lösung 5 (4)

teilstueck(L, T) :- append(_,T, Left), append(Left, _, L).

Aufgabe 6

(Klausur SS2010-2)
Gegeben sei das folgende CHR-Programm:

r1 @ j(X,Y) <=> X =< 1 | Y = X.

r2 @ j(X,Y) <=> X > 1 | X1 is X-1, X2 is X-2, 
                        j(X2,Y2), j(X1,Y1), 
                        Y is Y1+2*Y2.

Ergänzen Sie im Folgenden die Regelanwendungen und die dabei entfernten und erzeugten Constraints für die Eingabe j(4,Z) und geben Sie den Wert an, an den Z gebunden wird:

Weitere Übungen

... gibt's mit Lösungsvorschlägen hier:
fnogatz.github.com/talks/pdp-rep-13/prolog-chr/exercises.html
fnogatz.github.com/talks/pdp-rep-13/haskell/exercises.html

Credits

Thanks to Benjamin Erb for the html5slides and uulm template.

Title image: Miran Lipovača under CC BY-NC-SA 3.0