Cont monad shift

Question

While trying to build some intuition for the ContT monad transformer I (perhaps unsurprisingly) found myself confused. The issue lies with the shiftT operation which doesn't seem to do anything useful.

First a simplistic example of how one might use it

shiftT $ \famr -> lift $ do
  a <- calculateAFromEnvironment
  famr a

famr a could be some more complex expression as long as it returns some m r. Now an attempt to explain my intuition that shiftT is doesn't add anything:

-- inline shiftT
ContT (\f2 -> evalContT ((\f1 -> lift (do
  a <- calculateAFromEnvironment
  f1 a)) f2))

-- beta reduction
ContT (\f2 -> evalContT (lift (do
  a <- calculateAFromEnvironment
  f2 a)))

-- inline evalConT
ContT (\f2 -> runContT (lift (do
  a <- calculateAFromEnvironment
  f2 a)) return)

-- inline lift
ContT (\f2 -> runContT (ContT (\f3 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= f3)) return)

-- apply runConT
ContT (\f2 -> (\f3 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= f3) return)

-- beta reduce
ContT (\f2 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= return)

-- (>>= return) is identity
ContT $ \f2 -> do
  a <- calculateAFromEnvironment
  f2 a

Turns out we could have just build the ContT directly.

Question time: Is there a situation where shift/shiftT add anything over cont/ContT? Or are they just used to make the code more readable?

Answer 1

After searching github by Gurkenglas's advice I've discovered this very nice explanation of shiftT and resetT with examples of usages, motivation and semantic!

Those functions are very simple. Their definition in transformers library is straightforward:

resetT :: (Monad m) => ContT r m r -> ContT r' m r
resetT = lift . evalContT

shiftT :: (Monad m) => ((a -> m r) -> ContT r m r) -> ContT r m a
shiftT f = ContT (evalContT . f)

But philosophy and meaning far behind some intuitive understanding. So I recommend you to read explanation from the link above. Sometimes it happens that things that are easy to define actually can do something complex.

Adapted documentation from the explanation in pugs linked above:

shiftT

shiftT is like callCC, except that when you activate the continuation provided by shiftT, it will run to the end of the nearest enclosing resetT, then jump back to just after the point at which you activated the continuation. Note that because control eventually returns to the point after the subcontinuation is activated, you can activate it multiple times in the same block. This is unlike callCC's continuations, which discard the current execution path when activated.

See resetT for an example of how these delimited subcontinuations actually work.

resetT

Create a scope that shiftT's subcontinuations are guaranteed to eventually exit out the end of. Consider this example:

resetT $ do
    alfa
    bravo
    x <- shiftT $ \esc -> do   -- note: esc :: m Int, not a ContT
       charlie
       lift $ esc 1
       delta
       lift $ esc 2
       return 0
    zulu x

This will:

1. Perform alfa

2. Perform bravo

3. Perform charlie

4. Bind x to 1, and thus perform zulu 1

5. Fall off the end of resetT, and jump back to just after esc 1

6. Perform delta

7. Bind x to 2, and thus perform zulu 2

8. Fall off the end of resetT, and jump back to just after esc 2

9. Escape from the resetT, causing it to yield 0

Thus, unlike callCC's continuations, these subcontinuations will eventually return to the point after they are activated, after falling off the end of the nearest resetT.