home

Funktionale Programmierung: Einfache Listenoperationen

Prof. Dr. Uwe Schmidt FH Wedel

Einfache Listenoperationen

Aufgabe 1

length	Zeigen Sie durch einen Induktionsbeweis, dass für alle Listen xs und ys gilt:
	length (xs ++ ys) = length xs + length ys

Aufgabe 2

Duale Listen	Eine duale Sicht auf Listen ist die, Elemente an das Ende einer Liste anzuhängen. Folgender Datentyp ist dafür geeignet (Snoc = Cons rückwärts gelesen).
	data RList a = Nil \| Snoc (RList a) a
	Schreiben Sie Konversionsfunktionen, die normale Listen in diese Struktur überführen und umgekehrt und die elementaren Zugriffsfunktionen rHead, rTail, rInit, rLast:
	listToRList :: [a] -> RList a rlistToList :: RList a -> [a] rHead :: RList a -> a rTail :: RList a -> RList a rInit :: RList a -> RList a rLast :: RList a -> a

?	Welche Laufzeiten haben diese Funktionen?
	rLast, rInit: O(1) die anderen: O(n)

Aufgabe 3

splitAt	sei folgendermaßen definiert:
	splitAt :: Int -> [a] -> ([a], [a]) splitAt n xs = (take n xs, drop n xs)
	Entwickeln Sie eine Implementierung, die die beiden Teillisten mit einem Durchlauf durch die Argumentliste direkt berechnet.

Aufgabe 4

Mengen als Listen von Intervallen
Motivation	Mengen von Zahlen können durch aufsteigend sortierte Listen von Intervallen repräsentiert werden.
	type NumSet = [Interval] type Interval = (Int, Int)
Invarianten	Für die Intervalle soll gelten, dass sie abgeschlossene Intervalle der natürlichen Zahlen repräsentieren. Es muss also gelten dass die untere Grenze kleiner oder gleich der oberen Grenze ist.
	Für die Listen soll gelten, dass die Intervalle aufsteigend sortiert sind und dass sich keine benachbarten Intervalle überlappen oder aneinander stoßen. Es soll also immer nur die minimale Anzahl von Intervallen zur Repräsentation einer Menge verwendet werden.
Aufgabe	Schreiben sie zwei Funktionen zur Überprüfung, ob diese Bedingungen für einen Wert eingehalten werden.
	invNumSet :: NumSet -> Bool invInterval :: Interval -> Bool
Aufgabe	Entwickeln Sie Funktionen zum Testen, ob ein Element in einer Menge enthalten ist, zum Einfügen eines Elements, zum Einfügen eines Intervalls und zur Mengenvereinigung.
	isIn :: Int -> NumSet -> Bool insert :: Int -> NumSet -> NumSet insert' :: Interval -> NumSet -> NumSet union :: NumSet -> NumSet -> NumSet -- Hilfsfunktionen merge :: Interval -> Interval -> Interval overlap :: Interval -> Interval -> Bool
Tests	Entwickeln Sie Test-Beispiele für die Funktionen

Letzte Änderung: 27.03.2015

© Prof. Dr. Uwe Schmidt

Prof. Dr. Uwe Schmidt FH Wedel