From ab9484b343abd995cba915bb0ba4be8907dfa6ec Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Fri, 13 Nov 2015 23:45:26 +0000 Subject: Shorter lecture names --- ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs | 206 --------------------------- 1 file changed, 206 deletions(-) delete mode 100644 ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs (limited to 'ws2015/FFP/blaetter/02') diff --git a/ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs b/ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs deleted file mode 100644 index 5f2d936..0000000 --- a/ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs +++ /dev/null @@ -1,206 +0,0 @@ --- Fortgeschrittene Funktionale Programmierung, --- LMU, TCS, Wintersemester 2015/16 --- Steffen Jost, Alexander Isenko --- --- Übungsblatt 02. 28.10.2015 --- --- Thema: --- --- Anweisung: --- Gehen Sie diese Datei durch und bearbeiten Sie --- alle Vorkommen von undefined bzw. die mit -- !!! TODO !!! --- markierten Stellen. Testen Sie Ihre Lösungen mit GHCi! - - --- | A2-1 Funktionsdefinitionen --- --- Implementieren Sie folgende grundlegenden, --- bekannten Funktionen in Haskell. --- Selbst wenn Sie die Funktion nicht kennen, --- sollte Ihnen der Typ die korrekte Lösung ermöglichen! --- - -import Prelude hiding (uncurry,flip,(.),map,zip,zipWith,zip,foldl) - -import qualified Data.Map as P - --- Hinweis: Das import-Statement müssen Sie jetzt noch nicht verstehen, --- es ist nur notwendig zur Vermeidung von Namenskonflikten mit der --- Standardbibliothek, welche die meisten dieser Funktionen bereits enthält. - --- a) Uncurrying --- > uncurry (/) (1,2) == 0.5 -uncurry :: (a -> b -> c) -> ((a,b) -> c) -uncurry f (a,b) = f a b - --- b) Anwendung einer Funktion mit zwei Argumenten auf ein Paar --- > (1,2) ||> (/) == 0.5 -(||>) :: (a,b) -> (a -> b -> c) -> c -p ||> f = uncurry f p - - --- c) Vertauschung der Reihenfolge der Funktionsargumente --- > flip (/) 2 1 == 0.5 -flip :: (a -> b -> c) -> (b -> a -> c) -flip f b a = f a b - - --- d) Funktionskomposition --- > ((\x->x+3) . (\y->y*2)) 1 == 5 -(.) :: (b -> c) -> (a -> b) -> a -> c -(.) f g x = f $ g x - - --- e) Map (im Gegensatz zu A1-3 dieses Mal ohne List-Comprehension) --- > map (+10) [1,2,3,4] == [11,12,13,14] -map :: (a -> b) -> [a] -> [b] -map _ [] = [] -map f (x:xs) = f x : map f xs - - --- f) zip: --- > zip ['a','b','c'] [1,2,3,4,5] = [('a',1),('b',2),('c',3)] -zip :: [a] -> [b] -> [(a,b)] -zip [] _ = [] -zip _ [] = [] -zip (x:xs) (y:ys) = (x, y) : zip xs ys - - --- g) Zippen mit Funktionsanwendung: --- > zipWith (+) [1..] [1..3] == [2,4,6] -zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] -zipWith f xs ys = map (uncurry f) $ zip xs ys - - --- h) Falten nach links: --- > foldl (flip (:) ) [] [1..3] == [3,2,1] --- > foldl (\acc x -> x : acc)) [] [1..3] == [3,2,1] -foldl :: (b -> a -> b) -> b -> [a] -> b -foldl _ x [] = x -foldl f x (y:ys) = foldl f (f x y) ys - - - --- | A2-2 LambdaTerme --- --- Betrachten Sie die Lösung zur A1-1 g): - -data LambdaTerm = LVar Char - | LAbs Char LambdaTerm - | LApp LambdaTerm LambdaTerm - --- Ein paar Lambda Terme zum Testen: -lTerm_x = LVar 'x' -lTerm_y = LVar 'y' -lTerm_id = LAbs 'x' lTerm_x -lTerm_xx = LApp lTerm_x lTerm_x -lTerm_t = LAbs 'x' $ LApp lTerm_y lTerm_xx -lTerm_yk = LAbs 'y' $ LApp lTerm_t lTerm_t - --- a) Implementieren Sie eine Eq-Instanz für den Datentyp LambdaTerm! --- --- (Wer Lambda-Kalkül kennt: Zur Vereinfachung der Aufgabe --- ignorieren wir die übliche alpha-Äquivalenz, d.h. --- (LAbs 'x' $ LVar 'x') und (LAbs 'y' $ LVar 'y') --- dürfen als verschieden betrachtet werden) - -instance Eq LambdaTerm where - (LVar a) == (LVar b) = a == b - (LVar _) == _ = False - (LAbs a t_a) == (LAbs b t_b) = a == b && t_a == t_b - (LAbs _ _) == _ = False - (LApp t_a t'_a) == (LApp t_b t'_b) = t_a == t_b && t'_a == t'_b - (LApp _ _) == _ = False - --- b) Implementieren Sie die eine Show-Instanz für LambdaTerm. --- Achten Sie dabei auf eine korrekte Klammerung, aber --- verschwenden Sie erst einmal keine Zeit darauf, --- überflüssige Klammern zu vermeiden. - -instance Show LambdaTerm where - show (LVar a) = "LVar '" ++ pure a ++ "'" - show (LAbs a t) = "LAbs '" ++ pure a ++ "' (" ++ show t ++ ")" - show (LApp t t') = "LApp (" ++ show t ++ ") (" ++ show t' ++ ")" - - --- | A2-3 Klassendeklaration --- --- a) Deklarieren Sie eine Klasse "FinMap" für endliche partielle Abbildungen, welche folgende Operationen bereitsstellt: --- 1) "emptyM" liefert eine leere Abbildung --- 2) "insertM x a m" fügt die Abbildung [x->a] in die Abbildung m ein. --- Falls x schon enthalten war, dann wird es überschrieben. --- 3) "lookupM x m" liefert Nothing zurück, falls x nicht in m enthalten ist; --- ansonsten wird der für x gespeicherte Wert z zurückgeliefert (in Just verpackt) --- Die Funktion "lookupM" darf dabei annehmen, dass für x eine Vergleichsoperation vorliegt!?! - -class FinMap m where - emptyM :: m k v - insertM :: Ord k => k -> v -> m k v -> m k v - lookupM :: Ord k => k -> m k v -> Maybe v - -- Can we get around using constraints here without using the MultiParamTypeClasses language extension? - --- b) Machen Sie folgenden Datentyp zu einer Instanz der Typklasse Map: - --- data AL a b = AL [(a,b)] -newtype AL a b = AL [(a,b)] -- Äquivalent zur vorherigen Zeile. - -- newtype kann und darf verwenden werden, - -- wenn man nur einen Konstruktor mit nur einem Argument hat. - -- Dies erlaubt GHC eine Optimierung durchzuführen. - deriving (Show, Read, Eq) - -instance FinMap AL where - emptyM = AL $ [] - insertM x a (AL m) = AL $ (x, a) : [p | p@(x', _) <- m, x' /= x] - lookupM x (AL m) = listToMaybe [y | (x', y) <- m, x' == x] -- Due to lazyness this is no slower than explicitly short-circuiting the search - where - -- This is part of Data.Maybe - listToMaybe [] = Nothing - listToMaybe (x:_) = Just x - - ----- Werte zum anschließendem Testen, auskommentieren, ----- sobald Klasse und Instanz definiert wurden: -testMap0 :: AL Int Bool -testMap0 = emptyM -testMap1 = insertM 1 False testMap0 -testMap2 = insertM 3 False testMap1 -testMap3 = insertM 4 True testMap2 -testMap4 = insertM 2 True testMap3 - - --- Hinweis: --- Partielle Abbildungen wie hier durch Assoziationslisten zu implementieren, --- ist nicht bensonders effizient, da der Zugriff auf ein Element im Allgemeinen --- den Aufwand O(n) hat (man muss die ganze Liste abklappern - es könnte sich ja --- um das letzte Element der Liste handeln). --- Mit Suchbäumen läßt sich der Aufwand bekanntermaßen auf O(log n) reduzieren. --- Wer noch Lust & Zeit hat, kann versuchen, dies selbst zu implementieren --- und zur einer weiteren Instanz von FinMap machen. --- --- Die Standardbibliothek sieht zur Abstraktion hier keine solche Klasse vor, --- sondern bietet lediglich eine konkrete, effiziente Implementierung von --- endlichen Abbildungen an: Data.Map, welche wir in der kommenden Vorlesung --- betrachten werden. --- --- Dies kann man natürlich ganz schnell zu einer Instanz von FinMap machen. Wie? - -data Map k v = Tip - | Branch k v (Map k v) (Map k v) - -instance FinMap Map where - emptyM = Tip - insertM k v Tip = Branch k v Tip Tip - insertM k v (Branch k' v' lt gt) - | k == k' = Branch k v lt gt - | k < k' = Branch k' v' (insertM k v lt) gt - | otherwise = Branch k' v' lt (insertM k v gt) - lookupM _ Tip = Nothing - lookupM k (Branch k' v' lt gt) - | k == k' = Just v' - | k < k' = lookupM k lt - | otherwise = lookupM k gt - -instance FinMap P.Map where - emptyM = P.empty - insertM = P.insert - lookupM = P.lookup -- cgit v1.2.3