Do you want to play a game ?
Today you will receive callCC .
callCC :: ((a -> (forall r. ContT mr)) -> ContT ma) -> ContT ma -- you are here ^^
Everything to the left of this arrow of the function is the movements that your opponent made. To the right of the arrow is the end of the game. To win, you must build something that corresponds to the right side, using only the items that your opponent has provided.
Fortunately, you still have some words in deeds. See this arrow here?
callCC :: ((a -> (forall r. ContT mr)) -> ContT ma) -> ContT ma -- this is your opponent ^^
When you get something that contains an arrow, everything to the left of it is the steps you take and the part to the right of the end of this game branch, giving you another piece that you can use as part of yours (I hope ) winning strategy.
Before moving on, simplify a few things: the monad transformer aspect is just a distraction, so drop it; and add explicit quantifiers for each type variable.
callCC :: forall a. ((a -> (forall b. Cont b)) -> Cont a) -> Cont a
Now think of a type like forall a. ... forall a. ... If you produce something like this type, you say you can provide a value for any type a in general. If you get something with a similar type, you can choose a specific type to use. Compare this to a type of type A -> ... for a monomorphic function; when creating such a function, you say that you know how to provide a result for any value of type a , while obtaining such a function allows you to select the specific value of a to use. This is similar to the situation with forall , and in fact, parallta is executed. Thus, we can consider forall as an indication of the movement in which you or your opponent acquires a type, not a term. To reflect this, I will abuse the notation and write forall a. ... forall a. ... like a => ; we can handle it the same way as (->) , except that it should appear to the left of any applications of the associated type variable.
It can also be noted that the only thing that can be done directly with a value of type Cont a is to apply runCont to it. Therefore, we will do this in advance and enter all the relevant quantifiers directly into the type for callCC .
callCC :: a => ( (a -> (b => (r1 => (b -> r1) -> r1))) -> (r2 => (a -> r2) -> r2) ) -> (r3 => (a -> r3) -> r3)
Since we can treat forall in the same way as other function arrows, we can reorder things and remove the extra parentheses to work a bit. In particular, note that callCC is not really the end of the game, as it turns out; we must provide a function that boils down to providing another game in which we will again play the role of the rightmost arrow. Thus, we can keep the step by combining them. I will also use arguments like float on the left to get them all in one place.
callCC :: a => r3 => (a -> r3) -> (r2 => (b => r1 => a -> (b -> r1) -> r1) -> (a -> r2) -> r2) -> r3
So ... our move.
We need something like r3 . Our opponent made four moves that we received as arguments. One step is to choose r3 , so we are already at a disadvantage. Another move is a -> r3 , which means that if we can play a , our opponent will cough r3 , and we will be able to win. Unfortunately, our opponent also played a , so we returned to where we started. We will need something like a or some other way to get something like r3 .
The last step made by our opponent is more difficult, so we will consider it alone:
r2 => (b => r1 => a -> (b -> r1) -> r1) -> (a -> r2) -> r2
Remember that this is the step they took. So, the rightmost arrow here represents our opponent, and everything on the left represents the type of movements we can make. The result of this is something like r2 , where r2 is what we play. Therefore, we must play either r3 or a to make any progress.
Game a : If we play a as r2 , then we can play id as a -> r2 . The other move is more complicated, so we will move inside this one.
b => r1 => a -> (b -> r1) -> r1
Back to the rightmost arrow representing us. This time we need to produce something like r1 , where r1 is the step that the opponent took. They also played the function b -> r1 , where type b was also the step they took. So we need something like type b or r1 . Unfortunately, all they gave us was something like a , leaving us in an impregnable position. Guess that playing a used to be a bad choice. Try again...
Game r3 : If we play r3 as r2 , we also need to play the function a -> r3 ; fortunately, the adversary has already played such a function, so we can just use it. Once again, jump into another movement:
b => r1 => a -> (b -> r1) -> r1
... only to find that this is exactly the same impossible situation as before. Being at the mercy of the choice of the opponent r1 , not demanding that they provide a way of construction, we find ourselves in a trap.
Perhaps a little cheating will help?
Bend Rules - Play r1 :
We know that in regular Haskell, we can rely on laziness to twist things and allow computing to learn its own tail. Without worrying too much about how, suppose we can do the same here - take r1 , which our opponent plays in the internal game, and pull it out and come back to play it like r2 .
Once again, here the adversary moves:
r2 => (b => r1 => a -> (b -> r1) -> r1) -> (a -> r2) -> r2
After we connect the nodes to the nodes, this ends with the equivalent of this:
(b => a -> (b -> r1) -> r1) -> (a -> r1) -> r1
Arguments like this have disappeared thanks to our deception, but r1 is still chosen by the adversary. So, all that we have achieved here is shuffling things; we cannot even hope to get a or r3 from him, so we hit another dead end.
So, we make one final, desperate attempt:
Bend Rules - Playback b :
This time we take b which the opponent plays in the innermost game and loop to play like r2 . Now the enemy’s movement is as follows:
(r1 => a -> (b -> r1) -> r1) -> (a -> b) -> b
And again in the inner game:
r1 => a -> (b -> r1) -> r1
Continuing the deception, we can twist the result of b higher, and also, to give the function b -> r1 , we need r1 . Success!
Having retreated, we still have one problem. We need to play something like a -> b . There is no obvious way to find it, but we already have b , so we can just use const to drop a and -
- but wait. Where does this type b value come first? In short, in our shoes against the opponent, the only places where they can get are the result of the actions we do. If only b we have the one that they give us, we end up in circles; the game never ends.
So, in the game callCC only strategies that we led to the loss or permanent impasse.
callCC :: forall a. ((a -> (forall b . Cont b)) -> Cont a) -> Cont a callCC = error "A strange game..."
Alas, it seems that the only winning move is not to play.