理解Haskell callCC示例

Question

我很难理解以前的问题的答案。我希望下面的解释能澄清一些事情。下面的示例来自fpcomplete完全

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    (k, num) <- callCC $ \k -> let f x = k (f, x)
                               in return (f, 0)
    lift $ putStrLn "beta"
    lift $ putStrLn "gamma"
    if num < 5
        then k (num + 1) >> return ()
        else lift $ print num

输出是

alpha
beta
gamma
beta
gamma
beta
gamma
beta
gamma
beta
gamma
beta
gamma
5

我想我理解这个示例是如何工作的，但是为什么需要在let中有一个callCC表达式来“返回”这个延续，以便以后可以使用它。因此，我尝试通过以下简单的示例并修改它来直接返回延续。

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    callCC $ \k -> do
      k ()
      lift $ putStrLn "uh oh..."
    lift $ putStrLn "beta"
    lift $ putStrLn "gamma"

这个指纹

alpha
beta
gamma

我将其修改如下

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    f <- callCC $ \k -> do
      lift $ putStrLn "uh oh..."
      return k
    lift $ putStrLn "beta"
    lift $ putStrLn "gamma"

这个想法是，这个延续将作为f返回，并在这个测试示例中被使用，我希望它能够打印出来。

uh oh...
beta
gamma

但是这个例子不能编译，为什么不能这样做呢？

编辑：请考虑方案中的止痛示例。据我所知，计划不会有问题，对吗？

Answer 1

用相反的顺序看你的例子。

最后一个示例由于无限类型而不进行类型检查。看看callCC的类型，它就是((a -> ContT r m b) -> ContT r m a) -> ContT r m a。如果我们试图返回延续，就会返回ContT r m (a -> ContT r m b)类型的内容。这意味着我们得到了类型相等约束a ~ (a -> ContT r m b)，这意味着a必须是一个无限类型。Haskell不允许这样做(一般来说，出于很好的理由--据我所知，这里的无穷大类型将是类似于，提供一个无穷阶函数作为参数)。

在第二个例子中，您没有提到是否有什么让您困惑的地方，但是。它没有打印“呃.”的原因是……这是因为ContT操作是由k ()生成的，与许多ContT操作不同，它不使用以下计算。这是延续函数与返回ContT操作的普通函数之间的区别(免责声明，任何函数都可以返回这样的ContT操作，但一般情况下)。因此，当您使用打印或其他任何东西跟踪k ()时，这是不相关的，因为k ()只会丢弃以下操作。

所以，第一个例子。这里的let绑定实际上只用于处理k的参数。但是这样做，我们就避免了无限的类型。实际上，我们在let绑定中做了一些递归，这与我们之前得到的无限类型有关。f有点像已经完成的递归的延续版本。

我们传递给callCC的这个lambda的类型是Num n => ((n -> ContT r m b, n) -> ContT r m b) -> ContT r m (n -> ContT r m b, n)。这与上一个示例没有相同的无限类型问题，因为我们处理了参数。您可以通过其他方式使用let绑定来执行类似的技巧，而无需添加额外的参数。例如：

recur :: Monad m => ContT r m (ContT r m ())
recur = callCC $ \k -> let r = k r in r >> return r

这可能不是一个解释得很好的答案，但基本思想是，直接返回延续会造成无限类型的问题。通过使用let绑定在传递给callCC的lambda中创建一些递归，您可以避免这种情况。

Answer 2

正如其他人所写的那样，由于无限类型，最后一个示例不进行打字。

@augustss提出了另一种解决这个问题的方法：

您还可以创建一个newtype，将无限(equi-)递归类型包装为(iso-)递归新类型。-12月12日至13日12时50分

这是我的看法：

import Control.Monad.Trans.Cont
import Control.Monad.Trans.Class

data Mu t = In { out :: t (Mu t) }

newtype C' b a = C' { unC' :: a -> b }
type C b = Mu (C' b)

unfold = unC' . out
fold = In . C'

setjmp = callCC $ (\c -> return $ fold c)
jump l = unfold l l

test :: ContT () IO ()
test = do
    lift $ putStrLn "Start"
    l <- setjmp
    lift $ putStrLn "x"
    jump l

main = runContT test return

我想这就是@augustss所想的。

Answer 3

该示例在ContT () IO monad中执行，Monad允许导致()和一些提升的IO的延续。

type ExM a = ContT () IO a

ContT可能是一个令人难以置信的混乱的单子，但我发现Haskell的等式推理是一个强大的工具来解开它。这个答案的其余部分分几个步骤检查了原始示例，每个步骤都由语法转换和纯重命名提供动力。

因此，让我们首先检查一下callCC部分的类型--它最终是整个代码的核心。该块负责生成一种奇怪的元组，作为其一元值。

type ContAndPrev = (Int -> ExM (), Int)

getContAndPrev :: ExM ContAndPrev
getContAndPrev = callCC $ \k -> let f x = k (f, x) 
                                in return (f, 0)

通过使用(>>=)对其进行分段，可以使它更加熟悉，这正是它在实际环境中使用的方式--任何do-block去用户最终都会为我们创建(>>=)。

withContAndPrev :: (ContAndPrev -> ExM ()) -> ExM ()
withContAndPrev go = getContAndPrev >>= go

最后，我们可以检查它在呼叫站点上的样子。更清楚的是，我将对最初的示例做一些修改

flip runContT return $ do
  lift (putStrLn "alpha")
  withContAndPrev $ \(k, num) -> do
    lift $ putStrLn "beta"
    lift $ putStrLn "gamma"
    if num < 5
      then k (num + 1) >> return ()
      else lift $ print num

请注意，这是一个纯粹的语法转换。代码与原始示例相同，但它强调了withContAndPrev下这个缩进块的存在。这是理解Haskell callCC的秘诀--withContAndPrev可以访问整个“do块的其余部分”，它可以选择如何使用。

让我们忽略withContAndPrev的实际实现，看看是否能够创建我们在运行示例中看到的行为。这是相当棘手的，但我们想要做的是传递到块中调用自己的能力。Haskell是如此的懒惰和递归，我们可以直接编写它。

withContAndPrev' :: (ContAndPrev -> ExM ()) -> ExM ()
withContAndPrev' = go 0 where 
  go n next = next (\i -> go i next, n)

这仍然是一个递归的头痛，但它可能更容易看到它的工作方式。我们将使用do块的其余部分，并创建一个称为go的循环结构。我们将一个函数传递到块中，该函数使用一个新的整数参数调用我们的活套go，并返回前一个整数参数。

通过对原始代码进行更多的语法更改，我们可以开始稍微展开这段代码。

maybeCont :: ContAndPrev -> ExM ()
maybeCont k n | n < 5     = k (num + 1)
              | otherwise = lift (print n)

bg :: ExM ()
bg = lift $ putStrLn "beta" >> putStrLn "gamma"

flip runContT return $ do
  lift (putStrLn "alpha")
  withContAndPrev' $ \(k, num) -> bg >> maybeCont k num

现在，我们可以检查当betaGam >> maybeCont k num被传递到withContAndPrev时是什么样子的。

let go n next = next (\i -> go i next, n)
    next      = \(k, num) -> bg >> maybeCont k num
in
  go 0 next
  (\(k, num) -> betaGam >> maybeCont k num) (\i -> go i next, 0)
  bg >> maybeCont (\i -> go i next) 0
  bg >> (\(k, num) -> betaGam >> maybeCont k num) (\i -> go i next, 1)
  bg >> bg >> maybeCont (\i -> go i next) 1
  bg >> bg >> (\(k, num) -> betaGam >> maybeCont k num) (\i -> go i next, 2)
  bg >> bg >> bg >> maybeCont (\i -> go i next) 2
  bg >> bg >> bg >> bg >> maybeCont (\i -> go i next) 3
  bg >> bg >> bg >> bg >> bg >> maybeCont (\i -> go i next) 4
  bg >> bg >> bg >> bg >> bg >> bg >> maybeCont (\i -> go i next) 5
  bg >> bg >> bg >> bg >> bg >> bg >> lift (print 5)

因此，很明显，我们的假实现重新创建了原始循环的行为。我们的假行为是如何通过使用作为参数的“do块的其余部分”的递归结来实现的，这可能要稍微清楚一些。

有了这些知识，我们可以更深入地了解callCC。我们将再次受益，通过初步检查它的预装订形式。这是非常简单的，如果奇怪，在这种形式。

withCC gen block = callCC gen >>= block
withCC gen block = block (gen block)

换句话说，我们使用callCC，gen的参数来生成callCC的返回值，但是我们将最终应用该值的延续block传递给gen。这是递归跳转，但在含义上是清楚的-callCC确实是“用当前的延续调用这个块”。

withCC (\k -> let f x = k (f, x)
              in  return (f, 0)) next
next (let f x = next (f, x) in return (f, 0))

callCC的实际实现细节更具有挑战性，因为它们要求我们从(callCC >>=)的语义中找到一种定义callCC的方法，但这是不可忽略的。到头来，我们受益于这样一个事实：do块是编写的，这样每一行都得到了与(>>=)绑定的块的其余部分，这提供了一个自然的连续概念。