7

我无法理解上一个问题的答案。我希望对以下内容的解释能够澄清事情。以下示例来自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

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

编辑：考虑Scheme中的类似例子。据我所知，Scheme 不会有问题，对吗？但是为什么呢？

4

4 回答 4

5

正如其他人所写的那样，最后一个示例由于无限类型而没有进行类型检查。

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

您还可以创建一个新类型以将无限（等）递归类型包装成（等）递归新类型。– 2013 年 12 月 12 日 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 的想法。

于 2015-03-20T20:36:34.980 回答
4

以相反的顺序查看您的示例。

由于无限类型，最后一个示例不进行类型检查。看类型callCC，确实是((a -> ContT r m b) -> ContT r m a) -> ContT r m a。如果我们尝试返回延续，我们会返回一些 type ContT r m (a -> ContT r m b)。这意味着我们得到了类型等式约束a ~ (a -> ContT r m b)，这意味着a必须是无限类型。Haskell 不允许这些（通常，有充分的理由 - 据我所知，这里的无限类型将类似于，为其提供无限阶函数作为参数）。

在第二个示例中，您没有提到您是否感到困惑，但是。它不打印“uh oh...”的原因是因为ContT产生的动作k ()，不像许多ContT动作不使用以下计算。这是延续和返回动作的普通函数之间的区别ContT（免责声明，任何函数都可以返回这样的ContT动作，但一般来说）。因此，当您k ()使用 print 或其他任何内容进行后续操作时，它是无关紧要的，因为它k ()只是丢弃了以下操作。

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

我们传递给这个 lambda 的类型callCC是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 绑定在传递给的 lambda 中创建一些递归callCC，您可以避免这种情况。

于 2013-12-12T11:28:21.107 回答
1

该示例在ContT () IOmonad 中执行，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，但是我们传递到我们最终将值应用到gen的那个延续中。block它是递归的，但在含义上很清楚——<code>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写入块以便每一行都将块的其余部分绑定到它上面，(>>=)这提供了一个自然的连续概念。

于 2013-12-12T14:22:53.410 回答
0

为什么有必要在 callCC 中有一个 let 表达式来“返回”延续，以便以后可以使用它

这就是延续的确切用法，即捕获当前执行上下文，然后稍后使用此捕获延续跳回该执行上下文。

您似乎对函数名称感到困惑callCC，这可能向您表明它正在调用一个延续，但实际上它正在创建一个延续。

于 2013-12-12T07:21:01.910 回答