The explanation given below might be a bit heavy for someone who didn't know much about category theory. For those individuals I'd recommend Phil Wadler's papers: http://homepages.inf.ed.ac.uk/wadler/topics/monads.html I especially recommend "Monads for Functional Programming", "The Essence of Functional Programming" and "Comprehending Monads". Basically, though, the Haskell implementation _is_ the category theoretic definition of monad, with bind/return used instead of (f)map/join/return as described below. Mike

Date: Thu, 18 Aug 2005 20:39:37 -0400 From: Cale Gibbard Cc: haskell-cafe@haskell.org

On 14/08/05, Carl Marks wrote:

...

Is there any text/article which makes precise/rigorous/explicit the connection between the category theoretic definition of monad with the haskell implementation?

Well, a monad over a category C is an endofunctor T on C, together with a pair of natural transformations eta: 1 -> T, and mu: T^2 -> T such that 1) mu . (mu . T) = mu . (T . mu) 2) mu . (T . eta) = mu . (eta . T) = id_C

In Haskell, a monad is an endofunctor on the category of all Haskell types and Haskell functions between them. Application of the endofunctor to an object is given by applying a type constructor (the one which is made an instance of the Monad class). Application of the endofunctor to a function is carried out by fmap or liftM. The natural transformation eta is called return, and mu is called join (found in the Monad library).

Haskell uses a somewhat different (but equivalent) basis for a monad, in that it is not map, return, and join which need defining to make a type an instance of the Monad class, but return and (>>=), called "bind" or "extend".

One can define bind in terms of fmap, and join as x >>= f = join (fmap f x)

and one can get back join and fmap from return and bind: join x = x >>= id fmap f x = x >>= (return . f)

hope this helps, - Cale _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 22/08/05, Chung-chieh Shan wrote:

Michael Vanier wrote in article <20050819054742.5C785103BE4@orchestra.cs.caltech.edu> in gmane.comp.lang.haskell.cafe:

...

Basically, though, the Haskell implementation _is_ the category theoretic definition of monad, with bind/return used instead of (f)map/join/return as described below.

Doesn't the Haskell implementation really correspond to the notion of a strong monad in category theory, once we take into account the fact that free variables can occur anywhere in the arguments to bind and return?

Well, I had a look at the definition of strong monad. It seems that for the obvious symmetric monoidal structure given by (,) any Haskell monad admits the following strength, making it a strong monad: strength :: (Monad m) => (a, m b) -> m (a,b) strength (x, xs) = xs >>= (\a -> return (x,a)) It's less clear to me that any symmetric monoidal structure on the category of Haskell types admits a strength for any Haskell monad. It's also not so clear that it will always be unique. (This would be fairly interesting) Even if this is so, since Haskell monads don't come with a strength pre-defined, I'd hesitate to call them "strong" in the same way that I'd hesitate to call a metrisable topological space a metric space: the information isn't attached to begin with. - Cale