Literatur
|
LYAH: Functors, Applicative Functors and Monoids
|
| |
Applicative
|
Typklasse für applikative Funktoren
|
| |
Motivation
|
Applikative Funktoren sind mächtiger als Funktoren,
aber nicht so mächtig wie Monaden
|
|
Mit Funktoren können aus normalen einstelligen Funktionen
Funktionen für einen Funktor konstruiert werden.
|
|---|
|
Können auch 2-, 3- und n-stellige Funktionen geliftet werden?
|
|
Können auch einfache Werte (nullstellige Funktionen) geliftet werden?
|
Ziel |
lift0 :: a -> f a
lift0 = ...
lift1 :: (a -> b) -> (f a -> f b)
lift1 = fmap
lift2 :: (a -> b -> c) -> (f a -> f b -> f c)
lift2 = ...
lift3 :: (a -> b -> c -> d) -> (f a -> f b -> f c -> f d)
lift3 = ...
...
|
|
An lift1 erkennt man, dass die gesuchte Schnittstelle
Funktor als Oberklasse besitzen muss.
|
|
An lift0 erkennt man, dass eine Operation
zum Liften eines einfachen Wertes zu einem Funktor-Wert benötigt wird.
Diese Funktion wird pure genannt.
|
|
lift2 kann mit Hilfe einer Funktion <*>
(gesprochen: apply) mit folgendem Typ implementiert werden:
|
|
(<*>) :: f (a -> b) -> f a -> f b
|
|---|
|
<*> nimmt einen Funktor-Wert für eine Funktion
und einen Funktor-Wert für ein Argument und berechnet daraus einen
Funktor-Wert für das Resultat
|
|---|
|
lift2 f2 = \ x y -> (f2 <$> x) <*> y
f2 :: a1 -> (b1 -> c1)
x :: f a1
y :: f b1
(f2 <$> x) :: f (b1 -> c1)
y :: f b1
(f2 <$> x) <*> y :: f c1
|
|---|
|
3-stellige Funktionen können jetzt auf 2-stellige
Funktionen zurück geführt werden,
|
|
und damit n-stellige auf (n-1)-stellige
Funktionen.
|
|
lift3 f3 = \ x y z -> ((f3 <$> x) <*> y) <*> z
lift3 f3 x y z = f3 <$> x <*> y <*> z
|
|---|
|
<$> und <*>
sind linksassoziative Operatoren mit Priorität 4,
also sind die Klammern redundant.
|
|
Die Definitionen der lift-Funktionen werden damit so kurz,
dass es sinnvoller ist, diese zu vergessen und
<$> und <*> direkt zu verwenden.
|
| |
Typklasse
|
Dieses ergibt folgende Typklasse für applikative Funktoren
|
|
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
|
|---|
|
vordefiniert in Control.Applicative
|
|---|
| |
pure
|
Ein Wert wird in einen Funktor eingewickelt
|
(<*>) |
nimmt einen Funktor-Wert, der einstellige Funktionen enthält,
und wendet diese Funktionen auf die Werte im 2. Funktor-Wert an.
|
Beispiele
|
für applikative Funktoren
|
|
Maybe .
[.]
(String,.)
Either String .
Tree .
String -> .
|
|---|
| |
1. Beispiel |
|
Maybe a
|
instance Applicative Maybe where
pure :: a -> Maybe a
pure x = Just x
(<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
Just f <*> Just x = Just (f x)
_ <*> _ = Nothing
|
|
Hinweis zur Syntax:
Die spezialisierten Signaturen in der
instance-Definition sind redundant,
aber eine gute Dokumentation und können mit einer Spracherweiterung
{-# LANGUAGE InstanceSigs -#}
zu Beginn einer Datei zugelassen werden.
|
2. Definition |
die die Verwandschaft zum Funktor besser zeigt
|
|
instance Applicative Maybe where
pure = Just
Nothing <*> _ = Nothing
Just f <*> x = fmap f x
|
|---|
| |
|
(<*>) extrahiert,
wenn möglich, eine Funktion f aus dem 1. Argument
und führt damit ein fmap auf dem 2. Argument aus.
|
|
Deshalb die Einschränkung
Functor f => in der Klassendefinition von Applicative.
|
ghci |
λ> :m + Control.Applicative
λ> Just (+ 1) <*> Just 1
Just 2
λ> Just (+ 1) <*> Nothing
Nothing
λ> Nothing <*> Just 1
Nothing
λ> Nothing <*> Nothing
Nothing
|
| |
? |
Was passiert, wenn eine 2-stellige Funktion im Funktor-Wert steht?
|
ghci |
λ> let one = 1::Int
λ> :type pure (+)
pure (+) :: (Applicative f, Num a) => f (a -> a -> a)
λ> :type pure (+) <*> Just one
pure (+) <*> Just one :: Maybe (Int -> Int)
λ> :type pure (+) <*> Just one <*> Just 2
pure (+) <*> Just one <*> Just 2 :: Maybe Int
λ> pure (+) <*> Just one <*> Just 2
Just 3
|
| |
|
Dieses Schema funktioniert mit allen n-stelligen Funktionen mit n >= 1.
|
1. Gesetz
|
|
|
λ> fmap (+) (Just one) <*> Just 2
Just 3
|
|
(<$>) :: (Functor f) => (a -> b) -> f a -> f b
f <$> x = fmap f x
|
2. Beispiel |
|
Listen [.]
|
instance Applicative [] where
pure :: a -> [a]
pure x = [x]
(<*>) :: [a -> b] -> [a] -> [b]
fs <*> xs = [f x | f <- fs, x <- xs]
fs <*> xs = concat [fmap f xs | f <- fs]
fs <*> xs = concat (map (\ f -> map f xs) fs)
|
| |
ghci |
λ> :type (+) <$> [one,2,3]
(+) <$> [one,2,3] :: [Int -> Int]
λ> :type (+) <$> [one,2,3] <*> [10,20]
(+) <$> [one,2,3] <*> [10,20] :: [Int]
λ> (+) <$> [one,2,3] <*> [10,20]
[11,21,12,22,13,23]
|
| |
3. Beispiel
Tree |
data Tree a
= Null
| Tip a
| Fork (Tree a) (Tree a)
|
?
|
instance Applicative Tree ?
|
|
instance Applicative Tree where
pure :: a -> Tree a
pure = Tip
(<*>) :: Tree (a -> b) -> Tree a -> Tree b
Null <*> _t = Null
Tip f <*> xt = fmap f xt
Bin l r <*> xt = bin (l <*> xt) (r <*> xt)
|
| |
ghci |
λ> let ft = Bin (Tip (1 +)) (Tip (* 2))
λ> :type ft
ft :: Num a => Tree (a -> a)
λ> let xt = Bin (Bin (Tip 1) (Tip 2)) (Tip 10)
λ> :type xt
xt :: Num a => Tree a
λ> :t ft <*> xt
ft <*> xt :: Num b => Tree b
λ> ft <*> xt
Bin (Bin (Bin (Tip 2) (Tip 3)) (Tip 11))
(Bin (Bin (Tip 2) (Tip 4)) (Tip 20))
|
| |
Gesetze
|
für applikative Funktoren
|
|
pure f <*> x == fmap f x
pure id <*> x = x
pure f <*> pure x = pure (f x)
|
|---|
|
Zu einem Typkonstruktor kann es mehrere mögliche
Instanzen von Applicative geben.
|
Beipiel |
Listen
|
2. mögliche
Implementierung |
instance Applicative [] where
pure x = repeat x
fs <*> xs = zipWith (\f x -> f x) fs xs
fs <*> xs = zipWith ($) fs xs
repeat :: a -> [a]
repeat x = x : repeat x
|
?
|
Warum diese seltsame Implementierung für pure?
Die sieht nicht minimal aus!
|
|
| |
pure id <*> xs = xs -- für alle xs
|
| = | { Def. von <*> einsetzen } |
| |
zipWith ($) (pure id) xs
|
| = | { Def, von pure } |
| |
zipWith ($) (id : id : ...) xs
|
| = | { zipWith auswerten } |
| |
xs
|
|
|
Nur eine Instance pro Datentyp möglich?
|
?
|
Welche ist besser?
|
|
Keine, beide können auch gleichzeitig sinnvoll sein!
Aber die 1. wird häufiger genutzt (list comprehension).
|
Ausweg |
newtype Typdefinition
|
|
newtype ZipList a = ZipList { getZipList :: [a] }
instance Applicative ZipList where
pure x = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)
|
|---|
| |
|
Ist die 2. Implementierung sinnvoll, Listen in ZipList einwickeln,
applikative Operationen ausführen, anschließend mit
getZipList wieder auswickeln.
|
| |
Tree2 a
|
data Tree2 a
= Empty
| Node (Tree2 a) a (Tree2 a)
|
?
|
instance Applicative Tree2 ?
|
|
instance Applicative Tree2 where
pure x = Node Empty x Empty
Empty <*> xt = Empty
ft <*> Empty = Empty
Node Empty f Empty <*> xt
= fmap f xt
Node lft f rft <*> xt
= Node ...
where
lyt = lft <*> xt
yt = fmap f xt
ryt = rft <*> xt
Wie kann man bei <*> drei Bäume zu einem kombinieren?
|
|
Es gibt Funktoren, die keine applikativen Funktoren sind.
|
Funktionale Programmierung: Applikative Funktoren
