Seminář 3: Produkty, koprodukty a algebraické datové typy (ADT) Produkty
x
a <•
P2
Pl
• Objekt c e C s projekcemi p\ : c —¥ a a p2 : c —► b je produkt objektů a a 6 <ŕ=> Vx e C.V/ : x ^ a,g : x ^ b.3\q : x -ž- c. (f = Pi o q A g = P2 ° q)
• g faktorizuje f & g <^^> f = Pi ° q A g = P2 o q
• g je univerzálni mapováni
Příklady
• V Set kartézský součin
• V Poset (částečně uspořádaná množina) ínfimum Haskell
data (,) a b = (,) a b fst (x, _) = x — p_l snd (_, y) = y — p_2
q ::  (j -> a) -> (j -> b) -> j -> (,) a b q f g   x = (f x, g x)
Koprodukty (sumy)
• Objekt c € C se zahrnutími (inkluzemi) i\ : c <— a a i2 : c -(— & je koprodukt objektů a a & <^> Va; e C.V/ : x 4- a, g : x 4- b.3\q : x 4- c. (/ = q o i1 A g = q o i2)
Příklady
• V Set disjunktní sjednoceni
• V Poset (částečně uspořádaná množina) supremum Haskell
data Either a b = Left a I Right b
— i_l = Left
— i_2 = Right
q ::  (a -> j) -> (b -> j) -> Either a b -> j q f      (Left x)    = f x q _ g (Right x) = g x
x
1
Bifunktory
Produkt kategorií C x V
Skládá se z
• 0Cxv = {(c,d)\ceOc,deOv}
• ACxv = {(f,g)\f ■■       ce Ac,g        de Av}
Musí platit
• identita pro (a, 6) je (ida,idb)
• (f,h) o(g,k) = (f og,hok)
Bifunktor F = funktor z produktu kategorií F : C x P —)■ £
V každé kategorii C, kde pro každé dva objekty a a b můžemem najít jejich produkt, existuje bifunktor x (zapisován infixově).
x : C x C C : (a, b) h4 a x b
: (f : a -> a', g : b -> b') >-> (f x g : a x b -> a' x b')
a 4-
a! <-
a x b
ifx-g a' x 6' -
-4 b'
P2
Bifunktory v Haskellu
class Bifunctor f where
bimap ::  (a -> b) -> (c -> d) -> f a c -> f b d
bimap g h = first g . second h
first ::  (a -> b) -> f a c -> f b c
first g = bimap g id
second ::  (c -> d) -> f a c -> f a d
second h = bimap id h
{-# MINIMAL bimap I first, second #-}
instance Bifunctor (,) where bimap g h (x, y) = (g x, h y)
instance Bifunctor Either where bimap g _ (Left x)    = Left    (g x) bimap _ h (Right y) = Right (h y)
ADT a funktory
• Pro každý ADT umí GHC instancovat funktor s pomocí rozšíření (od GHC 9.2.1 bez rozšíření) {-# LANGUAGE DerivingFunctor #-}
data Example a = Ex a Int (Example a)  (Example Int) deriving (Functor)
2