了解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

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

编辑:考虑Scheme中的分析示例.据我所知,Scheme不会有问题,这是正确的吗？,但为什么呢？

Answer 1

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

@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 的想法。

Answer 2

反过来看你的例子。

由于无限类型，最后一个示例不进行类型检查。看类型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 ()不同，不使用以下计算。这是延续函数和返回操作的普通函数之间的区别（免责声明，任何函数都可以返回这样的操作，但一般来说）。因此，当您通过打印或其他任何内容跟进时，这是无关紧要的，因为它只是丢弃以下操作。ContTContTContTk ()k ()

那么，第一个例子。这里的 let 绑定实际上只是用来搞乱 的参数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，可以避免这种情况。