haskell - `get` 在 CPS 版本的 State monad 中是如何工作的？

Question

我试图理解这个 tutorial 之后的一般延续.

但是，我很难理解第 2.10 节中的以下示例:

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

state是 int 类型我想。我没有得到的是 k 的类型.据我了解，k捕获所有计算随后发生在 get () 之后，并且由于我们正在谈论一个状态单子(monad)，k表示将通过取 int 来继续的计算是合理的。 ， 因此

k : int => 'a

但从代码来看，它似乎没有这样做，它需要state第二次，这实际上意味着:

k : int => int => 'a

但我不知道第二个是从哪里来的，在什么意义上get是 unit => 'a 类型而不是 unit => int => 'a ?

与实际的 state monad 实现相比，困惑增加了更多:

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

即状态转换表示为从状态到结果和状态的元组的函数，这符合我的第一个理解。

任何人都可以领导吗？

其次，我应该如何实现get这里使用 Haskell 的 Control.Monad.Trans.Cont ?我在安慰类型系统时遇到问题。

更新

看来我得到了第二个:

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

但我仍然不明白为什么我需要将状态两次应用于延续。

Answer 1

您申请k在 state两次，因为第一个对应于 get () 的结果(我们希望 get 的效果是检索当前状态并将其作为结果返回)，第二个对应于在 get 之后传递状态(因为 get 不改变状态，与 get 之前的状态相同)到下一个有状态计算。

换句话说，由于状态单子(monad)是 State s a ~ s -> (a, s) ，其 CPS 版本为 State s r a ~ s -> (a -> s -> r) -> r ，所以对于 get : State s s , 因为 a ~ s , 延续将是 s -> s -> r 类型的函数.