Every monad is an applicative functor — generalizing to other categories

7
votes

I can readily enough define general Functor and Monad classes in Haskell:

class (Category s, Category t) => Functor s t f where
    map :: s a b -> t (f a) (f b)

class Functor s s m => Monad s m where
    pure :: s a (m a)
    join :: s (m (m a)) (m a)
    join = bind id
    bind :: s a (m b) -> s (m a) (m b)
    bind f = join . map f

I'm reading this post which explains an applicative functor is a lax (closed or monoidal) functor. It does so in terms of a (exponential or monoidal) bifunctor. I know in the Haskell category, every Monad is Applicative; how can we generalize? How should we choose the (exponential or monoidal) functor in terms of which to define Applicative? What confuses me is our Monad class seems to have no notion whatsoever of the (closed or monoidal) structure.

Edit: A commenter says it is not generally possible, so now part of my question is where it is possible.

2
haskellcategoriesfunctorapplicativecategory-theory
I seem to recall that this is not generally true, and relies on the extra (closed, etc.) structure of Hask. – Rein Henrichs
hackage.haskell.org/package/constrained-categories-0.3.1.1/docs/… – leftaroundabout

2 Answers

3
votes

What confuses me is our Monad class seems to have no notion whatsoever of the (closed or monoidal) structure.

If I understood your question correctly, that would be provided via the tensorial strength of the monad. The Monad class doesn't have it because it is intrinsic to the Hask category. More concretely, it is assumed to be: 

t :: Monad m => (a, m b) -> m (a,b)
t (x, my) = my >>= \y -> return (x,y)
3
votes

Essentially, all the monoidal stuff involved in the methods of a monoidal functor happens on the target category. It can be formalised thus†:

class (Category s, Category t) => Functor s t f where
  map :: s a b -> t (f a) (f b)

class Functor s t f => Monoidal s t f where
  pureUnit :: t () (f ())
  fzip :: t (f a,f b) (f (a,b))

s-morphisms only come in if you consider the laws of a monoidal functor, which roughly say that the monoidal structure of s should be mapped into this monoidal structure of t by the functor.

Perhaps more insightful is to factor an fmap into the class methods, so it's clear what the “func-”-part of the functor does:

class Functor s t f => Monoidal s t f where
  ...
  puref :: s () y -> t () (f y)
  puref f = map f . pureUnit
  fzipWith :: s (a,b) c -> t (f a,f b) (f c)
  fzipWith f = map f . fzip

From Monoidal, we can get back our good old Hask-Applicative thus:

pure :: Monoidal (->) (->) f => a -> f a
pure a = puref (const a) ()

(<*>) :: Monoidal (->) (->) f => f (a->b) -> f a -> f b
fs <*> xs = fzipWith (uncurry ($)) (fs, xs)

or

liftA2 :: Monoidal (->) (->) f => (a->b->c) -> f a -> f b -> f c
liftA2 f xs ys = fzipWith (uncurry f) (xs,ys)

Perhaps more interesting in this context is the other direction, because that shows us up the connection to monads in the generalised case:

instance Applicative f => Monoidal (->) (->) f where
  pureUnit = pure
  fzip = \(xs,ys) -> liftA2 (,) xs ys
       = \(xs,ys) -> join $ map (\x -> map (x,) ys) xs

That lambdas and tuple sections aren't available in a general category, however they can be translated to cartesian closed categories.

†I'm using (,) as the product in both monoidal categories, with identity element (). More generally you might write data I_s and data I_t and type family (⊗) x y and type family (∙) x y for the products and their respective identity elements.