On Wed, Feb 15, 2017 at 12:01 PM, Laurent Christophe <lachrist@vub.ac.be> wrote:
Hi guys, the way `StateT` are implemented as `Applicative` have been buggling my mind for some time.

instance (Functor m, Monad m) => Applicative (StateT s m) where
    pure a = StateT $ \ s -> return (a, s)
    StateT mf <*> StateT mx = StateT $ \ s -> do
        (f, s') <- mf s
        (x, s'') <- mx s'
        return (f x, s'')

Using dependant monadic computations, this implementation cannot be expressed in term of applicative.
This explains why we cannot have `instance (Applicative m) => Applicative (State s m)`.
However using real monadic style computations for implementing `<*>` buggles my mind.
Moreover `liftA2 (<*>)` can be used to generically compose applicative functors so why monads are needed?

StateT s m is not a composition of applicative functors. It allows two-way communication between the state and the underlying monad m.

Like Compose m (State s), effects in m can affect how the state evolves. Like Compose (State s) m, the state can influence what effects occur in m.

For example, StateT s Maybe will discard changes to the state if a subcomputation returns Nothing and permits subcomputations to choose whether to return Nothing based on the state. No applicative composition of State s and Maybe can do both.

These limitations are implied by the underlying types:

Compose m (State s) a = m (s -> (a, s))
Compose (State s) m a = s -> (m a, s)
StateT s m a          = s -> m (a, s)


--
Dave Menendez <dave@zednenem.com>
<http://www.eyrie.org/~zednenem/>