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

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?

与实际状态monad实现相比，混乱增加了更多：

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

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

任何人都可以提供线索吗？

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

更新

我好像得到了第二个：

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

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

Answer 1

您在 state 上应用 k 两次，因为第一个对应于 get () 的结果（我们希望 get 的效果是检索当前状态并将其作为结果返回），第二个对应于在 get 之后传递状态（因为 get 不会更改状态，所以与 [=13 之前的状态相同=]) 到下一个有状态计算。

换句话说，由于状态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.

类型的函数

How does `get` work in the CPS version of the State monad?