FFP - Blatt 2

1 files changed, 206 insertions, 0 deletions

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