diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2015-11-24 14:29:20 +0100 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2015-11-24 14:29:20 +0100 |
commit | 76b9e428426e2afeb67f48c094bbc0225563dd3d (patch) | |
tree | 0c10c68b5963a8e11724cba86879d4c395a7ab4b /ws2015/ffp/blaetter/06/FFP_U06_Monaden.hs | |
parent | 154ed6744254b0d7553e40071656b53382816123 (diff) | |
download | uni-76b9e428426e2afeb67f48c094bbc0225563dd3d.tar uni-76b9e428426e2afeb67f48c094bbc0225563dd3d.tar.gz uni-76b9e428426e2afeb67f48c094bbc0225563dd3d.tar.bz2 uni-76b9e428426e2afeb67f48c094bbc0225563dd3d.tar.xz uni-76b9e428426e2afeb67f48c094bbc0225563dd3d.zip |
FFP - 06 (partially) & 06b
Diffstat (limited to 'ws2015/ffp/blaetter/06/FFP_U06_Monaden.hs')
-rw-r--r-- | ws2015/ffp/blaetter/06/FFP_U06_Monaden.hs | 193 |
1 files changed, 193 insertions, 0 deletions
diff --git a/ws2015/ffp/blaetter/06/FFP_U06_Monaden.hs b/ws2015/ffp/blaetter/06/FFP_U06_Monaden.hs new file mode 100644 index 0000000..f444ad0 --- /dev/null +++ b/ws2015/ffp/blaetter/06/FFP_U06_Monaden.hs | |||
@@ -0,0 +1,193 @@ | |||
1 | -- Fortgeschrittene Funktionale Programmierung, | ||
2 | -- LMU, TCS, Wintersemester 2015/16 | ||
3 | -- Steffen Jost, Alexander Isenko | ||
4 | -- | ||
5 | -- Übungsblatt 06a. 25.11.2015 | ||
6 | -- | ||
7 | -- Thema: Monaden-Gesetze, Erste Schritte mit Monaden und Do-Notation | ||
8 | -- | ||
9 | -- Hier machen wir ein paar erste Schritte mit Monaden. | ||
10 | -- Wer das alles schon kennt und bereits von woanders her | ||
11 | -- mit der Do-Notation vertraut ist, sollte stattessen | ||
12 | -- die B-Version dieses Übungsblattes machen: | ||
13 | -- einen applikativen Parser bauen. | ||
14 | -- | ||
15 | -- Gehen Sie diese Datei durch und bearbeiten Sie | ||
16 | -- alle Vorkommen von undefined bzw. die mit -- !!! TODO !!! | ||
17 | -- markierten Stellen. Testen Sie Ihre Lösungen mit GHCi! | ||
18 | |||
19 | |||
20 | ---- A6-1 Monaden Gesetze nachweisen | ||
21 | -- | ||
22 | -- | ||
23 | -- a) | ||
24 | -- Auf Folie 04-42 fehlt der Beweis für die Assoziativität | ||
25 | -- Maybe-Instanz für die Typklasse Monad. | ||
26 | -- Führen Sie den Beweis aus! | ||
27 | -- (Geht ganz analog zu den anderen beiden Beweisen, d.h. | ||
28 | -- Definitionen ausfalten und umformen. | ||
29 | -- Bei Abgabe: Bitte zusätzlich kurze Begründung für jeden Schritt angeben!) | ||
30 | {- | ||
31 | Zu Zeigen: | ||
32 | Ausdruck | ||
33 | m >>= (\x-> ((f x) >>= g)) | ||
34 | ist gleich zu | ||
35 | (m >>= f) >>= g | ||
36 | -} | ||
37 | |||
38 | -- !!! TODO !!! | ||
39 | |||
40 | |||
41 | -- b) | ||
42 | {- Beweisen Sie, dass folgende Definition | ||
43 | |||
44 | instance Monad [] where | ||
45 | return x = [x] -- (Mo1) | ||
46 | xs >>= f = concat (map f xs) -- (Mo2) | ||
47 | |||
48 | das Monaden-Gesetz "Links-Identität" einhält! | ||
49 | |||
50 | Folgende Definition sind dabei eventuell nützlich: | ||
51 | |||
52 | concat :: [[a]] -> [a] | ||
53 | concat [] = [] -- (CcN) | ||
54 | concat (xs:xss) = xs ++ concat xss -- (CcC) | ||
55 | |||
56 | (++) :: [a] -> [a] -> [a] | ||
57 | (++) xs [] = xs -- (ANr) | ||
58 | (++) [] ys = ys -- (ANl) | ||
59 | (++) (x:xs) ys = x : (xs ++ ys) -- (ACl) | ||
60 | |||
61 | map :: (a -> b) -> [a] -> [b] | ||
62 | map _ [] = -- (MpN) | ||
63 | map f (x:xs) = (f x) : (map f xs) -- (MpC) | ||
64 | -} | ||
65 | |||
66 | -- !!! TODO !!! | ||
67 | |||
68 | |||
69 | |||
70 | |||
71 | ---- A6-2 Either-Monade und Do-Notation | ||
72 | -- | ||
73 | -- In der vorletzten Vorlesung am 12.11. haben wir gesehen | ||
74 | -- wie der Datentyp Either der Standardbibliothek zum | ||
75 | -- Funktor gemacht werden kann. | ||
76 | -- | ||
77 | -- Machen Sie diesen Datentyp nun zu einer Monade! | ||
78 | -- Um Namenskonflikten aus dem Weg zu gehen, | ||
79 | -- definieren wir Either einfach noch mal neu: | ||
80 | |||
81 | data Entweder a b = Eines a | Anderes b | ||
82 | deriving (Show, Eq) | ||
83 | |||
84 | -- Die Idee ist dabei die gleiche wie bei Maybe, | ||
85 | -- nur das "Nothing" hier noch einen Wert tragen kann. | ||
86 | |||
87 | instance Functor (Entweder a) where | ||
88 | fmap f (Anderes x) = Anderes $ f x | ||
89 | fmap _ (Eines x) = Eines x -- Because x@(Either a b) is not (Either a c), even if we can prove that x is Left. | ||
90 | |||
91 | instance Applicative (Entweder a) where | ||
92 | pure = Anderes | ||
93 | (Anderes f) <*> (Anderes x) = Anderes $ f x | ||
94 | (Eines x) <*> _ = Eines x -- ditto | ||
95 | _ <*> (Eines x) = Eines x | ||
96 | |||
97 | instance Monad (Entweder a) where | ||
98 | (Anderes a) >>= f = f a | ||
99 | (Eines x) >>= _ = Eines x -- ditto | ||
100 | |||
101 | -- Applicative Tests: | ||
102 | -- (*) <$> (Anderes 3) <*> (Anderes 4) | ||
103 | -- (*) <$> (Eines 3) <*> (Anderes 4) | ||
104 | -- (*) <$> (Anderes 3) <*> (Eines 4) | ||
105 | |||
106 | |||
107 | -- b) | ||
108 | -- Verallgemeinern Sie folgende gewöhnlichen Funktionsdefinition, | ||
109 | -- welche Kenntnis des Typs Entweder voraussetzen. | ||
110 | -- Schreiben Sie jeweils eine generische Fassung, | ||
111 | -- welche nur die Monaden-Instanz oder, wenn möglich, | ||
112 | -- nur Applicative voraussetzt: | ||
113 | |||
114 | -- b1) Beispiel: | ||
115 | multEnt :: (Num b) => (Entweder a b) -> (Entweder a b) -> (Entweder a b) | ||
116 | multEnt (Anderes x) (Anderes y) = Anderes (x * y) | ||
117 | multEnt (Anderes _) other = other | ||
118 | multEnt other _ = other | ||
119 | |||
120 | |||
121 | multEnt_M :: (Num b, Monad m) => m b -> m b -> m b | ||
122 | multEnt_M = multEnt_A -- The monad-applicative proposal was implemented ;-) | ||
123 | |||
124 | multEnt_A :: (Num b, Applicative f) => f b -> f b -> f b | ||
125 | multEnt_A a b = (*) <$> a <*> b | ||
126 | |||
127 | |||
128 | -- b2) | ||
129 | foo :: (Entweder a (b->c)) -> (Entweder a b) -> (Entweder a c) | ||
130 | foo (Anderes f) (Anderes x) = Anderes $ f x | ||
131 | foo (Eines a) _ = Eines a | ||
132 | foo _ (Eines a) = Eines a | ||
133 | |||
134 | foo_M :: (Monad m) => (m (b->c)) -> (m b) -> (m c) | ||
135 | foo_M = foo_A | ||
136 | |||
137 | foo_A :: (Applicative m) => (m (b->c)) -> (m b) -> (m c) | ||
138 | foo_A f x = ($) <$> f <*> x | ||
139 | |||
140 | |||
141 | -- b3) | ||
142 | ifM :: (Entweder a Bool) -> (Entweder a b) -> (Entweder a b) -> (Entweder a b) | ||
143 | ifM (Anderes True) x _ = x | ||
144 | ifM (Anderes False) _ y = y | ||
145 | ifM (Eines a) _ _ = Eines a | ||
146 | |||
147 | ifM_M :: (Monad m) => m Bool -> m b -> m b -> m b | ||
148 | ifM_M = ifM_A | ||
149 | ifM_A :: (Applicative f) => f Bool -> f b -> f b -> f b | ||
150 | ifM_A b x y = bool <$> x <*> y <*> b | ||
151 | |||
152 | |||
153 | |||
154 | bool :: a -> a -> Bool -> a | ||
155 | -- ^ This should really be in Prelude (Data.Bool at least) | ||
156 | bool x _ True = x | ||
157 | bool _ x False = x | ||
158 | |||
159 | |||
160 | |||
161 | ---- A6-3 Do - Notation | ||
162 | -- | ||
163 | -- Implementieren Sie folgende Funktion unter Verwendung der Do-Notation: | ||
164 | -- Hinweis: Einfach den Typen folgen, alles andere kommt von allein! | ||
165 | |||
166 | filterM :: Monad m => (a -> m Bool) -> [a] -> m [a] | ||
167 | filterM p = foldr trav (return []) | ||
168 | where | ||
169 | trav x xs = bool (x :) id <$> p x <*> xs -- Applicative is cooler than do notation ;-) | ||
170 | |||
171 | trav' x xs = do -- But if I must … | ||
172 | include <- p x | ||
173 | xs' <- xs | ||
174 | return $ case include of | ||
175 | True -> x : xs' | ||
176 | False -> xs' | ||
177 | |||
178 | -- Beispiele zum Testen: | ||
179 | silly1 :: Int -> Maybe Bool | ||
180 | silly1 0 = Nothing | ||
181 | silly1 x = Just $ even x | ||
182 | |||
183 | silly2 :: Int -> [Bool] | ||
184 | silly2 0 = [] | ||
185 | silly2 x | even x = [False,True,True,False] | ||
186 | | otherwise = [False,False] | ||
187 | |||
188 | -- > filterM silly [1..10] | ||
189 | -- Just [2,4,6,8,10] | ||
190 | |||
191 | -- > filterM silly $ [1..10]++[1,0,1] | ||
192 | -- Nothing | ||
193 | |||