How to get a job in the CPS version of the state monad?

Question

I am trying to understand the sequel as a whole by following this tutorial .

However, it is difficult for me to understand the following example in section 2.10:

# let get () = shift (fun k -> fun state -> k state state) ;; get : unit => 'a = <fun> 

state is of type int , I suppose. What I don't get is type k . In my opinion, k fixes that all calculations appear after get () , and since we are talking about the state monad, k it is reasonable to imagine a calculation that will continue by taking int , therefore

 k : int => 'a 

but from the code, it doesn't seem to do this, and it takes state a second time, which actually means:

 k : int => int => 'a 

but I don’t get where the second comes from, and in what sense get is of type unit => 'a instead of unit => int => 'a ?

Compared to the real monad-monad implementation, the confusion adds more:

 newtype StateT sma = StateT { runStateT :: s -> m (a,s) } 

i.e. state transition is represented as a function of state to a tuple of result and state, which corresponds to my first understanding.

Can anyone give an edge?

Secondly, how can I implement get here using Haskell Control.Monad.Trans.Cont ? I have problems with a type system.

---

UPDATE

It seems I have a second:

 Prelude Control.Monad.Trans.Cont> let get () = shift $ \k -> return $ \i -> kii 

But I still don't understand why I need to apply the state twice to the continuation.

Answer 1

You apply k on state twice, because the first corresponds to the result of get () (we want the get effect to return the current state and return it as a result), and the second corresponds to pass the state after get (which, since get does not change the state, matches the state before get ) until the next stateful calculation.

In other words, since the state monad State sa ~ s -> (a, s) , its version is CPS State sra ~ s -> (a -> s -> r) -> r , therefore for get : State ss , since a ~ s , the continuation will be a function of the type s -> s -> r .