FFP - 05

1 files changed, 219 insertions, 0 deletions

diff --git a/ws2015/ffp/blaetter/05/FFP_U05_ApplikativeF.hs b/ws2015/ffp/blaetter/05/FFP_U05_ApplikativeF.hs
new file mode 100644
index 0000000..4f68f18
--- /dev/null
+++ b/ws2015/ffp/blaetter/05/FFP_U05_ApplikativeF.hs
@@ -0,0 +1,219 @@
+-- Fortgeschrittene Funktionale Programmierung, 
+--   LMU, TCS, Wintersemester 2015/16
+--   Steffen Jost, Alexander Isenko
+--
+-- Übungsblatt 05. 18.11.2015
+--
+-- Thema: Applikative Funktoren
+--
+-- 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!
+--  
+--        _____________________________________________________________________
+--       |                                                                     |
+--       | Ziele für dieses Blatt:                                             |
+--       |   * Instanzen für eigene Datentypen schreiben können                |
+--       |   * Applicative Gesetze und Klassenfunktionen kennenlernen          |
+--       |   * Klasse Traversable kennenlernen                                 |
+--       |_____________________________________________________________________|
+--       |
+--    λ_/
+--   /|
+--   / \
+
+import Prelude hiding (Traversable, traverse)
+import Data.Functor
+import Control.Applicative
+
+---- A5-1 Instanzen von Applikativen Funktoren
+--
+--    Gegeben ist eine alternative Datentypdeklaration
+--    für gewöhnliche Listen:
+
+data List a = Nil | Cons a (List a)
+  deriving (Eq, Show)
+  
+{- 
+-- Manuell definierte Show-Instanz für gewöhnliche Schreibweise:
+instance Show a => Show (List a) where
+  show Nil = "[]"
+  show (Cons x Nil) = show x ++ " : " ++ "[]"
+  show (Cons x xs) = show x ++ " : " ++ show xs
+--
+-- Für den Ausdruck gilt damit folgende Schreibweise:
+--       []      entspricht   Nil
+--       (h:t)   entspricht   (Cons h t)
+-}
+
+
+--    In der Vorlesung wurden zwei Möglichkeiten vorgestellt,
+--    Listen zu Applikativen Funktoren zu machen.
+--    In dieser Aufgabe sollen Sie dies nachvollziehen,
+--    d.h. schauen Sie dabei also möglichst _NICHT_ in Folien 4-19 ff.
+--    sondern nur die davor!
+
+
+-- a) Betrachten Sie folgenden fehlerhaften Lösungsversuch.
+--    Der Lösungsversuch kompiliert und lässt sich ausführen,
+--    aber die Gesetze eines Applikativen Funktors werden
+--    missachtet.
+--    Finden Sie durch ausprobieren mindestens ein Gesetz,
+--    welches missachtet wird!
+--
+--    Beispiel:
+--              > pure id <*> Nil2   :: List2 Int -- explizite Typangabe
+--              Nil2
+--      liefert noch keinen Hinweis daruf, dass z.B. das Gesetz "Identität"
+--      verletzt wird -- aber vielleicht wird es für andere Werte als Nil2 verletzt,
+--      oder vielleicht wird ein anderes Gesetz verletzt?! Finden Sie es heraus!
+--
+--    Hinweis: Achten Sie bei Ihren Tests in GHCI darauf,
+--      dass auch die richtige Instanz verwendet wird,
+--      z.B. durch explizite Angabe des Typs!
+
+data List2 a = Nil2 | Cons2 a (List2 a) deriving (Show, Eq)
+
+instance Functor List2 where
+  fmap _ Nil2 = Nil2
+  fmap f (Cons2 x xs) = Cons2 (f x) (fmap f xs)
+
+instance Applicative List2 where
+  -- pure :: a -> List2 a           -- Typsignaturen sind in Instanzdeklarationen unzulässig
+  pure x = Nil2
+  -- <*> :: List2 (a -> b) -> List2 a -> List2 b
+  Nil2 <*> _ = Nil2
+  (Cons2 x xs) <*> Nil2       = Nil2
+  (Cons2 x xs) <*> Cons2 y ys = Cons2 (x y) (xs <*> ys)
+
+{-
+ - Nimm:
+ - ghci> pure id <*> (Cons2 () Nil2)
+ - Nil2
+ - Dies verletzt Identität.
+ -}
+
+-- b) Ist folgende Nachbesserung zur a) wirklich besser?
+--    Werden nun alle Gesetze respektiert?
+
+data List3 a = Nil3 | Cons3 a (List3 a) deriving (Show, Eq)
+
+instance Functor List3 where
+  fmap f xs = pure f <*> xs
+
+instance Applicative List3 where
+  -- pure :: a -> List3 a
+  pure x = Cons3 x Nil3
+  -- <*> :: List3 (a -> b) -> List3 a -> List3 b
+  Nil3 <*> _ = Nil3
+  (Cons3 x xs) <*> Nil3       = Nil3
+  (Cons3 x xs) <*> Cons3 y ys =
+    Cons3 (x y) (xs <*> ys)
+
+{-
+ - Nimm:
+ - ghci> pure id <*> (Cons3 () (Cons3 () Nil3))
+ - Cons3 () Nil3
+ - Auch dies verletzt Identität.
+ -}
+
+-- c) Machen Sie es nun selbst richtig!
+--    Machen Sie den Typ List zu einer korrekten Instanz von Applicative!
+--    Experimentieren Sie anschliessend mit ein paar Beispielen.
+
+instance Functor List where
+  fmap f xs = pure f <*> xs
+
+-- Analog zu ZipList
+instance Applicative List where
+  pure x = Cons x (pure x)
+  (Cons x xs) <*> (Cons y ys) = Cons (x y) (xs <*> ys)
+  _ <*> _ = Nil
+
+
+---- A5-2 Kontextfolge
+--
+-- Gegeben ist folgende Funktionsdefinition,
+-- bei der leider die Typsignatur fehlt.
+
+-- a)
+-- Berechnen Sie die Typsignatur selbst manuell, also ohne einfach GHCI zu fragen!
+-- Schlagen Sie ggf. die Typen von pure, (:), (<$>) und (<*>) nach!
+
+folgeA :: Applicative f => [f a] -> f [a]
+folgeA []    = pure []
+folgeA (h:t) = (:) <$> h <*> folgeA t
+
+
+-- b)
+-- Wieder eine Denksportaufgabe:
+-- zu welchem Ergebnis wertet folgende Ausdrücke aus:
+
+a5_2b1 = folgeA [Just 1, Just 27, Just 2]
+-- Just [1, 27, 2]
+a5_2b2 = folgeA [Just 4, Just (sqrt 27), Just (sum [1..100]), Nothing, Just 0]
+-- Nothing
+a5_2b3 = folgeA [[1,2],[3],[4,5]]
+-- [[1,3,4],[1,3,5],[2,3,4],[2,3,5]]
+a5_2b4 = folgeA [ZipList [1,2], ZipList [3], ZipList [4,5]]
+-- ZipList [1, 3, 4]
+a5_2b5 = folgeA [(*2),(+1), negate] $ 3
+-- [6, 4, -3]
+
+
+
+
+---- A5-3 Anwendung von Applikativen Funktoren mit der Typklasse Traversable
+--
+--
+-- Gegeben ist folgende vereinfachte Version 
+-- der Typklasse Traversable (im Original siehe Modul Data.Traversable:
+-- 
+
+class Traversable t where
+  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
+  
+  sequenceA :: Applicative f => t (f a) -> f (t a)
+  sequenceA = traverse id
+  
+
+-- Weiterhin ist folgender Datentyp für Binäre Bäume gegeben:
+  
+data Baum a = Blatt a | Gabel (Baum a) a (Baum a) | Astloch
+  deriving (Show, Eq)
+
+test1 = Gabel (Blatt 42) 1 (Gabel (Gabel Astloch 69 $ Blatt 7) 44 Astloch)
+test2 = Gabel (Blatt [42]) [1,2,3] (Gabel (Gabel Astloch [69,96] $ Blatt [7]) [44,101,0] Astloch)
+
+
+-- a) Machen Sie den Typ "Baum" zu einer Instanz
+-- der Tyklasse Traversable!
+--
+-- Hinweis:
+--  Schauen Sie sich _NICHT_ das Modul Data.Traversable
+--  aus der Standardbibliothek an, da dessen Dokumentation
+--  bereits die Lösung zu dieser Aufgabe als Beispiel behandelt.
+
+instance Traversable Baum where
+  traverse _ Astloch = pure Astloch
+  traverse f (Blatt x) = Blatt <$> f x
+  traverse f (Gabel c1 x c2) = Gabel <$> traverse f c1 <*> f x <*> traverse f c2
+
+-- Beispiele:
+--  > take 1 $ drop 4 $ traverse (\x->[x,-x]) test1
+--  [Gabel (Blatt 42) 1 (Gabel (Gabel Astloch (-69) (Blatt 7)) 44 Astloch)]
+--
+--  > traverse (\x->if x>0 then Just x else Nothing) test1
+--  Just (Gabel (Blatt 42) 1 (Gabel (Gabel Astloch 69 (Blatt 7)) 44 Astloch))
+--
+--  > traverse (\x->if even x then Just x else Nothing) test1
+--  Nothing
+--
+--  > take 2 $ drop 5 $ sequenceA test2
+--  [Gabel (Blatt 42) 1 (Gabel (Gabel Astloch 96 (Blatt 7)) 0 Astloch),Gabel (Blatt 42) 2 (Gabel (Gabel Astloch 69 (Blatt 7)) 44 Astloch)]
+
+
+-- b) Gibt es einen Zusammenhang zwischen folgeA und sequenceA? 
+
+-- folgeA ist sequenceA spezialisiert auf []