Lecteur, écrivain monades

17

Soit C un CCC . Soit (×) être un bifoncteur produit sur C . Comme Cat est CCC, nous pouvons curry (×) :

curry(×):C(CC)

curry(×)A=λB.A×B

Catégorie de foncteurs CC a une structure monoïdale habituelle. A monoid en CC est une monade en C . Nous considérons que les produits finis que la structure monoïdale sur C .

curry(×)1id

A B.curry(×)(A×B)(curry(×)A)(curry(×)B)

Par conséquent préserve la structure monoïdale, donc il transporte un monoïde vers une monade et un comonoïde vers une comonade. À savoir, il transporte un monoïde arbitraire w vers ( W r i t e r w ) monade (regardez la définition - w doit être un monoïde). De même, il transporte la comonoïde diagonale vers la comonade Coreader.(curry(×))w(Writer w)w

Maintenant, pour être concret, je déplie la construction de Writer.

Commencer. En fait , ils ont simplement des noms distincts dans Haskell. Nous avons une monoid Haskell w , m a p p e n d , m e m p t y :Writer=Coreader=curry(×) w,mappend,mempty

mappend:w×ww

mempty:1w

Writer est un foncteur, il doit donc cartographier également les morphismes, tels que et m e m p t y . J'écris ceci comme ci-dessous, bien qu'il ne soit pas valide dans Haskell:mappendmempty

Writer mappend:Writer(w×w)Writer w

est une transformation naturelle, un morphisme en C C . Par propriétés de c uWriter mappendCC c'est une fonction, qui prend a O b ( C ) et donne un morphisme en C :curry(×)aOb(C)C

Writer mappend a=mappend×(id(a)):Writer(w×w)aWriter w a

De façon informelle, des composants de leur montant de type p et pompesWriter mappend aw intacte. C'est exactement la définition de Writer dans Haskell. Un obstacle est que pour la monadeW r i t e r w , μ , r | nous avons besoinaWriter w,μ,η

μ:Writer wWriter wWriter w

c'est-à-dire incompatibilité des types. Mais ces foncteurs sont isomorphes: par l'associateur habituel pour les produits finis qui est un isomorphisme naturel λ a . w × ( w × a ) = W r i t e r w W r i t e r wWriter(w×w)=λa.(w×w)×aλa.w×(w×a)=Writer wWriter w . On définit alors via W r i t e r m aμ . J'omets une construction de η via m e m p t y .Writer mappendηmempty

Écrivain, être un foncteur, conserve des diagrammes commutatives, à savoir les conserves monoid égalités, nous avons donc des égalités prouvé accordées pour = monoid dans ( C C ) = une monade en C . Fin.Writer w,μ,η(CC)C

Et Reader et Cowriter? Le lecteur est adjoint à Coreader, comme expliqué dans la définition de Coreader, voir le lien ci-dessus. De même, Cowriter est adjoint à Writer. Je n'ai pas trouvé de définition de Cowriter, je l'ai donc inventée par analogie dans le tableau:

texte alternatif

{- base, Hackage.category-extras -}
import Control.Comonad
import Data.Monoid
data Cowriter w a = Cowriter (w -> a)
instance Functor (Cowriter w) where
    fmap f (Cowriter g) = Cowriter (f . g)
instance Monoid w => Copointed (Cowriter w) where
    extract (Cowriter g) = g mempty
instance Monoid w => Comonad (Cowriter w) where
    duplicate (Cowriter g) = Cowriter
        (\w' -> Cowriter (\w -> g (w `mappend` w')))

Voici les définitions simplifiées de ces (co) monades. fr_ob F désigne une cartographie d'un foncteur F sur des objets, fr_mor F désigne une cartographie d'un foncteur F sur des morphismes. Il est un objet de monoid en C .w,+^,0^C

  • Écrivain
    • fr_ob(Writer w)a=a×w
    • fr_mor(Writer w)f=λa0,w2.a0,f w2
    • ηa=λa0.a0,0^
    • μa=λa0,w1,w0.a0,w0+^w1
  • Lecteur
    • fr_ob(Reader r)a=ra
    • fr_mor(Reader r)f=λg r0.f(g r0)
    • ηa=λa0 r0.a0
    • μa=λf r0.f r0 r0
  • Coreader
    • fr_ob(Coreader r)a=r×a
    • fr_mor(Coreader r)f=λr0,a0.f r0,a0
    • ηa=λr0,a0.a0
    • μa=λr0,a0.r0,r0,a0
  • Cowriter
    • fr_ob(Cowriter w)a=wa
    • fr_mor(Cowriter w)f=λg r0.f(g r0)
    • ηa=λf.f 0^
    • μa=λf w1w0.f(w0+^w1)

La question est que l'adjonction en concerne les foncteurs, pas les monades. Je ne vois pas comment l'adjonction implique "Coreader est une comonade" "Reader est une monade" et "Writer est une monade" "Cowriter est une comonade".C

Remarque. J'ai du mal à fournir plus de contexte. Cela demande du travail. Surtout, si vous avez besoin d'une pureté catégorique et que ces (co) monades ont été introduites pour les programmeurs. Continuez à harceler! ;)

beroal
la source
Offre: vous pouvez prendre une capture d'écran du tableau et mettre l'image ici.
MS Dousti
Vous devez copier la question ici.
Dave Clarke du
2
people downvoting should post a comment explaining why.
Suresh Venkat
1
@Ohad. I confess that I introduced that change to try to provide the question with more context (as was originally found in the blog post originally referenced). I think beroal should spend more effort making his question self contained, for example, by defining what Reader and Writer and Coreader and Cowriter are in categorical terms or in Haskell or both, rather than assuming that we all know what is being referred to.
Dave Clarke
2
@beroal: What I meant was that, as I don't use Haskell on a day to day basis, parsing the Haskell code and making the transition into CT is non-trivial for me, and perhaps others. By rephrasing the question in purely categorical terms, you are more likely to receive an answer quicker...
Ohad Kammar

Réponses:

13

Yes, if a monad M:CC has a right adjoint N, then N automatically inherits a comonad structure.

CDFun(C,D) for the categeory of functors from C to D; Its objects are functors and its morphisms natural transformations. Write FunL(C,D) for the full subcategory of Fun(C,D) on the functors which have right adjoints (in other words, we consider functors CD with right adjoints and arbitrary natural transformations between them). Write FR:DC for the right adjoint of a functor F:CD. Then R:FunL(C,D)Fun(D,C) is a contravariant functor: if α:FG is a natural transformation then there is an induced natural transformation αR:GRFR.

If C=D, then Fun(C,C) has a monoidal structure given by composition and so does FunL(C,D), because the composition of left adjoints is a left adjoint. Specifically, (FG)R=GRFR, so R is an antimonoidal contravariant functor. If you apply R to the structural natural transformations which equip a functor M with the structure of a monad, what you get out is a comonad.

Reid Barton
la source
1
And one should mention that some of these functors, for example R is not really a functor but rather something like a pseudo-functor because it typically satisfies functoriality only up to canonical isomorphisms. Nevertheless, the main point is valid.
Andrej Bauer
7

By the way, this:

Let (×) be a product bifunctor in C. As C is CCC, we can curry (×)

is slightly incorrect. For one, the usual terminology would be (if I'm not mistaken) that × is a bifunctor over or on C. "In" typically means constructions using the arrows and objects of a category, whereas functors "on" categories refer to constructions relating multiple categories. And the product bifunctor isn't a construction within a Cartesian category.

And this relates to the larger inaccuracy: the ability to curry the product bifunctor has nothing to do with C being Cartesian closed. Rather, it is possible because Cat, the category of categories (insert caveats) is Cartesian closed. So the currying in question is given by:

HomCat(C×D,E)HomCat(C,ED)

where C×D is a product of categories, and ED is the category of functors F:DE. This works regardless of whether C, D and E are Cartesian closed, though. When we let C=D=E, we get:

×:C×CC
curry×:CCC

But this is merely a special case of:

F:C×DE
curryF:CED
Dan Doel
la source
2 Dan Doel: Yes, yes, yes, thanks. I did the mistake while translating from the original post beroal.livejournal.com/23223.html .
beroal
4

Consider the adjunction F,G,ϵ,η. For every such adjunction we have a monad GF,η,GϵF and also a comonad FG,ϵ,FηG. Notably, F and G need not be endofunctors, and in general they aren't (e.g., the list monad is an adjuction between the free and forgetful functors between Set and Mon).

So, what you want to do is take Reader (or Writer) and decompose it into the adjoint functors which give rise to the monad and the corresponding comonad. Which is to say that the connection between Reader and Coreader (or Writer and Cowriter) isn't the one you're looking for.

And it's probably better to think of currying as :hom(×A,=)hom(,=A), i.e. X,Y. {f:X×AY}{f:XYA}. Or if it helps, :hom(×A,=×1)hom(1,=A)

wren romano
la source
2 wren ng thornton: I am not aware of any defining adjunction for Reader and Writer similar to adjunctions between Set and a category of algebraic structures. Or do you mean that every monad is defined by an adjunction as in "MacLane. Categories for the Working Mathematician. VI. Monads and Algebras. 2. Algebras for a Monad. Theorem 1 (Every monad is defined by its T-algebras)."? Can you be more specific? Actually my question is the conclusion of an attempt to define those (co)monads in elegant words as the list monad is.
beroal
@beroal: I'm pretty sure Reader and Writer aren't adjoint, or at least I've yet to find a way to get the categories to work out for it. No, my point was that monads and comonads arise in "the same way", namely via an adjunction, as described above. I don't have a copy of MacLane, but yes T-algebras are the standard name for the trick above (but then again, all sorts of unrelated things are called "X-algebras", "Y-algebras",...).
wren romano
Which description of the list monad are you trying to match the eloquence of? Given the free monoid functor F:SetMon, the forgetful functor U:MonSet, the unit transformation η:idSetUF, and the counit transformation ϵ:FUidMon you have an adjunction F,U,η,ϵ. Which means you have a monad UF,η,UϵF, namely the list monad in Set. And you get the list comonad in Mon: FU,ϵ,FηU. Eloquent?
wren romano
Functors (Reader a) and (Writer a) are adjoint, and that adjunction gives rise to the (State a) monad.
beroal
"No, my point was that monads and comonads arise in "the same way", namely via an adjunction, as described above". If you get the monad and the comonad from the adjunction between categories Set and Mon, you get the monad on Set and the comonad on Mon — different categories. But Reader and Writer are on the same CCC category.
beroal