Goto in Haskell:谁能解释一下延续 monad 用法的这种看似疯狂的效果? [英] Goto in Haskell: Can anyone explain this seemingly insane effect of continuation monad usage?

问题描述

来自 这个 主题(Control.Monad.Cont fun, 2005)，TomaszZielonka 引入了一个函数(Thomas Jäger 以清晰和友好的方式进行了评论).Tomasz 接受 callCC 主体的参数(一个函数)并返回它以供以后使用，并带有以下两个定义:

From this thread (Control.Monad.Cont fun, 2005), Tomasz Zielonka introduced a function (commented in a clear and nice manner by Thomas Jäger). Tomasz takes the argument (a function) of a callCC body and returns it for later usage with the following two definitions:

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 语义，这看起来非常酷:

Those are also mentioned in Haskellwiki. Using them, you can resemble goto semantics in haskell which looks really cool:

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.

This prints the numbers 0 to 10.

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

Here comes the interesting point. I used this together with the Writer Monad to solve a certain problem. My code looks like the following:

{-# 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

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

When you compile and run this code, the output is:

The quick brown fox ...
4

数字 0 到 3 在这个例子的深邃黑暗中被吞没了.

The numbers zero to three are swallowed somewhere in the profound darkness of this example.

现在，在Real World Haskell"中，O'Sullivan、Goerzen 和 Stewart 状态

Now, in "Real World Haskell" O'Sullivan, Goerzen and Stewart states

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

"Stacking monad transformers is analogous to composing functions. If we change the order in which we apply functions and then get different results, we won't be suprised. So it is with monad transformers, too." (Real World Haskell, 2008, P. 442)

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

I came up with the idea to swap the transformers above:

--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 的实例定义(这就是为什么我最近问 这个问题.)

However, this won't compile because there is no instance definition for MonadWriter in Control.Monad.Cont (which is why I recently asked this question.)

我们添加一个实例，使监听和传递未定义:

We add an instance leaving listen and pass undefined:

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

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

Add those lines, compile and run. All numbers are printed.

在前面的例子中发生了什么?

What has happened in the previous example?

推荐答案

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

Here's a somewhat informal answer, but hopefully useful. getCC' returns a continuation to the current point of execution; you can think of it as saving a stack frame. The continuation returned by getCC' has not only ContT's state at the point of the call, but also the state of any monad above ContT on the stack. When you restore that state by calling the continuation, all of the monads built above ContT return to their state at the point of the getCC' call.

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

In the first example you use type APP= WriterT [String] (ContT () IO), with IO as the base monad, then ContT, and finally WriterT. So when you call loop, the state of the writer is unwound to what it was at the getCC' call because the writer is above ContT on the monad stack. When you switch ContT and WriterT, now the continuation only unwinds the ContT monad because it's higher than the writer.

ContT 并不是唯一会导致此类问题的 monad 转换器.下面是一个与 ErrorT

ContT isn't the only monad transformer that can cause issues like this. Here's an example of a similar situation with 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..."

即使 writer monad 被告知值，当内部 ErrorT monad 运行时，它们都会被丢弃.但是如果我们切换变压器的顺序:

Even though the writer monad was being told values, they're all discarded when the inner ErrorT monad is run. But if we switch the order of the transformers:

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"])

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

Here the internal state of the writer monad is preserved, because it's lower than ErrorT on the monad stack. The big difference between ErrorT and ContT is that ErrorT's type makes it clear that any partial computations will be discarded if an error is thrown.

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

It's definitely simpler to reason about ContT when it's at the top of the stack, but it is on occasion useful to be able to unwind a monad to a known point. A type of transaction could be implemented in this manner, for example.

这篇关于Goto in Haskell:谁能解释一下延续 monad 用法的这种看似疯狂的效果?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！