From b91812f31131580b751f610164f9c3d24b7c5eaa Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Sat, 31 Oct 2015 01:06:10 +0100 Subject: FFP - Blatt 2 --- .../blaetter/02/FFP_U02_Typklassen.hs | 206 +++++++++++++++++++++ 1 file changed, 206 insertions(+) create mode 100644 ws2015/fortgeschrittene_funktionale_programmierung/blaetter/02/FFP_U02_Typklassen.hs (limited to 'ws2015') diff --git a/ws2015/fortgeschrittene_funktionale_programmierung/blaetter/02/FFP_U02_Typklassen.hs b/ws2015/fortgeschrittene_funktionale_programmierung/blaetter/02/FFP_U02_Typklassen.hs new file mode 100644 index 0000000..5f2d936 --- /dev/null +++ b/ws2015/fortgeschrittene_funktionale_programmierung/blaetter/02/FFP_U02_Typklassen.hs @@ -0,0 +1,206 @@ +-- 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