5

I am trying to understand continuation in general following this tutorial.

However, I am having difficulties to understand 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 the type of k. According to my understanding, k captures all computation comes subsequently after get (), and since we are talking about a state monad, k is reasonable to represent a computation that will be continued by taking an int, hence

k : int => 'a

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

k : int => int => 'a

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

Compared to the actual state monad implementation, the confusion adds more:

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

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

Can anyone give a lead?

Secondly, how am I supposed to implement get here using Haskell's Control.Monad.Trans.Cont? I am having problems comforting the type system.

UPDATE

It seems I got the second one:

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

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

iehrlich
  • 3,572
  • 4
  • 34
  • 43
Jason Hu
  • 6,239
  • 1
  • 20
  • 41
  • @Bergi it's actually called OchaCaml. I am following the tutorial but I don't think languages in use impact the understanding of the concept in this case. – Jason Hu Jun 15 '17 at 02:43

1 Answers1

4

You apply k on state twice because the first one corresponds to the result of get () (we want get's effect to be retrieving the current state and returning it as the result) and the second one corresponds to passing the state after the get (which, because get doesn't change the state, is the same as the state before the get) to the next stateful computation.

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

Cactus
  • 27,075
  • 9
  • 69
  • 149
  • that's the main part i don't get. should continuation be enough just by passing the current state already? i also don't understand how to step from the state monad version to cps version. – Jason Hu Jun 15 '17 at 02:46
  • also how can i know the type of continuation just by looking at the code? which part should i look, the hole or not the hole? – Jason Hu Jun 15 '17 at 02:50
  • Think of what you would want to pass if the result of `get` was supposed to be the current state + 1 (fixing it to `State Int` for the sake of example). The subsequent state would still be the same as the incoming state, but the result would be different. So you'd need to pass `state + 1` as the result argument and `state` as the new state argument to the continuation. – Cactus Jun 15 '17 at 07:17