How to implement this Traversable use pattern?

Question

When use Data.Traversable I frequently requires some code like

import Control.Applicative (Applicative,(<*>),pure)
import Data.Traversable (Traversable,traverse,sequenceA)
import Control.Monad.State (state,runState)

traverseF :: Traversable t => ((a,s) -> (b,s)) -> (t a, s) -> (t b, s)
traverseF f (t,s) = runState (traverse (state.curry f) t) s

to traverse the structure and build up a new one driven by some state. And I notice the type signature pattern and believe it could be able to generalized as

fmapInner :: (Applicative f,Traversable t) => (f a -> f b) -> f (t a) -> f (t b)
fmapInner f t = ???

But I fail to implement this with just traverse, sequenceA, fmap, <*> and pure. Maybe I need stronger type class constrain? Do I absolutely need a Monad here?

UPDATE

Specifically, I want to know if I can define fmapInner for a f that work for any Traversable t and some laws for intuition applied (I don't know what the laws should be yet), is it imply that the f thing is a Monad? Since, for Monads the implementation is trivial:

--Monad m implies Applicative m but we still 
--  have to say it unless we use mapM instead
fmapInner :: (Monad m,Traversable t) => (m a -> m b) -> m (t a) -> m (t b)
fmapInner f t = t >>= Data.Traversable.mapM (\a -> f (return a))

UPDATE

Thanks for the excellent answer. I have found that my traverseF is just

import Data.Traversable (mapAccumL)
traverseF1 :: Traversable t => ((a, b) -> (a, c)) -> (a, t b) -> (a, t c)
traverseF1 =uncurry.mapAccumL.curry

without using Monad.State explicitly and have all pairs flipped. Previously I though it was mapAccumR but it is actually mapAccumL that works like traverseF.

Answer 1

I've now convinced myself that this is impossible. Here's why,

 tF ::(Applicative f, Traversable t) => (f a -> f b) -> f (t a) -> f (t b)

So we have this side-effecting computation that returns t a and we want to use this to determine what side effects happen. In other words, the value of type t a will determine what side effects happen when we apply traverse.

However this isn't possible possible with the applicative type class. We can dynamically choose values, but the side effects of out computations are static. To see what I mean,

pure :: a -> f a -- No side effects
(<*>) :: f (a -> b) -> f a -> f b -- The side effects of `f a` can't
                                  -- decide based on `f (a -> b)`.

Now there are two conceivable ways to determine side effects at depending on previous values,

smash :: f (f a) -> f a

Because then we can simply do

smash $ (f :: a -> f a) <$> (fa :: f a) :: f a

Now your function becomes

traverseF f t = smash $ traverse (f . pure) <$> t

Or we can have

bind :: m a -> (a -> m b) -> m b -- and it's obvious how `a -> m b`
                                 -- can choose side effects.

and

traverseF f t = bind t (traverse $ f . pure)

But these are join and >>= respectively and are members of the Monad typeclass. So yes, you need a monad. :(

Also, a nice, pointfree implementation of your function with monad constraints is

traverseM = (=<<) . mapM . (.return)

Edit,

I suppose it's worth noting that

traverseF :: (Applicative f,Traversable t) => (f a -> f b) -> t a -> f (t a)
traverseF = traverse . (.pure)