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
|
-- 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
|
