On Tue, Jan 18, 2011 at 09:16:06AM +0530, C K Kashyap wrote:

Hi, I was going through http://en.wikipedia.org/wiki/Monad_(category_theory) - under Formal Definition I notice that monad is a Functor T:C -> C

My question is - when we think of Maybe as a functor T:C -> C .... should we think that C here refers to Hakell types? As in, (Int and Maybe Int are objects in C) and (Int -> Int and Maybe Int -> Maybe Int are arrows in C) and T is an arrow between them. Is that right?

Yes, exactly.

I am not able to fully understand how those diagrams translate to haskell - I can guess that T^2 -> T referes to things like concat operation but not able to relate it to bind.

The T^2 -> T operation in Haskell is called join :: Monad m => m (m a) -> m a which, as you correctly point out, is concat for the list monad. This presentation in terms of fmap, return, and join is another common way of presenting monads. To relate it with bind we have m >>= f = join (fmap f m) join m = m >>= id There are is also a form of the monad laws in terms of fmap, return, join. For more I recommend checking out http://en.wikibooks.org/wiki/Haskell/Category_theory -Brent

On 1/17/11 10:46 PM, C K Kashyap wrote:

Hi, I was going through http://en.wikipedia.org/wiki/Monad_(category_theory) - under Formal Definition I notice that monad is a Functor T:C -> C

My question is - when we think of Maybe as a functor T:C -> C .... should we think that C here refers to Hakell types?

Not quite. A functor is a mapping between categories. Well, then what's a mapping between categories? It's a pair of maps, one mapping objects to objects and the other mapping arrows to arrows, such that they preserve the category structure (i.e., obey the functor laws). For categories like the ones for lambda calculi, the objects are types and the arrows are functions. Thus, the C there is referring to some category (namely a category modeling Haskell's type system). If you wish, you can think of categories as being like Either Object Arrow, for a particular class of objects and a particular class of arrows. So we'd have, T : Either Ob Hom -> Either Ob Hom T (Left ob) = ... T (Right hom) = ... Though nobody does that and we prefer our notation to slide over the fact that functors and categories have two parts, and so we actually write: T : C -> C T ob = ... T hom = ... So we might have that T Int = Bool, or T Int = [Int], or whatever. But we don't usually give types for the components of a functor, since we care more about the functor as a whole (e.g., we don't give types to individual lines of a function definition either, we only give a type for the whole function).

As in, (Int and Maybe Int are objects in C) and (Int -> Int and Maybe Int -> Maybe Int are arrows in C) and T is an arrow between them. Is that right? For some reason, I was imagining them as two different categories C and D.

Generally speaking functors do go between different categories, but there's no reason they can't be on the same category (e.g., the identity functor :) Conventional monads are always endofunctors though, since otherwise we couldn't talk about the natural transformations like return and join (we don't have arrows between objects in different categories). There are some generalizations of monads that relax this however. -- Live well, ~wren