haskell - 如何使callCC更动态？

我认为ContT的正确类型应该是

newtype ContT m a = ContT {runContT :: forall r. (a -> m r) -> m r}

和其他控制运算符(operator)

shift :: Monad m => (forall r. (a -> ContT m r) -> ContT m r) -> ContT m a
reset :: Monad m => ContT m a -> ContT m a
callCC :: ((a -> (forall r. ContT m r)) -> ContT m a) -> ContT m a

不幸的是，我无法进行callCC类型检查，也不知道该怎么做。
我设法进行shift和reset类型检查

reset :: Monad m => ContT m a -> ContT m a
reset e = ContT $ \ k -> runContT e return >>= k

shift :: Monad m => (forall r. (a -> ContT m r) -> ContT m r) -> ContT m a
shift e = ContT $ \ (k :: a -> m r) ->
    runContT ((e $ \ v -> ContT $ \c -> k v >>= c) :: ContT m r) return

但是我仍然不能在像这样的递归跳转中使用shift和reset吗？

newtype H r m = H (H r m -> ContT m r)

unH (H x) = x

test = flip runContT return $ reset $ do
    jump <- shift (\f -> f (H f))
    lift . print $ "hello"
    unH jump jump

有人尝试过吗？

最佳答案

您要play a game吗？

今天，您将成为callCC。

callCC :: ((a -> (forall r. ContT m r)) -> ContT m a) -> ContT m a
--                                       you are here ^^

该功能箭头左侧的所有内容都是对手所做的 Action 。箭头的右边是游戏的结尾。为了赢得胜利，您必须仅使用对手提供的棋子来构建与右侧匹配的东西。

幸运的是，您在事情上仍有发言权。在这里看到这个箭头？

callCC :: ((a -> (forall r. ContT m r)) -> ContT m a) -> ContT m a
--                this is your opponent ^^

当您收到本身包含箭头的内容时，该位置左侧的所有内容都代表您要进行的 Action ，而右侧部分则表示该游戏分支的末端，从而为您提供了另一个可以用作您的一部分(希望如此)制胜策略。

在进行下一步之前，让我们简化一些事情:monad变压器方面只是一种干扰，因此请舍弃；并为每个类型变量添加显式量词。

callCC :: forall a. ((a -> (forall b. Cont b)) -> Cont a) -> Cont a

现在，考虑一下像forall a. ...这样的类型。如果您生成具有类似类型的内容，就是说您可以为任何类型的a提供值。如果收到类似类型的东西，则可以选择要使用的特定类型。将其与A -> ...之类的单态函数进行比较；产生这样的函数表示您知道如何为A类型的任何值提供结果，而接收到这样的函数可以让您选择要使用的特定值A。这似乎与forall相同，并且实际上并行成立。因此，我们可以将forall视为指示您或您的对手演奏某类型而不是术语的 Action 。为了反射(reflect)这一点，我将滥用表示法并将forall a. ...编写为a =>；然后，我们可以像对待(->)一样对待它，只不过它必须出现在绑定(bind)的类型变量的任何使用的左侧。

我们还可以注意到，唯一可以使用Cont a类型的值完成的操作就是对其应用runCont。因此，我们将提前进行此操作，并将所有相关的量词直接嵌入callCC的类型中。

callCC :: a => ( (a -> (b => (r1 => (b -> r1) -> r1)))
               -> (r2 => (a -> r2) -> r2)
               ) -> (r3 => (a -> r3) -> r3)

因为我们能够像对待其他功能箭头一样对待forall，所以我们可以对事物进行重新排序并删除多余的括号以使事物整理得更整洁。特别要注意的是，事实证明callCC实际上并没有结束。我们必须提供一个功能，相当于提供另一个游戏，在该游戏中我们再次扮演最右边的箭头的角色。因此，我们可以通过合并这些步骤来节省步骤。我还将类型参数 float 到左侧以将它们全部放在一个位置。

callCC :: a => r3 => (a -> r3)
       -> (r2 => (b => r1 => a -> (b -> r1) -> r1) -> (a -> r2) -> r2)
       -> r3

所以...我们的举动。

我们需要r3类型的东西。我们的对手已经采取了四项措施，我们已将其作为论据。一种方法是选择r3，所以我们已经处于不利地位。另一个 Action 是a -> r3，这意味着如果我们可以播放a，我们的对手就会咳嗽出r3，然后我们就可以胜利。不幸的是，我们的对手也玩过a，所以我们回到了起点。我们要么需要某种a类型的东西，要么需要某种其他方式来获得r3类型的东西。

我们对手的最后一步比较复杂，因此我们将单独研究一下:

r2 => (b => r1 => a -> (b -> r1) -> r1) -> (a -> r2) -> r2

记住，这是他们采取的行动。因此，这里最右边的箭头代表我们的对手，左边的一切代表我们可以做出的 Action 类型。结果是r2类型的东西，其中r2是我们要玩的东西。所以很明显，我们需要播放r3或a才能取得任何进展。

播放a:如果我们将a用作r2，则可以将id用作a -> r2。另一步更加复杂，因此我们将深入其中。

b => r1 => a -> (b -> r1) -> r1

返回最右边代表我们的箭头。这次，我们需要产生r1类型的东西，其中r1是对手做出的 Action 。他们还播放了一个函数b -> r1，其中b类型也是他们所做的。因此，我们需要它们中的b或r1类型的东西。不幸的是，他们给我们的只是a类型的东西，这使我们处于无法赢得的位置。猜猜早点播放a是一个错误的选择。让我们再试一次...

播放r3:如果我们将r3当作r2播放，我们还需要播放a -> r3函数；幸运的是，对手已经发挥了这样的作用，所以我们可以简单地使用它。我们再次跳进了另一步:

b => r1 => a -> (b -> r1) -> r1

...只是发现它和以前完全一样是不可能的情况。受制于对手选择r1的摆设，而不要求他们提供一种构造方式的选择，这使我们陷入困境。

也许有些欺骗会有所帮助？

弯曲规则-播放r1:

我们知道，在常规的Haskell中，我们可以依靠惰性来扭转事物，让计算吞噬自己的尾巴。不用太担心如何做，让我们想象一下我们可以在这里做同样的事情-拿我们对手在内部游戏中玩的r1，然后将其拉回并作为r2播放。

再次，这是对手的 Action :

r2 => (b => r1 => a -> (b -> r1) -> r1) -> (a -> r2) -> r2

在我们打结恶作剧之后，它最终等同于以下内容:

(b => a -> (b -> r1) -> r1) -> (a -> r1) -> r1

由于我们的欺骗，类型参数已消失，但是对手仍然选择了r1。因此，我们在这里完成的所有工作就是重新整理事情；显然，我们甚至都没有希望从中获得a或r3的方法，因此我们遇到了另一个死胡同。

因此，我们进行了最后一次绝望的尝试:

弯曲规则-播放b:

这次，我们将对手在最内层游戏中所玩的b拿来循环播放，作为r2。现在，对手的举动如下所示:

(r1 => a -> (b -> r1) -> r1) -> (a -> b) -> b

然后回到内部游戏:

r1 => a -> (b -> r1) -> r1

继续这种技巧，我们也可以将上面的b结果扭曲，以提供给b -> r1函数，以接收我们需要的r1。成功!

退一步，我们还有一个问题。我们必须播放a -> b类型的东西。没有明显的方法可以找到一个，但是我们已经有了一个b，因此我们可以在上面使用const来丢弃a并-

- 可是等等。 b类型的值首先从哪里来？简单地把自己放在对手的鞋上，他们唯一能获得的位置就是我们做出的 Action 的结果。如果我们拥有的唯一b是他们给我们的callCC，那么我们最终将绕圈而行。游戏永无止境。

因此，在ojit_code游戏中，我们唯一导致失败或永久性僵局的策略。

callCC :: forall a. ((a -> (forall b . Cont b)) -> Cont a) -> Cont a
callCC = error "A strange game..."

las，看来唯一的制胜法宝是不上场。

关于haskell - 如何使callCC更动态？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7178919/