Search code examples
haskellmonadscategory-theory

Are all Monad instances in Haskell just different ways for mapping from Hask to Hask?


I'm reading Haskell/Category theory and here is the definition of monad from that article:

A monad is a special type of functor, from a category to that same category, that supports some additional structure. So, down to definitions. A monad is a functor M:C->C, along with two morphisms for every object X in C:

unit: X -> M(X)

join: M(M(X)) -> M(X)

As I understand it, in Haskell return is equivalent to unit. But with return I can write:

x :: [Int]  -- x is a member of Lst category
x = return 5

and this is valid code in Haskell. Now, as you can see, 5 here is not a member of Lst, but return works for it.

So, I guess that Lst is not С from M:C->C. But who then?

Maybe the right answer is Hask, but I'm not sure that "functor from a category to its subcategory" is the same as "functor from a category to the same category".


Solution

  • This is a common point of confusion and you've asked the question clearly enough for it to be answerable.

    I'm not sure that "functor from category to it's subcategory" is the same as "functor from category to the same category".

    It's not the same. A functor consists of four pieces of data: a source category C, a target category D, a mapping of objects of C to objects of D, and a mapping of morphisms of C to morphisms of D, satisfying some conditions. If you change D, then you change the functor.

    However when we define a functor, we often have some choice in the category D. I infer from your question that Lst is a subcategory of Hask whose objects are types of the form [a], though I'm not sure what the morphisms of Lst are supposed to be. We could define a functor [] of either of these two shapes:

    1. [] : Hask -> Lst (i.e., the target category of [] is Lst)

    2. [] : Hask -> Hask (i.e., the target category of [] is Hask)

    These are technically different functors, and we have to make a choice. In this context, the correct choice is choice 2. We need the source and target categories to be the same because we need to apply [] to the output of [], in join. So C = Hask and M = [].

    In general, it turns out to rarely be useful to consider categories like Lst that are defined as the image of some type constructor. I'm not sure where this (very common) idea comes from. I recommend you set aside the idea of "the category Lst". Just one category is enough for now!

    For an analogy consider the function that squares a real number f(x) = x^2. We can view this as a function f : R -> R from the real numbers to the real numbers, even though it so happens that f(x) only takes on nonnegative real values. The target of f does not have to be equal to the image of f (the values that are actually attained by f on its input values).