StateT over Cont. Why is my state not being reset?

Question

I'm playing with the Cont monad tricks described here and in this SO question.

This function lets you "jump back" to earlier in the computation, taking a parameter so you can do things differently:

import Control.Monad.Cont
import Control.Monad.State.Strict
import Control.Monad.Writer.Strict

getCC' :: MonadCont m => a -> m (a,a -> m b)
getCC' x0 = callCC (\c -> let f x = c (x, f) in return (x0, f))

I have these toy examples of monad transformers on top of Cont:

foo :: WriterT String (Cont String) ()
foo = do
    (stop,loop) <- getCC' False
    if stop
        then do tell "bbb"
        else do tell "aaa"
                loop True

foo' :: StateT String (Cont String) ()
foo' = do
    (stop,loop) <- getCC' False
    if stop
        then do modify $ \s -> s ++ "bbb"
        else do modify $ \s -> s ++ "aaa"
                loop True

In the first example (as explained in the linked SO question) the effects of Cont have "priority" over the effects of the WriterT. When we reset the computation, the log is lost:

*Main> print $ runCont (execWriterT foo) id
"bbb"

The second example does exactly the same thing, only using StateT instead of WriterT. However, in this case the log is preserved!

*Main> print $ runCont (execStateT foo' "") id
"aaabbb"

What is the explanation of this discrepancy?

chi · Accepted Answer · 2017-07-08T17:31:37.923

(I feel this is not a completely satisfactory answer, but at least it should clarify a little.)

I believe this is because of the lifting of callCC. In the state monad case, after chasing the rabbit down the hole, we meet this:

liftCallCC :: CallCC m (a, s) (b, s) -> CallCC (StateT s m) a b
Uniform lifting of a callCC operation to the new monad. This version rolls back to the original state on entering the continuation.
liftCallCC' :: CallCC m (a, s) (b, s) -> CallCC (StateT s m) a b
In-situ lifting of a callCC operation to the new monad. This version uses the current state on entering the continuation.

Which one is taken? The one preserving state:

instance MonadCont m => MonadCont (LazyState.StateT s m) where
    callCC = LazyState.liftCallCC' callCC

instance MonadCont m => MonadCont (StrictState.StateT s m) where
    callCC = StrictState.liftCallCC' callCC

What happens for the writer monad?

instance (Monoid w, MonadCont m) => MonadCont (LazyWriter.WriterT w m) where
    callCC = LazyWriter.liftCallCC callCC

instance (Monoid w, MonadCont m) => MonadCont (StrictWriter.WriterT w m) where
    callCC = StrictWriter.liftCallCC callCC

Ah-ha! No '!

liftCallCC :: Monoid w => CallCC m (a, w) (b, w) -> CallCC (WriterT w m) a b
Lift a callCC operation to the new monad.

No state-preserving variant is found in the library. The above variant, instead, is found there defined as

liftCallCC callCC f = WriterT $
    callCC $ \ c ->
    runWriterT (f (\ a -> WriterT $ c (a, mempty)))

Note the mempty. If we had a get operation, we could store there the "current state", so that it is not lost in the process, but if we had that we would no longer be in the writer monad, but in the state one.

Also note that stacking the monads in the opposite order achieves what we'd want.

bar :: ContT String (Writer String) ()
bar = do
    (stop,loop) <- getCC' False
    if stop
        then do lift $tell "bbb"
        else do lift $ tell "aaa"
                loop True

-- > runWriter (runContT bar (const $ pure ""))
-- ("","aaabbb")

I feel the state-forgetting behaviour should be the default one, not just for uniformity with `WriterT`, but to enforce the intuitive rule that the effects of inner monads "have priority" in some sense. — danidiaz, Jul 08 '17 at 17:59

StateT over Cont. Why is my state not being reset?

1 Answers1