Seminář 7: Monády
Monáda
• Monáda M = (T, η, µ) – endofunktor T a dvě přirozené transformace η a µ
T : C → C
η : Id =⇒ T (jednotka)
µ : T2
=⇒ T (násobení)
• Tyto dva diagramy komutují (čtverec asociativity a dva jednotkové trojúhelníky)
T3
T2
T2 T
T T2
T
T
µ · T
µ
µ
T · µ
id id
η · T T · η
µ
Kleisliho kategorie
Monáda nad kategorií tvoří novou kategorii nazvanou Kleisliho kategorie. C je kategorie
a M = (T, η, µ) je monáda nad ní. Kleisliho kategorie CT je potom následující:
• Objekty z CT přímo odpovídají objektům z C
• Morfismy z CT jsou ve formě f : a → Tb, tedy: HomCT
(a, b) HomC(a, Tb)
• Kompozice morfismů fT : a → Tb, gT : b → Tc definována: gT ◦T fT ≡ µc ◦ (Tg) ◦ f
• Identity idaT jsou rovny ηa
Monády a adjunkce
Mějme adjunkci L R pro kategorie C, D.
η : ID → R ◦ L
: L ◦ R → IC
Tedy R ◦ L je endofunktor. Jednotce odpovídá η, násobení se definuje takto:
µ = R ◦ ◦ L
Platí: adjunkce R L =⇒ uvnitř je monáda (R ◦ L, η, µ)
Opačně pouze: monáda nad C =⇒ ∃ adjunkce F G, kde F : C → CT a G : CT → C
Haskell
Pro názornost si zavedeme následující definici monády v Haskellu:
class Functor m => Monad m where
join :: m (m a) -> m a
return :: a -> m a
join ∼= µ
return ∼= η
Skutečná definice je ekvivalentní. Funkci bind je možné napsat pomocí join a fmap.
class Applicative m => Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
a >>= f = join (fmap f a)
Pro připomenutí:
fmap :: Functor f => (a -> b) -> f a -> f b
Kleisliho rybí operátory
Operátor pro zřetězení monádových funkcí (obdoba (.)):
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
g <=< f = join . fmap g . f
Verze plující na druhou stranu:
(>=>) = flip (<=<)
Příklady
instance Monad Maybe where
join (Just (Just x)) = Just x
join _ = Nothing
return a = Just a
instance Monad [] where
join = concat
return x = [x]
instance Writer Str where
join (Writer ((Writer (a, s')), s)) = Writer (a, s ++ s')