home

Funktionale Programmierung: Grundlegende Konzepte

Prof. Dr. Uwe Schmidt FH Wedel

Grundlegende Konzepte

Aufgabe 1

Gegeben	f :: Integer -> Integer g :: Integer -> (Integer -> Integer) h :: ... h x y = f (g x y)

?	Welchen Typ besitzt h?

?	Welche Gleichungen sind korrekt?
	h = f . g h x = f . (g x) h x y = (f . g) x y

Aufgabe 2

uncurry	definieren Sie eine Funktion uncurry, die eine Funktion mit Currying in eine Funktion ohne Currying konvertiert, also eine inverse Funktion zu curry.
	Zeigen Sie, dass folgende Eigenschaften gelten
	curry (uncurry f) x y = f x y uncurry (curry f) (x, y) = f (x, y)
Typen	Bestimmen Sie die Typen der Ausdrücke
	curry . uncurry uncurry . curry

Aufgabe 3

>>>, &&& und ***	Seien folgende Funktionen (Operatoren) gegeben:
	(f >>> g) x = (g . f) x (f &&& g) x = (f x, g x) (f *** g) = (fst >>> f) &&& (snd >>> g)
?	Welche Typen besitzten >>>, &&& und ***?
?	Gilt das folgende Gesetz?
	(f &&& g) >>> fst = f
?	Gilt das folgende Gesetz?
	(f &&& g) >>> snd = g
?	Gilt das folgende Gesetz?
	h >>> (f &&& g) = (h >>> f) &&& (h >>> g)

Aufgabe 4

fib	Definieren Sie eine Funktion fib zur Berechnung der Fibonacci-Zahlen ab 0
fib2	Definieren Sie eine Funktion fib2, die lineare Laufzeit besitzt.

collatz	Definieren Sie eine Funktion collatz, die berechnet wieviele Rekursionsschritte benötigt werden, um eine natürliche Zahl n >= 1 auf 1 zu reduzieren. Folgende Reduktionsregel sind dabei anzuwenden: Wenn n gerade ist, so wird n halbiert, wenn n ungerade ist, so wird n verdreifacht und um 1 erhöht.
collatz1	Definieren Sie eine endrekursive Variante dieser Funktion.

cmax	Definieren Sie eine Funktion cmax, die für ein Intervall von Zahlen das Maximum der Collatz-Funktion berechnet. Nutzen Sie die vordefinierten Funkt min und max.

imax	Definieren Sie eine Funktion imax, die für ein Intervall von Zahlen das Maximum einer ganzzahligen Funktion berechnet. Formulieren Sie die obige Funktion cmax so um, dass sie mit imax arbeitet.

imax2	Entwickeln Sie eine Funktion die die Position und den Wert bestimmt, an der das Maximum angenommen wird. Versuchen Sie, eine endrekursive Lösung zu finden (mit einer lokalen Hilfsfunktion).

Aufgabe 5

Quicksort	Der Quicksort-Algorithmus kann auf folgende Weise spezifiziert werden:
	qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x : xs) = qsort lessX ++ [x] ++ qsort greaterX where lessX = [ y \| y <- xs, y < x ] greaterX = [ y \| y <- xs, y >= x ]
Ineffizienz	Bei der Ausführung der Funktion qsort wird in jedem Rekursionsschritt die Liste xs zwei mal durchlaufen, einmal für lessX und einmal für greaterX.
Optimierung	Verändern Sie den Algorithmus so, dass die beiden Teillisten gleichzeiting in einem Durchlauf berechnet werden.

Letzte Änderung: 12.03.2012

© Prof. Dr. Uwe Schmidt

Prof. Dr. Uwe Schmidt FH Wedel