haskell - Haskell 中的 Goto : Can anyone explain this seemingly insane effect of continuation monad usage?

Question

来自this线程(Control.Monad.Cont fun，2005)，Tomasz Zielonka 引入了一个函数(Thomas Jäger 以清晰而漂亮的方式进行了评论)。 Tomasz 获取 callCC 主体的参数(函数)并将其返回以供以后使用，并具有以下两个定义:

import Control.Monad.Cont
...
getCC :: MonadCont m => m (m a)
getCC = callCC (\c -> let x = c x in return x)

getCC' :: MonadCont m => a -> m (a, a -> m b)
getCC' x0 = callCC (\c -> let f x = c (x, f) in return (x0, f))

Haskellwiki中也提到了这些。使用它们，您可以类似于 haskell 中的 goto 语义，这看起来非常酷:

import Control.Monad.Cont

getCC' :: MonadCont m => a -> m (a, a -> m b)
getCC' x0 = callCC (\c -> let f x = c (x, f) in return (x0, f))

main :: IO ()
main = (`runContT` return) $ do
    (x, loopBack) <- getCC' 0
    lift (print x)
    when (x < 10) (loopBack (x + 1))
    lift (putStrLn "finish")

这将打印数字 0 到 10。

有趣的一点来了。我将它与 Writer Monad 一起使用来解决某个问题。我的代码如下所示:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, UndecidableInstances #-}

import Control.Monad.Cont
import Control.Monad.Writer

getCC :: MonadCont m => m (m a)
getCC = callCC (\c -> let x = c x in return x)

getCC' :: MonadCont m => a -> m (a, a -> m b)
getCC' x0 = callCC (\c -> let f x = c (x, f) in return (x0, f))

-- a simple monad transformer stack involving MonadCont and MonadWriter
type APP= WriterT [String] (ContT () IO)

runAPP :: APP a -> IO ()
runAPP a= runContT (runWriterT a) process
      where process (_,w)= do
               putStrLn $ unlines w
               return ()

driver :: Int -> APP ()
driver k = do
   tell [ "The quick brown fox ..." ]
   (x,loop) <- getCC' 0
   collect x
   when (x<k) $ loop (x+1) 

collect :: Int -> APP ()
collect n= tell [ (show n) ] 

main :: IO ()
main = do
   runAPP $ driver 4

编译并运行此代码时，输​​出为:

The quick brown fox ...
4

数字 0 到 3 被吞没在这个例子的黑暗中的某个地方。

现在，在“现实世界 haskell ”奥沙利文、戈尔岑和斯图尔特状态

“堆叠 monad 转换器类似于组合函数。如果我们改变应用函数的顺序，然后得到不同的结果，我们不会感到惊讶。monad 转换器也是如此。”(现实世界 Haskell，2008 年，第 442 页)

我想出了交换上面变压器的想法:

--replace in the above example
type APP= ContT () (WriterT [String] IO)
...
runAPP a = do
    (_,w) <- runWriterT $ runContT a (return . const ())
    putStrLn $ unlines w

但是，这不会编译，因为 Control.Monad.Cont 中没有 MonadWriter 的实例定义(这就是我最近询问 this question 的原因。)

我们添加一个实例，离开监听并传递未定义的:

instance (MonadWriter w m) => MonadWriter w (ContT r m) where
  tell = lift . tell
  listen = undefined
  pass = undefined

添加这些行，编译并运行。所有数字均被打印。

前面的示例发生了什么？

Answer 1

这是一个有点非正式的答案，但希望有用。 getCC' 返回当前执行点的延续；您可以将其视为保存堆栈帧。 getCC' 返回的延续不仅具有调用时 ContT 的状态，还具有 ContT 之上任何 monad 的状态在堆栈上。当您通过调用延续来恢复该状态时，在 ContT 之上构建的所有 monad 都会返回到 getCC' 调用时的状态。

在第一个示例中，您使用 type APP= WriterT [String] (ContT () IO)，以 IO 作为基本 monad，然后 ContT，最后是WriterT。因此，当您调用 loop 时，写入器的状态将恢复为 getCC' 调用时的状态，因为写入器位于 ContT 之上单子(monad)栈。当您切换 ContT 和 WriterT 时，现在延续只会展开 ContT monad，因为它比 writer 更高。

ContT 并不是唯一可能导致此类问题的 monad 转换器。下面是 ErrorT

类似情况的示例

func :: Int -> WriterT [String] (ErrorT String IO) Int
func x = do
  liftIO $ print "start loop"
  tell [show x]
  if x < 4 then func (x+1)
    else throwError "aborted..."

*Main> runErrorT $ runWriterT $ func 0
"start loop"
"start loop"
"start loop"
"start loop"
"start loop"
Left "aborted..."

尽管编写器 monad 被告知了值，但当内部 ErrorT monad 运行时，它们都会被丢弃。但是如果我们交换变压器的顺序:

switch :: Int -> ErrorT String (WriterT [String] IO) () 
switch x = do
  liftIO $ print "start loop"
  tell [show x]
  if x < 4 then switch (x+1)
    else throwError "aborted..."

*Main> runWriterT $ runErrorT $ switch 0
"start loop"
"start loop"
"start loop"
"start loop"
"start loop"
(Left "aborted...",["0","1","2","3","4"])

这里保留了编写器 monad 的内部状态，因为它低于 monad 堆栈上的 ErrorT 。 ErrorT 和 ContT 之间的最大区别在于，ErrorT 的类型清楚地表明，如果抛出错误，任何部分计算都将被丢弃。

当 ContT 位于堆栈顶部时，推理它肯定更简单，但有时能够将 monad 展开到已知点很有用。例如，一种交易可以通过这种方式实现。