1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
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 []
|
