Funktory, aplikativní funktory, monády
IB016 Seminář z funkcionálního programování
Vladimír Štill, Martin Ukrop
Fakulta informatiky, Masarykova univerzita
Jaro 2018
IB016: Cvičení 03 Jaro 2018 1 / 22
Připomenutí: Maybe, Either, druhy
Maybe: datový typ rošířený o jednu hodnotu
data Maybe a = Just a | Nothing
často: Nothing je selhání
IB016: Cvičení 03 Jaro 2018 2 / 22
Připomenutí: Maybe, Either, druhy
Maybe: datový typ rošířený o jednu hodnotu
data Maybe a = Just a | Nothing
často: Nothing je selhání
Either: sjednocení dvou datových typů
data Either a b = Left a | Right b
často: chybný a korektní výpočet
IB016: Cvičení 03 Jaro 2018 2 / 22
Připomenutí: Maybe, Either, druhy
Maybe: datový typ rošířený o jednu hodnotu
data Maybe a = Just a | Nothing
často: Nothing je selhání
Either: sjednocení dvou datových typů
data Either a b = Left a | Right b
často: chybný a korektní výpočet
Druhy: „typování typů“
Maybe Int :: *
Either :: * -> * -> *
(,) :: * -> * -> *
IB016: Cvičení 03 Jaro 2018 2 / 22
Typová třída Functor
Motivace: Zobecňování funkce map
      map :: (a -> b) -> [a]         -> [b]
treeMap :: (a -> b) -> BinTree a -> BinTree b
         ....
IB016: Cvičení 03 Jaro 2018 3 / 22
Typová třída Functor
Motivace: Zobecňování funkce map
      map :: (a -> b) -> [a]         -> [b]
treeMap :: (a -> b) -> BinTree a -> BinTree b
         ....
Typová třída Functor:
class Functor f where
      fmap :: (a -> b) -> f a -> f b
pro typy, přes které se dá „mapovat“
třída pro „unární typové funkce“, tedy věci druhu * -> *
pravidla ověřuje programátor (!)
instance pro [], BinTree, Maybe, IO, Either e, (->) r, ...
IB016: Cvičení 03 Jaro 2018 3 / 22
Motivace: Co s funkcemi?
Jak aplikovat funkci na hodnotu s kontextem?
(+5) $ Just 2 Just 7
(+5) $ Nothing Nothing
IB016: Cvičení 03 Jaro 2018 4 / 22
Motivace: Co s funkcemi?
Jak aplikovat funkci na hodnotu s kontextem?
(+5) $ Just 2 Just 7
(+5) $ Nothing Nothing
fmap :: Functor f => (a -> b) -> f a -> f b
IB016: Cvičení 03 Jaro 2018 4 / 22
Motivace: Co s funkcemi?
Jak aplikovat funkci na hodnotu s kontextem?
(+5) $ Just 2 Just 7
(+5) $ Nothing Nothing
fmap :: Functor f => (a -> b) -> f a -> f b
Jak aplikovat funkci v kontextu na jinou hodnotu v kontextu?
Just (+5) `apply` Just 2 Just 7
Just (+5) `apply` Nothing Nothing
Nothing `apply` Just 2 Nothing
IB016: Cvičení 03 Jaro 2018 4 / 22
Motivace: Co s funkcemi?
Jak aplikovat funkci na hodnotu s kontextem?
(+5) $ Just 2 Just 7
(+5) $ Nothing Nothing
fmap :: Functor f => (a -> b) -> f a -> f b
Jak aplikovat funkci v kontextu na jinou hodnotu v kontextu?
Just (+5) `apply` Just 2 Just 7
Just (+5) `apply` Nothing Nothing
Nothing `apply` Just 2 Nothing
fmap (+) (Just 5) `apply` Just 2 Just 7
IB016: Cvičení 03 Jaro 2018 4 / 22
Motivace: Co s funkcemi?
Jak aplikovat funkci na hodnotu s kontextem?
(+5) $ Just 2 Just 7
(+5) $ Nothing Nothing
fmap :: Functor f => (a -> b) -> f a -> f b
Jak aplikovat funkci v kontextu na jinou hodnotu v kontextu?
Just (+5) `apply` Just 2 Just 7
Just (+5) `apply` Nothing Nothing
Nothing `apply` Just 2 Nothing
fmap (+) (Just 5) `apply` Just 2 Just 7
Jakého typu bude operátor apply?
IB016: Cvičení 03 Jaro 2018 4 / 22
Motivace: Co s funkcemi?
Jak aplikovat funkci na hodnotu s kontextem?
(+5) $ Just 2 Just 7
(+5) $ Nothing Nothing
fmap :: Functor f => (a -> b) -> f a -> f b
Jak aplikovat funkci v kontextu na jinou hodnotu v kontextu?
Just (+5) `apply` Just 2 Just 7
Just (+5) `apply` Nothing Nothing
Nothing `apply` Just 2 Nothing
fmap (+) (Just 5) `apply` Just 2 Just 7
Jakého typu bude operátor apply?
apply :: Functor f => f (a -> b) -> f a -> f b
IB016: Cvičení 03 Jaro 2018 4 / 22
Typová třída Applicative
class Functor f => Applicative f where
      pure :: a -> f a
      (<*>) :: f (a -> b) -> f a -> f b
definováno v modulu Control.Applicative
rozšíření třídy Functor pro práci s funkcemi v kontextu
funkce pure „obalí“ hodnotu minimální strukturou
(„přidá nejjednodušší kontext“)
IB016: Cvičení 03 Jaro 2018 5 / 22
Typová třída Applicative
class Functor f => Applicative f where
      pure :: a -> f a
      (<*>) :: f (a -> b) -> f a -> f b
definováno v modulu Control.Applicative
rozšíření třídy Functor pro práci s funkcemi v kontextu
funkce pure „obalí“ hodnotu minimální strukturou
(„přidá nejjednodušší kontext“)
Applicative definuje infixové synonymum pro fmap
(<$>) :: (Functor f) => (a -> b) -> f a -> f b
f <$> x = fmap f x
IB016: Cvičení 03 Jaro 2018 5 / 22
Instance třídy Applicative I.
instance Applicative Maybe where
IB016: Cvičení 03 Jaro 2018 6 / 22
Instance třídy Applicative I.
instance Applicative Maybe where
      pure :: a -> Maybe a
      pure = Just
      (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
      Nothing <*> _ = Nothing
      (Just f) <*> something = fmap f something
instance Applicative (Either e) where
IB016: Cvičení 03 Jaro 2018 6 / 22
Instance třídy Applicative I.
instance Applicative Maybe where
      pure :: a -> Maybe a
      pure = Just
      (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
      Nothing <*> _ = Nothing
      (Just f) <*> something = fmap f something
instance Applicative (Either e) where
      pure :: a -> Either e a
      pure = Right
      (<*>) :: Either e (a -> b)
               -> Either e a -> Either e b
      Left e <*> _ = Left e
      Right f <*> r = fmap f r
IB016: Cvičení 03 Jaro 2018 6 / 22
Instance třídy Applicative II.
instance Applicative IO where
IB016: Cvičení 03 Jaro 2018 7 / 22
Instance třídy Applicative II.
instance Applicative IO where
      pure :: a -> IO a
      pure = return
      (<*>) :: IO (a -> b) -> IO a -> IO b
      a <*> b = do
            f <- a
            x <- b
            return (f x)
IB016: Cvičení 03 Jaro 2018 7 / 22
Instance třídy Applicative pro seznamy
Co se seznamy?
[(+5), (*2), (^2)] <*> [2, 3]
IB016: Cvičení 03 Jaro 2018 8 / 22
Instance třídy Applicative pro seznamy
Co se seznamy?
[(+5), (*2), (^2)] <*> [2, 3]
1 Aplikujme každou funkci na každou hodnotu
[2+5, 3+5, 2*2, 3*2, 2^2, 3*2]
⇒ výchozí instance
IB016: Cvičení 03 Jaro 2018 8 / 22
Instance třídy Applicative pro seznamy
Co se seznamy?
[(+5), (*2), (^2)] <*> [2, 3]
1 Aplikujme každou funkci na každou hodnotu
[2+5, 3+5, 2*2, 3*2, 2^2, 3*2]
⇒ výchozí instance
2 Aplikujme každou funkci na jednu hodnotu
[2+5, 3*2]
2 různé instance pro tentýž typ nemůžou být ⇒ nový typ
tzv. ZipList
newtype ZipList a = ZipList { getZipList :: [a] }
      deriving (Show, Eq, Ord, Read)
IB016: Cvičení 03 Jaro 2018 8 / 22
Instance třídy Applicative III.
instance Applicative [] where
IB016: Cvičení 03 Jaro 2018 9 / 22
Instance třídy Applicative III.
instance Applicative [] where
      pure :: a -> [a]
      pure x = [x]
      (<*>) :: [a -> b] -> [a] -> [b]
      fs <*> xs = [f x | f <- fs, x <- xs]
IB016: Cvičení 03 Jaro 2018 9 / 22
Instance třídy Applicative IV.
instance Functor ZipList where
IB016: Cvičení 03 Jaro 2018 10 / 22
Instance třídy Applicative IV.
instance Functor ZipList where
      fmap :: (a -> b) -> ZipList a -> ZipList b
      fmap f (ZipList xs) = ZipList (map f xs)
instance Applicative ZipList where
IB016: Cvičení 03 Jaro 2018 10 / 22
Instance třídy Applicative IV.
instance Functor ZipList where
      fmap :: (a -> b) -> ZipList a -> ZipList b
      fmap f (ZipList xs) = ZipList (map f xs)
instance Applicative ZipList where
      pure :: a -> ZipList a
      pure x = ZipList (repeat x)
      (<*>) :: ZipList (a -> b)
               -> ZipList a -> ZipList b
      ZipList fs <*> ZipList xs =
            ZipList (zipWith (\f x -> f x) fs xs)
IB016: Cvičení 03 Jaro 2018 10 / 22
Pravidla pro třídu Applicative
Identita
(pure id) <*> x ≡ x
Kompozice
(pure (.)) <*> f <*> g <*> x ≡ f <*> (g <*> x)
Homomorfizmus
(pure f) <*> (pure x) ≡ pure (f x)
Výměna
u <*> (pure y) ≡ (pure ($ y)) <*> u
(vícero párů závorek je implicitních)
IB016: Cvičení 03 Jaro 2018 11 / 22
Pravidla pro třídu Applicative
Identita
(pure id) <*> x ≡ x
Kompozice
(pure (.)) <*> f <*> g <*> x ≡ f <*> (g <*> x)
Homomorfizmus
(pure f) <*> (pure x) ≡ pure (f x)
Výměna
u <*> (pure y) ≡ (pure ($ y)) <*> u
(vícero párů závorek je implicitních)
Jako důsledek bude pro instanci platit také
(pure f) <*> x = fmap f x
IB016: Cvičení 03 Jaro 2018 11 / 22
Aplikace bězných funkcí na hodnoty v kontextu
Definice funkcí liftAX pro zjednodušení práce s Applicative:
fmap (+) (Just 5) <*> (Just 2) Just 7
IB016: Cvičení 03 Jaro 2018 12 / 22
Aplikace bězných funkcí na hodnoty v kontextu
Definice funkcí liftAX pro zjednodušení práce s Applicative:
fmap (+) (Just 5) <*> (Just 2) Just 7
(+) <$> (Just 5) <*> (Just 2) Just 7
IB016: Cvičení 03 Jaro 2018 12 / 22
Aplikace bězných funkcí na hodnoty v kontextu
Definice funkcí liftAX pro zjednodušení práce s Applicative:
fmap (+) (Just 5) <*> (Just 2) Just 7
(+) <$> (Just 5) <*> (Just 2) Just 7
liftA2 (+) (Just 5) (Just 2) Just 7
IB016: Cvičení 03 Jaro 2018 12 / 22
Aplikace bězných funkcí na hodnoty v kontextu
Definice funkcí liftAX pro zjednodušení práce s Applicative:
fmap (+) (Just 5) <*> (Just 2) Just 7
(+) <$> (Just 5) <*> (Just 2) Just 7
liftA2 (+) (Just 5) (Just 2) Just 7
liftA2 :: Applicative f =>
                  (a -> b -> c) -> f a -> f b -> f c
liftA2 f a b = f <$> a <*> b
Existují i varianty pro další arity, viz dokumentace.
IB016: Cvičení 03 Jaro 2018 12 / 22
Ukázka: vyhodnocování výrazů I.
data Expr = Con Float
               | Add Expr Expr | Sub Expr Expr
               | Mul Expr Expr | Div Expr Expr
               deriving (Eq, Show)
IB016: Cvičení 03 Jaro 2018 13 / 22
Ukázka: vyhodnocování výrazů I.
data Expr = Con Float
               | Add Expr Expr | Sub Expr Expr
               | Mul Expr Expr | Div Expr Expr
               deriving (Eq, Show)
eval :: Expr -> Float
eval (Con x) = x
eval (Add x y) = eval x + eval y
eval (Sub x y) = eval x - eval y
eval (Mul x y) = eval x * eval y
eval (Div x y) = eval x / eval y
IB016: Cvičení 03 Jaro 2018 13 / 22
Ukázka: vyhodnocování výrazů II.
eval' :: Expr -> Maybe Float
eval' (Con x) = Just x
eval' (Add x y) = liftA2 (+) (eval' x) (eval' y)
eval' (Sub x y) = liftA2 (-) (eval' x) (eval' y)
eval' (Mul x y) = liftA2 (*) (eval' x) (eval' y)
eval' (Div x y) = liftA2 (/) (eval' x) yy
   where yy = if eval' y == Just 0
                        then Nothing
                        else eval' y
IB016: Cvičení 03 Jaro 2018 14 / 22
Motivace: Co s funkcemi vytvářejícími kontext?
Jak aplikovat funkci na hodnotu v kontextu?
fmap :: Functor f => (a -> b) -> f a -> f b
IB016: Cvičení 03 Jaro 2018 15 / 22
Motivace: Co s funkcemi vytvářejícími kontext?
Jak aplikovat funkci na hodnotu v kontextu?
fmap :: Functor f => (a -> b) -> f a -> f b
Jak aplikovat funkci v kontextu na hodnotu v kontextu?
(<*>) :: Applicative f =>
            f (a -> b) -> f a -> f b
IB016: Cvičení 03 Jaro 2018 15 / 22
Motivace: Co s funkcemi vytvářejícími kontext?
Jak aplikovat funkci na hodnotu v kontextu?
fmap :: Functor f => (a -> b) -> f a -> f b
Jak aplikovat funkci v kontextu na hodnotu v kontextu?
(<*>) :: Applicative f =>
            f (a -> b) -> f a -> f b
Jak aplikovat funkci, která produkuje hodnotu v kontextu, na
hodnotu v kontextu?
apply2 :: Applicative f =>
               f a -> (a -> f b) -> f b
IB016: Cvičení 03 Jaro 2018 15 / 22
Typová třída Monad
class Applicative m => Monad m where
      return :: a -> m a
      (>>=) :: m a -> (a -> m b) -> m b
      (>>) :: m a -> m b -> m b
            x >> y = x >>= \_ -> y
      fail :: String -> m a
            fail msg = error msg
definováno v modulu Control.Monad
logické rozšíření třídy Applicative pro pohodlnou práci s
funkcemi vytvářejícími kontext
funkce fail se volá například pri selhání vzoru v do-notaci
IB016: Cvičení 03 Jaro 2018 16 / 22
Instance třídy Monad I.
instance Monad Maybe where
IB016: Cvičení 03 Jaro 2018 17 / 22
Instance třídy Monad I.
instance Monad Maybe where
      return :: a -> Maybe a
      return = Just
      (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
      Nothing >>= f = Nothing
      Just x >>= f   = f x
      fail :: String -> Maybe a
      fail _ = Nothing
IB016: Cvičení 03 Jaro 2018 17 / 22
Instance třídy Monad II.
instance Monad [] where
      return :: a -> [a]
      return x = [x]
      (>>=) :: [a] -> (a -> [b]) -> [b]
      xs >>= f = concat (map f xs)
      fail :: String -> [a]
      fail _ = []
IB016: Cvičení 03 Jaro 2018 18 / 22
Pravidla pro třídu Monad
Levá identita
return x >>= f ≡ f x
Pravá identita
m >>= return ≡ m
Asociativita
(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)
IB016: Cvičení 03 Jaro 2018 19 / 22
do-notace
do-notace je jenom syntaktický cukr pro >>=
tj. se všemi monády můžeme pracovat přes do
IB016: Cvičení 03 Jaro 2018 20 / 22
do-notace
do-notace je jenom syntaktický cukr pro >>=
tj. se všemi monády můžeme pracovat přes do
maybePlus
   :: Maybe Float -> Maybe Float -> Maybe Float
maybePlus x y = do
   justX <- x
   justY <- y
   return $ justX + justY
IB016: Cvičení 03 Jaro 2018 20 / 22
Úkol: instance Functor a Applicative
Uvažme následující datový typ:
newtype Triple a = Triple { unTriple :: (a, a, a) }
                           deriving (Eq, Ord, Show, Read)
1 Napište instanci pro třídu Functor.
(Jak bude fungovat funkce map?)
2 Zamyslete se nad platností pravidel (!) třídy Functor.
3 Napište instanci pro třídu Applicative.
(Jak aplikovat funkce?)
4 Zamyslete se nad platností pravidel (!) třídy Applicative.
IB016: Cvičení 03 Jaro 2018 21 / 22
Úkol: do-notace
1 Napište „nedeterministické“ „skoro-aritmetické“ funkce:
2 ~+~ 5 ∗ [6, 7, 8]
3 ~*~ 5 ∗ [10, 15, 20, 12, 15, 18]
2 Napište pomocí do-notace nedeterministický výpočet:
almostPlusTimes x y z ≡ (x ~+~ y) ~*~ z
3 Implementujte funkci maxMinEval :: [a] -> (a, a), která
z možných výsledků vybere nejmenší a největší.
IB016: Cvičení 03 Jaro 2018 22 / 22