9

在尝试为 ContT monad 转换器建立一些直觉时，我（也许并不奇怪）发现自己很困惑。问题在于 shiftT 操作，它似乎没有做任何有用的事情。

首先是一个简单的例子，说明如何使用它

shiftT $ \famr -> lift $ do
  a <- calculateAFromEnvironment
  famr a

famr a可能是一些更复杂的表达式，只要它返回 some m r。现在试图解释我的直觉 shiftT 没有添加任何东西：

-- inline shiftT
ContT (\f2 -> evalContT ((\f1 -> lift (do
  a <- calculateAFromEnvironment
  f1 a)) f2))

-- beta reduction
ContT (\f2 -> evalContT (lift (do
  a <- calculateAFromEnvironment
  f2 a)))

-- inline evalConT
ContT (\f2 -> runContT (lift (do
  a <- calculateAFromEnvironment
  f2 a)) return)

-- inline lift
ContT (\f2 -> runContT (ContT (\f3 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= f3)) return)

-- apply runConT
ContT (\f2 -> (\f3 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= f3) return)

-- beta reduce
ContT (\f2 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= return)

-- (>>= return) is identity
ContT $ \f2 -> do
  a <- calculateAFromEnvironment
  f2 a

事实证明，我们可以直接构建 ContT。

提问时间：是否存在 shift/shiftT 在 cont/ContT 之上添加任何内容的情况？还是它们只是用来使代码更具可读性？

4

2 回答 2

9

在通过Gurkenglas的建议搜索 github之后，我发现了这个非常好的解释以及用法、动机和语义的示例！shiftTresetT

这些功能非常简单。它们在transformers库中的定义很简单：

resetT :: (Monad m) => ContT r m r -> ContT r' m r
resetT = lift . evalContT

shiftT :: (Monad m) => ((a -> m r) -> ContT r m r) -> ContT r m a
shiftT f = ContT (evalContT . f)

但哲学和意义远远落后于一些直观的理解。所以我建议你从上面的链接中阅读解释。有时，容易定义的事情实际上可以做一些复杂的事情。

从上面链接的哈巴狗的解释中改编的文档：

shiftT

shiftT就像callCC，除了当您激活 提供的延续时shiftT，它将运行到最近的封闭 的末尾resetT，然后跳回到您激活延续的点之后。请注意，因为控制最终会回到激活子延续后的点，所以您可以在同一个块中多次激活它。这与callCC's continuations 不同，后者在激活时会丢弃当前的执行路径。

resetT有关这些分隔的子延续如何实际工作的示例，请参阅。

resetT

创建一个范围，它shiftT的子延续保证最终退出。考虑这个例子：

resetT $ do
    alfa
    bravo
    x <- shiftT $ \esc -> do   -- note: esc :: m Int, not a ContT
       charlie
       lift $ esc 1
       delta
       lift $ esc 2
       return 0
    zulu x

这将：

  1. 履行alfa

  2. 履行bravo

  3. 履行charlie

  4. 绑定x到 1，从而执行zulu 1

  5. 从末端掉下来resetT，然后再跳回esc 1

  6. 履行delta

  7. 绑定x到 2，从而执行zulu 2

  8. 从末端掉下来resetT，然后再跳回esc 2

  9. 逃离resetT, 导致它产生 0

因此，与callCC' 的延续不同，这些子延续最终会在它们被激活后返回到该点，在从最近的 的末端跌落之后resetT。

于 2017-04-29T14:59:57.953 回答
4

您是对的，可以使用未定界的延续来表达定界的延续。所以 和 的定义shiftT总是resetT可以用 just 来描述ContT。但：

  • 定界的延续不太强大。这使它们更容易实现，也更容易为人类推理。（另请参阅Oleg Kiselyov的许多其他有趣的关于延续的帖子）。
  • 使用熟悉的移位/重置符号更容易理解，特别是对于那些熟悉这个概念的人。

本质上，延续允许将程序从里到外：当调用传递的函数时，由 分隔的块reset被压缩到程序的内部。shift（在无限延续的情况下，整个执行上下文被压缩在里面，这就是让它们如此奇怪的原因。）

让我们举几个例子：

import Data.List
import Control.Monad
import Control.Monad.Trans
import Control.Monad.Trans.Cont

test0 :: Integer
test0 = evalCont . reset $ do
    return 0

如果我们reset没有shift，它只是一个纯粹的计算，没什么特别的。上面的函数只是简单地返回0.

现在让我们同时使用它们：

test1 :: Integer
test1 = evalCont . reset $ do
    r <- shift $ \esc -> do
        let x = esc 2
            y = esc 3
        return $ x * y
    return $ 1 + r

这变得更有趣了。shift和之间的代码reset实际上被压缩到 的调用中esc，在这个简单的例子中它只是return $ 1 + r. 当我们调用esc时，将执行整个计算，其结果成为esc调用的结果。我们这样做了两次，所以本质上我们调用了两次之间shift的所有内容reset。而整个计算result $ x * y的结果就是shift调用的结果。

所以从某种意义上说，shift块成为计算的外部部分，中间的块成为计算reset的shift内部部分。

到目前为止，一切都很好。shift但是，如果我们调用两次，就会变得更加令人生畏，就像在这个代码示例中一样：

list2 :: [(Int, String)]
list2 = evalCont . reset $ do
    x <- shift $ \yieldx ->
        return $ concatMap yieldx [1, 2, 3]
    y <- shift $ \yieldy ->
        return $ concatMap yieldy ["a", "b", "c"]
    return [(x, y)]

这是它产生的结果（对于那些想要尝试将其作为练习的人隐藏）：

[(1,"a"),(1,"b"),(1,"c"),(2,"a"),(2,"b"),(2,"c"),(3,"a"),(3,"b"),(3,"c")]

现在发生的事情是程序被翻了两次：

  1. 首先，x <- shift ...块外的所有内容都绑定到yieldx调用，包括下一个shift。并且计算的结果是x <- shift ...块的结果。
  2. 其次，当调用第二个y <- shift ...insideyieldx时，其余的计算再次绑定到yieldy调用。而这个内部计算的结果就是y <- shift ...块的结果。

因此，在x <- shift我们为三个参数中的每一个运行其余的计算时，在每个参数中，我们对其他三个参数中的每一个都做类似的事情。结果是两个列表的笛卡尔积，因为我们基本上执行了两个嵌套循环。

同样的事情也适用于shiftTand resetT，只是增加了副作用。例如，如果我们想调试实际发生的事情，我们可以在IOmonad 中运行上述代码并打印调试语句：

list2' :: IO [(Int, String)]
list2' = evalContT . resetT $ do
    x <- shiftT $ \yield ->
        lift . liftM concat . mapM (\n -> print n >> yield n) $ [1, 2, 3]
    y <- shiftT $ \yield ->
        lift . liftM concat . mapM (\n -> print n >> yield n) $ ["a", "b", "c"]
    return [(x, y)]
于 2017-04-30T20:15:43.057 回答