Lifting inside continuations

Question

I have a continuation with type (a -> b) -> b. I also have a function that is "almost" a suitable context, with type Monad m => a -> m b. Is there a way to upgrade the continuation from (a -> b) -> b to (a -> m b) -> m b? My instinct is no, but I'd like to be wrong about this.

Answer 1

It is indeed impossible, at least in the general case where m can be an arbitrary monad.

Assume the monad m is the continuation monad (- -> r) -> r. (I omit the newtype wrapper for clarity).

Then, what you want is a way to convert (a -> b) -> b into (a -> (b -> r) -> r) -> (b -> r) -> r. In other words, you want a polymorphic term of type

t :: ((a -> b) -> b) -> (a -> (b -> r) -> r) -> (b -> r) -> r

We prove that t can not exist by contradiction. Let us assume such a t exists. We can specialize it by choosing r~a and b~Void (the empty type).

t :: ((a -> Void) -> Void) -> (a -> (Void -> a) -> a) -> (Void -> a) -> a

Now, recall we have a (total!) function absurd :: Void -> a (essentially, absurd x = case x of {}). We then get

\ x -> t x (\y _ -> y) absurd
:: ((a -> Void) -> Void) -> a

By the Curry-Howard isomorphism the following would be a logical tautology in intuitionistic logic:

((A -> False) -> False) -> A

But the formula above is Not (Not A) -> A, i.e., double negation elimination, which is known to be impossible to prove in intuitionistic logic. Hence, we get a contradiction, and we have to conclude that there is no term t of that type.

Note that t could exist for other monads m.