Mon Aug 15 19:50:05 CEST 2011

From Applicative to Monad

Each Monad gives rise to an Applicative where

    pure = return
    <*> = ap

Where ap is:

    ap mf ma = do
      f <- mf
      a <- ma
      return $ f a


    ap = liftM2 ($)

but not all Applicatives are Monads.  See [1][2] for examples.

So, does it make sense to say that I was not able to encode a certain
behaviour as Applicative, but was able to do it as Monad?

Yes it does, since requiring Monad is requiring more structure.

What I tried to accomplish could be implemented as composition of
Kleisli arrows (a -> M b), which is something an Applicative can't do.

( I'm implementing recurrence relations represented as

  data Sig s a = {init :: s, next :: s -> (a,s)) }

  and the corresponsing signal operators.  I settled on signals as
  monad values and operators as Kleisli arrows.  Note that isn't a
  true monad due to the dependence on the `s' parameter, which isn't
  constant for join )

So which primitives to implement to define both Monad and Applicative?
It seems this only needs:

   (pure/return, join, ap)
   (pure/return, join, fmap)

So Functor to Monad needs return+join, while Applicative to Monad only
needs join since it already has return.  The join operation is what
implements the "monadness", the piercing of monad structure to "get
stuf out" which is necessary to chain Kleisli arrows, while
pure/return only put stuff inside the Monad.

[1] http://haskell.1045720.n5.nabble.com/Applicative-but-not-Monad-td3142155.html
[2] http://en.wikibooks.org/wiki/Haskell/Applicative_Functors#ZipLists