转到Haskell:任何人都可以解释这种看似疯狂的持续monad使用效果吗？

Question

从这个线程(Control.Monad.Cont fun,2005),Tomasz Zielonka介绍了一个函数(由ThomasJä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被吞噬了.

现在,在"真实世界哈斯克尔"奥沙利文,戈尔岑和斯图尔特说

"堆叠monad变换器类似于组合函数.如果我们改变函数的顺序然后得到不同的结果,我们就不会感到惊讶.所以它也适用于monad变换器." (Real World 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的实例定义(这就是我最近问过这个问题的原因.)

我们添加一个实例离开listen并传递undefined:

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

添加这些行,编译并运行.所有数字都打印出来.

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

Answer 1

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

在第一个例子中,你使用type APP= WriterT [String] (ContT () IO),IO作为基础monad,然后ContT,最后WriterT.因此,当您调用时loop,编写器的状态将解除调用时的状态,getCC'因为ContT编写器位于monad堆栈上方.当您切换ContT和WriterT,现在只能继续解开ContT,因为它是比作家较高的单子.

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被告知价值观,但是当内部ErrorTmonad被运行时,它们都被丢弃了.但是如果我们改变变压器的顺序:

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的内部状态,因为它低于ErrorTmonad堆栈.之间的大的差异ErrorT和ContT是ErrorT的类型清楚地表明,如果错误被抛出的任何部分的计算将被丢弃.

ContT当它位于堆栈的顶部时,它的理由肯定更简单,但有时能够将monad展开到已知点是有用的.例如,可以以这种方式实现一种交易.

Answer 2

我花了一些时间在λ演算中追踪这个.它生成了我不会尝试在这里重现的派生页面和页面,但我确实对monad堆栈的工作方式有了一些了解.您的类型扩展如下:

type APP a = WriterT [String] (ContT () IO) a
           = ContT () IO (a,[String])
           = ((a,[String]) -> IO()) -> IO()

你可以同样扩大了作家return,>>=以及tell与续的一起return,>>=和callCC.追查它是非常乏味的.

调用loop驱动程序的效果是放弃正常的延续,而是再次从调用返回getCC'.放弃的延续包含将当前添加x到列表中的代码.所以相反,我们重复循环,但现在x是下一个数字,并且只有当我们达到最后一个数字(因此不放弃延续)时,我们将列表从["The quick brown fox"]和中拼凑起来["4"].

就像"真实世界Haskell"强调IO monad需要保持在堆栈的底部一样,延续monad仍然保持领先地位似乎也很重要.