home

Funktionale Programmierung: Listenoperationen

Prof. Dr. Uwe Schmidt FH Wedel

Listenoperationen

Aufgabe 1

Wiederholung	Schreiben Sie eine Funktion reverse', die in einer Zeit proportional zur Länge der Eingabeliste arbeitet. Tipp: Benutzen Sie eine Hilfsfunktion zum Akkumulieren des Resultats.
?	Lösung?
	reverse' x = reverse1 x [] where reverse1 [] res = res reverse1 (x : xs) res = reverse1 xs (x : res)
HUnit	Entwickeln Sie einfache Testfälle für die Überprüfung, dass die eigene reverse' Funtion genaus so arbeitet wie die vordefinierte reverse Funktion. Die Dokumentation für HUnit befindet sich im Modul Test.HUnit in der ghc library (Test.HUnit.Base) Suche in der Dokumentation auf hackage ). Ein Tutorial über HUnit gibt es im dem Haskell-Wiki.
?	Ein einfacher Test?
	import Test.HUnit ... testReverse = runTestTT reverseTests reverseTests = "reverse" ~: test [ "reverse' == reverse" ~: test (map tc1 values) , "reverse' . reverse' == id" ~: test (map tc2 values) ] where values = ["", "1", "123", "123456789"] tc1 xs = show xs ~: reverse xs ~=? reverse1 xs tc2 xs = show xs ~: xs ~=? (reverse1 . reverse1) xs
foldl und foldr	Versuchen Sie eine Lösung zu finden, die mit einer geeigneten fold-Funktion arbeitet.
?	Lösung?
	reverse' :: [a] -> [a] reverse' = foldl (flip (:)) []

Aufgabe 2

cross	Gegeben sei folgende Funktion:
	cross :: [a] -> [b] -> [(a, b)] cross l1 l2 = [ (x, y) \| x <- l1, y <- l2 ]
	Entwickeln Sie eine gleichwertige Funktion, die nicht mit list comprehension formuliert ist, sondern durch concat und map.
?	Lösung?
	cross' :: [a] -> [b] -> [(a,b)] cross' l1 l2 = concat (map (\x -> (map (\y -> (x,y)) l2)) l1) cross'' :: [a] -> [b] -> [(a,b)] cross'' l1 l2 = concat (map f1 l1) where f1 x = map f2 l2 where f2 y = (x,y)

Aufgabe 3

takeWhile, dropWhile	takeWhile :: (a -> Bool) -> [a] -> [a] takeWhile p [] = [] takeWhile p (x:xs) \| p x = x : takeWhile p xs \| otherwise = []
	dropWhile :: (a -> Bool) -> [a] -> [a] dropWhile p [] = [] dropWhile p xs@(x:xs') \| p x = dropWhile p xs' \| otherwise = xs
	Zeigen Sie, dass für alle Prädikate p und alle Listen xs gilt:
	takeWhile p xs ++ dropWhile p xs = xs
span	eine Kombination von takeWhile und dropWhile:
	span :: (a -> Bool) -> [a] -> ([a], [a]) span p xs = (takeWhile p xs, dropWhile p xs)
	Entwickeln sie eine Version von span, die die Liste nur einmal abarbeitet.
?	Lösung?
	span' :: (a -> Bool) -> [a] -> ([a], [a]) span' p l@(x:xs) \| not (p x) = ([],l) span' _ [] = ([],[]) span' p (x:xs) = (x:xs',xs'') where (xs',xs'') = span' p xs

Aufgabe 4

inits	Schreiben Sie eine Funktion, die zu einer Liste alle Präfixe berechnet. Diese werden in einer Liste gesammelt.
	inits :: [a] -> [[a]] inits l = ...
	Beispiele
	inits "abc" = ["", "a", "ab", "abc"] inits [1] = [[], [1]] inits [1..] = [[], [1], [1,2], ...]
?	Lösung?
	inits :: [a] -> [[a]] inits [] = [[]] inits (x:xs) = [] : map (x:) (inits xs) -- Ulf Sauer: Heureka! :-D inits = foldr (\ x xs -> [] : map (x:) xs) [[]]

Letzte Änderung: 27.03.2015

© Prof. Dr. Uwe Schmidt

Prof. Dr. Uwe Schmidt FH Wedel