From 17af38d7b43fbb8d2105de5e01fe27795a724119 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Wed, 18 Nov 2015 16:50:48 +0100 Subject: FFP - 05 --- ws2015/ffp/blaetter/05/FFP_U05_ApplikativeF.hs | 219 +++++++++++++++++++++++++ 1 file changed, 219 insertions(+) create mode 100644 ws2015/ffp/blaetter/05/FFP_U05_ApplikativeF.hs (limited to 'ws2015') 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 [] -- cgit v1.2.3