Übung 10

10. Januar 2002 (Abgabe 21. Januar 2002)

Aufgabe 1 (4 Punkte)

Zeigen Sie, dass für die Funktion

sumList [] = 0
sumList (b:y) = b + sumList y

a) sumList (x ++ y) = sumList x + sumList y

b) sumList (x ++ y) = sumList (y ++ x)

gelten.

Aufgabe 2 (2 Punkte)

Beweisen Sie, dass für die Funktion

double [] = []
double (b:y) = (2*b) : double y

double (x ++ y) = double x ++ double y

gilt.

Aufgabe 3 (4 Punkte)

Zeigen Sie, dass für die Funktion length für alle endlichen Listen x und y die Gleichung

a) length (x ++ y) = length x + length y

und für alle endlichen Listen x die Gleichung

b) length (double x) = length x

gilt.

Aufgabe 4 (2 Punkte)

Beweisen Sie durch Induktion über x, dass für alle endlichen Listen x und y die Gleichung

sumList (x ++ (a:y)) = a + sumList (x ++ y)

gilt.

Aufgabe 5 (4 Punkte)

Beweisen Sie (evtl. mit Hilfe von Aufgabe 4), dass für alle endlichen Listen x die Gleichung

sumList (double x) = sumList (x ++ x)

gilt.

Aufgabe 6 (4 Punkte)

Die Funktion

concat [] = []
concat (c:z) = c ++ concat z

concat [w] = w

concat (x ++ y) = concat x ++ concat y

gilt.