Implementing Applicative (<*>) for StateT

Question

This question has been asked before, but without a real answer. In fact the accepted answer suggests that it is not possible, despite the fact that

StateT is a Monad, and hence a superset of Applicative. As a result, the standard libraries simply use (<*>) = ap
(as Petr notes) composing applicatives always yields an applicative.

One of the implementations of MaybeT I've read about used

liftA2 (<*>) :: (Applicative f, Applicative f1) => f (f1 (a -> b)) -> f (f1 a) -> f (f1 b)

to implement Applicative but I can't make that work here. My work in progress has tried lots of options around the following:

-- (<*>) :: StateT s f (a -> b) -> State s f a -> State s f b
instance (Applicative f) => Applicative (StateT s f) where
    pure a =  StateT $ \s -> pure (a, s)
    (StateT f) <*> (StateT g) = StateT $ \s ->          -- f :: s -> m (a -> b, s),  g :: s -> m (a, s)
                                    let
                                        mabs = f s          -- mabs :: m (a -> b, s)
                                        mab = fmap fst mabs
                                        ms' = fmap snd mabs

                                    in undefined

I'm wondering what I am missing, and hoping that I will learn something about Applicative in the process.

Stacking transformers is not quite the same as composing functors. Hence "composing applicatives always yields an applicative" doesn't really help. — leftaroundabout, Jan 12 '15 at 14:12
...if you're ok with `(Monad f) => `, then the task is of course simple: just inline the definition of `>>=` into the definition of `ap`, and simplify. — leftaroundabout, Jan 12 '15 at 14:18

score 4 · Answer 1 · answered Jan 12 '15 at 14:37

Tony uses some alternative notation, and Simon's answer is very terse, so here is what I ended up with:

-- (<*>) :: StateT s f (a -> b) -> State s f a -> State s f b
instance (Monad f, Applicative f) => Applicative (StateT s f) where
    pure a =  StateT $ \s -> pure (a, s)
    StateT f <*> StateT a =
        StateT $ \s -> 
                f s >>= \(g, t) ->                   -- (f s) :: m (a->b, s)
                    let mapper = \(z, u) -> (g z, u) -- :: (a, s) -> (b, s)
                    in fmap mapper (a t)             -- (a t) :: m (a, s)

I had to declare f also a Monad, but that is OK as it is part of the definition of a Monad transformer, as I understand it.

score 2 · Accepted Answer · edited Jan 12 '15 at 14:57

2

An implementation (taken from Tony Morris' functional programming course) could be

(<*>) :: (Functor f, Monad f) =>
  StateT s f (a -> b)
  -> StateT s f a
  -> StateT s f b
StateT f <*> StateT a =
  StateT (\s -> (\(g, t) -> (\(z, u) -> (g z, u)) <$> a t) =<< f s)

edited Jan 12 '15 at 14:57

Daniel Wagner

145,880
9
220
380

answered Jan 12 '15 at 14:04

Simon Gibbons

6,969
1
21
34

That uses a monadic bind. – leftaroundabout Jan 12 '15 at 14:07
That's OK, because f is a Monad by defintion of a Transformer. I just need to de-minify the rest... – Simon H Jan 12 '15 at 14:16

Implementing Applicative (<*>) for StateT

2 Answers2