Literatur
|
|
| |
Typklassen
|
beschreiben gemeinsame Schnittstellen für mehrere Typen
|
| |
Beispiel
|
class Eq a where
== :: a -> a -> Bool
/= :: a -> a -> Bool
x /= y == not (x == y)
instance Eq Bool where
x == y = ...
instance Eq Int where
x == y = ...
instance Eq a => Eq [a] where
x == y = ...
|
| |
|
Gleiche Eigenschaften verschiedener Typen zusammengefasst.
|
| |
|
Gibt es auch gleiche Eigenschaften (Operationen) für verschiedene Typkonstruktoren
|
|
Ja, aber welche?
|
Beispiele
|
für einstellige Typkonstruktoren (Konstruktoren mit einem Typparameter)
|
|
Maybe .
[.]
(String, .)
Either String .
data Tree a
= Null
| Tip a
| Bin (Tree a) (Tree a)
data Tree2 a
= Empty
| Node (Tree2 a) a (Tree2 a)
String -> .
|
|---|
| |
|
Welche Eigenschaften für verschiedene Typkonstruktoren
kommen wiederholt vor?
|
|
Elementweise Verarbeitung aller enthaltenen Werte, ohne die Struktur zu verändern.
|
1. Beispiel |
|
[a]
|
map :: (a -> b) -> ([a] -> [b])
map f [] = []
map f (x : xs) = f x : map f xs
|
| |
2. Beispiel |
|
Maybe a
|
mapMaybe :: (a -> b) -> (Maybe a -> Maybe b)
mapMaybe f Nothing = Nothing
mapMaybe f (Just x) = Just (f x)
|
| |
3. Beispiel |
|
(String, a)
|
mapSnd :: (a -> b) -> (String, a) -> (String, b)
mapSnd f (x, y) = (x, f y)
|
| |
4. Beispiel |
|
Either String a
|
mapEither :: (a -> b) -> (Either String a -> Either String b)
mapEither f (Left s) = Left s
mapEither f (Right x) = Right (f x)
|
| |
5. Beispiel |
|
Tree2 a
|
data Tree2 a
= Empty
| Node (Tree2 a) a (Tree2 a)
mapTree2 :: (a -> b) -> (Tree2 a -> Tree2 b)
mapTree2 f Empty = Empty
mapTree2 f (Node l x r) = Node (mapTree2 f l) (f x) (mapTree2 f r)
|
| |
|
6. Beispiel: Tree a?
|
|
data Tree a
= Null
| Tip a
| Bin (Tree a) (Tree a)
mapTree :: (a -> b) -> (Tree a -> Tree b)
mapTree f Null = Null
mapTree f (Tip x) = Tip (f x)
mapTree f (Bin l r) = Bin (mapTree f l) (mapTree f r)
|
| |
|
7. Beispiel: String -> a?
|
|
mapFct :: (a -> b) -> ((String -> a) -> (String -> b))
mapFct f g = \ s -> f (g s)
mapFct f g = f . g
|
Wunsch
|
nicht map, mapMaybe, mapSnd, mapEither, mapTree, mapTree2, mapFct
sondern Überladen eines Bezeichner fmap
|
|
Eine Typklasse für Typkonstruktoren
|
Lösung
|
Funktoren
|
Definition
|
class Functor f where
fmap :: (a -> b) -> (f a -> f b)
|
| |
|
Die Variable f steht für einen Typkonstruktor mit einem Typ-Parameter,
nicht für einen einfachen Typ.
|
Instanzen |
für die Beispiele
|
[]
|
instance Functor [] where
fmap = map
|
| |
Maybe
|
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
|
| |
(,) String
|
instance Functor ((,) String) where
fmap f (x, y) = (x, f y)
|
| |
Either String
|
instance Functor (Either String) where
fmap f (Left s) = Left s
fmap f (Right x) = Right (f x)
|
| |
Tree2
|
instance Functor Tree2 where
fmap f Empty = Empty
fmap f (Node l x r) = Node (fmap f l) (f x) (fmap f r)
|
| |
|
Tree?
|
|
instance Functor Tree where
fmap f Null = Null
fmap f (Tip x) = Tip (f x)
fmap f (Bin l r) = Bin (fmap f l) (fmap f r)
|
| |
|
String ->, Funktionen mit Argument vom Typ String?
|
|
instance Functor ((->) String) where
fmap :: (a -> b) -> (String -> a) -> (String -> b)
fmap f g = f . g
|
| |
|
r ->, beliebige Funktionen?
|
|
instance Functor ((->) r) where
fmap :: (a -> b) -> (r -> a) -> (r -> b)
fmap f g = f . g
|
| |
|
Gesetze für fmap?
|
|
fmap id = id
fmap (f . g) = fmap f . fmap g
Schon eines der Gesetze reicht, das andere kann daraus abgeleitet werden.
|
| |
|
Wer stellt diese Gesetze sicher?
|
|
Nicht das Haskell-Sprachsystem!
Dieses ist Aufgabe der Entwickler.
|
|
Viele weitere Strukturen sind Funktoren.
|
|
|
Funktionale Programmierung: Funktoren
