Monads as additions

Question

I read about monads in category theory. In one definition of monads, a pair of conjugate functors is used. Using these functors, the monad is defined in a circular motion. Adjunctions seem to be very important in category theory, but I have not seen any explanation of the Haskell monks in terms of conjugate functors. Has anyone given him a thought?

Answer 1

Edit : just for fun, I will do it right. Original answer saved below.

The current join code for additional categories is now in the add-on package: http://hackage.haskell.org/package/adjunctions

I will simply work through the state monad clearly and simply. This code uses Data.Functor.Compose from the package of transformers, but otherwise is autonomous.

The adjacency f (D → C) and g (C → D) written by f - | g, can be characterized in several ways. We will use the description concit / unit (epsilon / eta), which gives two natural transformations (morphisms between functors).

 class (Functor f, Functor g) => Adjoint fg where counit :: f (ga) -> a unit :: a -> g (fa) 

Note that “a” in consensus is indeed an identity functor in C, and “a” in unity is indeed an identity functor in D.

We can also reconstruct the definition of joining a homosexual from the definition of contingent / unit.

 phiLeft :: Adjoint fg => (fa -> b) -> (a -> gb) phiLeft f = fmap f . unit phiRight :: Adjoint fg => (a -> gb) -> (fa -> b) phiRight f = counit . fmap f 

In any case, now we can define Monad from our unit / concit application like this:

 instance Adjoint fg => Monad (Compose gf) where return x = Compose $ unit x x >>= f = Compose . fmap counit . getCompose $ fmap (getCompose . f) x 

Now we can implement the classic join between (a,) and (a →):

 instance Adjoint ((,) a) ((->) a) where -- counit :: (a,a -> b) -> b counit (x, f) = fx -- unit :: b -> (a -> (a,b)) unit x = \y -> (y, x) 

And now a type synonym

 type State s = Compose ((->) s) ((,) s) 

And if we upload it to ghci, we can confirm that the state is our classic state monad. Please note that we can take the opposite composition and get Costant Comonad (aka comonad store).

There are several other additions we can make to monads in this way (for example, a pair (Bool,)), but these are kind of weird monads. Unfortunately, we cannot make add-ons that encourage Reader and Writer directly in Haskell in a pleasant way. We can do Cont, but, as copumpkin describes, this requires joining from the opposite category, so it actually uses a different “form” of the “Adjoint” class, which changes some arrows. This form is also implemented in another module in the add-on package.

this material is considered differently in an article by Derek Elkins in the book "Monad Reader 13" - "Calculated Monads with Category Theory: http://www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf

In addition, a recently updated article by Kan Extensions for Program Optimization Hinze looks at building a list monad from a binding between Mon and Set : http://www.cs.ox.ac.uk/ralf.hinze/Kan.pdf

---

Old answer:

Two links.

1) Category-additions provide, as always, an idea of ​​additions and how monads arise from them. As usual, it’s good to think, but quite easy to document: http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Functor-Adjunction.html

2) -Cafe also delivers with a promising but concise discussion of the role of affiliations. Some of them may help in interpreting add-on categories: http://www.haskell.org/pipermail/haskell-cafe/2007-December/036328.html

Answer 2

Derek Elkins recently showed me how to eat supper as Cont Monad arises from composing a contravariant functor (_ -> k) with itself, since it turns out to be self-adjoint. The way you get (a -> k) -> k . However, its contingent eliminates the double negation that cannot be written in Haskell.

For some Agda code that illustrates and proves this, see http://hpaste.org/68257 .

Answer 3

This is an old thread, but I found an interesting question, so I did some calculations myself. Hopefully Bartosh is still there and can read this.

Indeed, the Eilenberg-Moore construction gives a very clear picture in this case. (I will use the CWM notation with Haskell syntax)

Let T be the monad of the list < T,eta,mu > ( eta = return and mu = concat ) and consider the T-algebra h:T a -> a .

(Note that T a = [a] is a free monoid <[a],[],(++)> , that is, identity [] and multiplication (++) .)

By definition, h must satisfy hT h == h.mu a and h.eta a== id .

Now, some simple diagrammatic race proves that h actually induces a monoid structure on a (defined by x*y = h[x,y] ), and that h becomes a monoid homomorphism for this structure.

Conversely, any monoidal structure < a,a0,* > defined in Haskell is naturally defined as a T-algebra.

Thus ( h = foldr ( * ) a0 , a function that “replaces” (:) with (*) and maps [] to a0 , identity).

Thus, in this case, the category of T-algebras is only the category of monoid structures defined in Haskell, HaskMon.

(Please verify that morphisms in T-algebras are actually monoidal homomorphisms.)

It also characterizes lists as universal objects in HaskMon, as well as free products in Grp, polynomial rings in CRng, etc.

Adjacency corresponding to the specified design, < F,G,eta,epsilon >

Where

• F:Hask -> HaskMon , which takes type a into the "free monoid generated by a ", that is, [a] ,
• G:HaskMon -> Hask , forgetful functor (forget multiplication),
• eta:1 -> GF , the natural transformation defined by \x::a -> [x] ,
• epsilon: FG -> 1 , the natural transformation defined by the folding function above ("canonical surjection" from a free monoid to its partial monoid)

Further, there is another “Claysley category” and its corresponding adherence. You can verify that this is only a category of Haskell types with morphisms a -> T b , where its compositions are given by the so-called "Claysley composition" (>=>) . A typical Haskell programmer will find this category more familiar.

Finally, as shown in CWM, the category of T-algebras (respectively, the Claysley category) becomes a terminal (respectively initial) object in the category of sentences that define the list of monads T in the appropriate sense.

I propose to perform similar calculations for the binary tree functor T a = L a | B (T a) (T a) T a = L a | B (T a) (T a) to test your understanding.

Answer 4

I found the standard construction of helper functors for any Eilenberg-Moore monad, but I'm not sure if it adds any information about the problem. The second category in the construction is the category of T-algebras. Algebra T adds “product” to the initial category.

So how will this work for a list monad? A functor in a list monad consists of a type constructor, for example, Int->[Int] and a function mapping (for example, the standard application of a map to lists). Algebra adds a mapping from lists to elements. One example would be the addition (or multiplication) of all elements of a list of integers. The functor F takes any type, for example Int, and maps it to the algebra defined in the Int lists, where the product is defined by a monadic connection (or vice versa, a union is defined as a product). The forgetting functor G takes algebra and forgets the product. A pair of F , G , adjoint functors is then used to construct the monad in the usual way.

I must say that I am not wiser.

Answer 5

If you are interested, here are some thoughts about the layman about the role of monads and adjunctions in programming languages:

First of all, for a given monad T there is a unique adherence to the Claysley category T In Haskell, the use of monads is mainly limited to operations in this category (which is essentially a category of free algebras, not relevant). In fact, all you can do with Monk Haskell is to compile some Kleisley morphisms, type a->T b using the expressions do, (>>=) , etc., to create a new morphism. In this context, the role of monads is limited only by the economy of notation. One of them uses morphism associativity to be able to write (say) [0,1,2] instead of (Cons 0 (Cons 1 (Cons 2 Nil))) , that is, you can write a sequence as a sequence, and not as a tree.

Even the use of IO monads is not essential, since the current Haskell-type system is powerful enough to implement data encapsulation (existential types).

This is my answer to your initial question, but I'm curious what Haskell experts have to say about it.

On the other hand, as we have already noted, there is also a 1-1 correspondence between monads and (T-) -algebras. Alignment, in MacLane terms, is "a way to express equivalence of categories." In a typical installation of additions <F,G>:X->A , where F “generator of free algebras” and G is the “forgetful functor”, the corresponding monad will (using T-algebras) describe how (and when) the algebraic structure is constructed A on objects X

In the case of Hask and the monad of the list T, the structure that T introduces is that of a monoid, and this can help us establish the properties (including the correctness) of the code through the algebraic methods that the monoid theory provides. For example, the function foldr (*) e::[a]->a can easily be considered as an associative operation if <a,(*),e> is a monoid, a fact that can be used by the compiler to optimize the calculation (for example, parallelism). Another application is to identify and classify “recursion patterns” in functional programming using categorical methods in the hope of (partially) getting rid of “goto functional programming”, Y (arbitrary recursion combinator).

Apparently, such applications are one of the main motives of the creators of Category Theory (MacLane, Eilenberg, etc.), namely, to establish the natural equivalence of categories and transfer the known method to one category to another (for example, homological methods to topological spaces, algebraic programming methods, etc.). Here, conjugations and monads are indispensable tools for using this combination of categories. (By the way, the concept of monads (and its duals, comonads) is so general that you can even go so far as to define Haskell's “cohomology”. But I haven't thought about it yet.)

As for the undefined functions that you mentioned, I have much less to say ... But note that; if joining <F,G>:Hask->A for some category A defines a list of monad T , there must be a unique "comparison functor" K:A->MonHask (the category of monoids defined in Haskell), see CWM. In fact, this means that your category of interests should be a category of monoids in some limited form (for example, for its absence some partial, but not free algebras may be absent).

Finally, some notes:

The binary tree functor mentioned in my last publication easily generalizes to an arbitrary data type T a1 .. an = T1 T11 .. T1m | ... T a1 .. an = T1 T11 .. T1m | ... Namely, any data type in Haskell naturally defines a monad (along with the corresponding category of algebras and the Claysley category), which is the result of the fact that any data constructor in Haskell is complete. This is another reason why I find the Haskell Monad class not much more than syntactic sugar (which, of course, is pretty important in practice).