Koprvoky 22. dubna 2022
Komonáda v kategorii C je monáda v C°P. Explicitně: Srovnání s monádami
Definice 1. Komonáda v kategorii C je trojice W = (T,£,S), kde
• T: C —>■ C, (endofunktor)
• e:T=^Id, (kojednotka, ko ret urn, extract) rj-.ld=>T
• S:T^>T2. (konásobení, ko join, duplicate) fi:T2^T
takové, že následující diagramy komutují.
j3    ST    j2 j •<== T2 ===>- T
TS\\     \\s      X ll'
T2      — T T
Haskell
class Functor w => Comonad w where
extract
extend
duplicate
w a -(w a w a -
> b) —>■ w a w (w a)
w b
Jako u monád, z extend a duplicate stačí jedno: extend f   = fmap f ■ duplicate duplicate = extend id
Skládání ko-Kleisliho šipek:
(w b
(w a
w a
f =<= g = f ■ extend g Pravidla pro komonady v Haskellu:
extend extract    = id extract ■ extend f    = f extend f ■ extend g    =    extend (f ■ extend g)
return :: a —> m a
bind :: (a —> m b) —> m a —> m b
join :: m (m a) —> m a
bind = join ■ fmap f join = bind id
(<=<): :(b -» mc)-t(a -» mb)-» a -» mc
f <=< g = bind f ■ g
Z adjunkti
Pokud F:C^PaG:ľ^C jsou adjungované funktory (F H G):
• n: Idc     GF, (jednotka)
• e:FG=^Idx>, (kojednotka)
Tvrzení 1. Každá adjunkce (F, G, n, e) dává zrod komonádé FG v T>. GF je monáda v C
p: GFGF GF
S: FG =>■ FGFG      S = FnG p = GcF
Tvrzení 2. Každá komonáda se rodí z adjunkce.
(Podobně jako u monád - přes ko-Kleisliho kategorii, v níž identita odpovídá extract a skládání šípek realísuje operátor =<=.)
KOPRVOKY 2
Příklady
Dvojice   Funktor ( r, —). Šipky mají podobu Kočtenář (též Env), chová se jako čtenář.
r, a)
b.
Zaměřené grafy   extract vrací vrchol; duplicate vyrábí graf grafů se stejným tvarem jako původní graf, v každém vrcholu je původní graf s jiným zaměřeným vrcholem.
Monáda čtenáře: funktor ( r —>• —) šipky a —> r —>• b
Kořenové stromy   extract vrací kořen; duplicate vyrábí strom stromů se stejným tvarem jako původní strom, v každém uzlu je příslušný podstrom původního stromu.
Strom je pěkná monáda, má-li hodnoty jen v listech.
Nekonečné seznamy   data Stream a = Cons a (Stream a).
Výsledek duplicate xs má na z-té posici nekonečný seznam odpovídající drop i xs.
Zippery Datová struktura representující stav procházení jiné datové struktury: zaměřený prvek + zatím neprošlá část + již prošlá část. Např. data ListZipper a = Zip [a] a [a].
Funkce   Funktor (m —>■ —). Šipky mají podobu (m —>■ a) —>■ b. m je monoid. Kopísař (též Traced), chová se jinak než písař.
Zaměřený slovník   data Store s a = Store (s —>■ a) s, kostav.
Např. celulární automat ä la Game of Life: Typem indexu (s) jsou souřadnice. Výpočet typu Store Coords Bool —»■ Bool implementuje pravidlo pro jednu buňku, extend ho aplikuje po celé ploše.
Monáda písaře: funktor (l, —), l je monoid šipky a —> (l, b)
Adjunkce (s, —) H (s —>• —) plodí monádu State s~s —>• (s,—) komonádu Store s ~ (s, s —> —)
Mimo Hask
Definice 2 (funkce uzávěru). Funkce f: S —>■ S na částečně uspořádané množině (S, <) je funkcí uzávěru, pokud pro všechna x,y 6 S splňuje:
x < f (x) f(f(x))=f(x)
x<y^f(x) <f(x)
Tvrzení 3. Funkce uzávěru jsou právě monády v kategorií odpovídající příslušnému posetu. Duální pojem (funkce vnitřku) jsou tamní komonády.
Modálni logika   Modálni operátory (možnost a nutnost, „někdy platí"/„vždy platí")
A -> oA UA -> A
ooA^oA \JA —>■ ĽDA
KOPRVOKY 3
Úlohy na procvičení
1. Ukažte, že pravidla pro haskellové komonády odpovídají pravidlům pro skládání šipek v ko-Kleisliho kategoriích.
2. Navrhněte dvě různé platné instance Comonad pro stromy s libovolnou aritou: data Tree a = Node a [Tree a].
3. Uvažme tuto implementaci zaveditelnou pro každý funktor: duplicate wx = fmap (Ax —»■ wx) wx.
Rozhodněte, zda může vést při vhodné implementaci extract taková implementace k platné komonádě
(a) u funktoru St ream,
(b) u některého jiného funktoru,
(c) obecně u všech funktoru.