Pause monad

Question

Monads可以做许多惊人的,疯狂的事情.他们可以创建具有值叠加的变量.它们可以允许您在计算之前访问未来的数据.它们可以让您编写破坏性更新,但不是真的.然后延续monad让你打破人们的思想!通常是你自己的.;-)

但这是一个挑战:你能制作一个可以暂停的单子吗？

data Pause s x
instance Monad (Pause s)
mutate :: (s -> s) -> Pause s ()
yield :: Pause s ()
step :: s -> Pause s () -> (s, Maybe (Pause s ()))

该Pause单子是一种状态的单子(因此mutate,具有明显的语义).通常情况下,像这样的monad具有某种"运行"功能,它运行计算并将您送回最终状态.但Pause它是不同的:它提供了一个step函数,它运行计算直到它调用魔法yield函数.这里计算暂停,返回给调用者足够的信息以便稍后恢复计算.

额外的awesomne​​ss:允许调用者修改step调用之间的状态.(例如,上面的类型签名应该允许这样做.)

---

使用案例:编写执行复杂操作的代码通常很容易,但是要将其转换为也在其操作中输出中间状态的总PITA .如果您希望用户能够在执行过程中途改变某些内容,那么事情变得非常复杂.

实施思路:

• 显然它可以用线程,锁和IO.但我们能做得更好吗？;-)

• 继续monad疯狂的东西？

• 也许是某种编写器monad,yield只记录当前状态,然后我们可以step通过迭代日志中的状态来"假装" 它.(显然这排除了改变步骤之间的状态,因为我们现在并没有真正"暂停"任何东西.)

Answer 1

注意:您没有直接访问s此monad中的当前状态.

Pause s只是一个免费的monad mutate和yield操作.直接实施你得到:

data Pause s a
  = Return a
  | Mutate (s -> s) (Pause s a)
  | Yield (Pause s a)

instance Monad (Pause s) where
  return = Return
  Return a   >>= k = k a
  Mutate f p >>= k = Mutate f (p >>= k)
  Yield p    >>= k = Yield (p >>= k)

使用几个智能构造函数为您提供所需的API:

mutate :: (s -> s) -> Pause s ()
mutate f = Mutate f (return ())

yield :: Pause s ()
yield = Yield (return ())

以及驱动它的步骤功能

step :: s -> Pause s () -> (s, Maybe (Pause s ()))
step s (Mutate f k) = step (f s) k
step s (Return ()) = (s, Nothing)
step s (Yield k) = (s, Just k)

您也可以直接使用来定义它

data Free f a = Pure a | Free (f (Free f a))

(来自我的'免费'套餐)

data Op s a = Mutate (s -> s) a | Yield a

然后我们已经有一个Pause monad

type Pause s = Free (Op s)

并且只需要定义智能构造函数和步进器.

让它更快.

现在,这些实现很容易推理,但它们没有最快的操作模型.特别是,(>> =)的左关联用法产生渐近较慢的代码.

为了解决这个问题,您可以将Codensity monad应用于现有的免费monad,或者直接使用'Church free'monad,我在博客中深入介绍了这两种方法.

http://comonad.com/reader/2011/free-monads-for-less/

http://comonad.com/reader/2011/free-monads-for-less-2/

http://comonad.com/reader/2011/free-monads-for-less-3/

应用Free monad的Church编码版本的结果是,您可以轻松地推断出数据类型的模型,并且您仍然可以获得快速评估模型.

Answer 2

当然; 你只是让任何计算结果,或者暂停自己,给出一个在恢复时使用的动作,以及当时的状态:

data Pause s a = Pause { runPause :: s -> (PauseResult s a, s) }

data PauseResult s a
    = Done a
    | Suspend (Pause s a)

instance Monad (Pause s) where
    return a = Pause (\s -> (Done a, s))
    m >>= k = Pause $ \s ->
        case runPause m s of
            (Done a, s') -> runPause (k a) s'
            (Suspend m', s') -> (Suspend (m' >>= k), s')

get :: Pause s s
get = Pause (\s -> (Done s, s))

put :: s -> Pause s ()
put s = Pause (\_ -> (Done (), s))

yield :: Pause s ()
yield = Pause (\s -> (Suspend (return ()), s))

step :: Pause s () -> s -> (Maybe (Pause s ()), s)
step m s =
    case runPause m s of
        (Done _, s') -> (Nothing, s')
        (Suspend m', s') -> (Just m', s')

该Monad实例就是序列以正常的方式外,通过最终的结果到k延续,或将计算的其余部分上悬挂完成.

Answer 3

这是我如何使用免费 monad进行的.呃,嗯,他们是什么？它们是树木,在节点处有动作,在树叶处有值,>>=表现得像树木嫁接.

data f :^* x
  = Ret x
  | Do (f (f :^* x))

在数学中为这样的东西写F ^* X 并不罕见,因此我的胡思乱想的中缀类型名称.要创建一个实例,你只需要f成为可以映射的东西:任何人Functor都可以.

instance Functor f => Monad ((:^*) f) where
  return = Ret
  Ret x  >>= k  = k x
  Do ffx >>= k  = Do (fmap (>>= k) ffx)

这只是"适用k于所有的树叶和移植到最终的树木".这些树可以代表交互式计算的策略:整个树覆盖与环境的每个可能的交互,并且环境选择树中要遵循的路径.他们为什么要自由？它们只是树木,没有关于它们的有趣的等式理论,说哪些策略等同于其他策略.

现在让我们有一个用于制作Functors的工具包,它们对应于我们可能希望能够执行的一系列命令.这东西

data (:>>:) s t x = s :? (t -> x)

instance Functor (s :>>: t) where
  fmap k (s :? f) = s :? (k . f)

捕获在输入类型和输出类型的一个命令x之后获取值的想法.要做到这一点,你需要选择一个输入并解释如何在给定命令输出的情况下继续输入值.要在这样的事物中映射函数,请将其添加到延续中.到目前为止,标准设备.对于我们的问题,我们现在可以定义两个仿函数:stsxt

type Modify s  = (s -> s) :>>: ()
type Yield     = () :>>: ()

就像我刚刚写下了我们希望能够执行的命令的值类型!

现在让我们确保我们可以在这些命令之间做出选择.我们可以证明,仿函数之间的选择产生了一个仿函数.更标准的设备.

data (:+:) f g x = L (f x) | R (g x)

instance (Functor f, Functor g) => Functor (f :+: g) where
  fmap k (L fx) = L (fmap k fx)
  fmap k (R gx) = R (fmap k gx)

因此,Modify s :+: Yield代表了修改和屈服之间的选择.任何简单命令的签名(以值而不是操纵计算与世界通信)都可以通过这种方式变成仿函数.我不得不亲手做到这一点!

这给了我你的monad:免费monad超过修改和收益的签名.

type Pause s = (:^*) (Modify s :+: Yield)

我可以将modify和yield命令定义为one-do-then-return.除了协商虚拟输入之外yield,这只是机械的.

mutate :: (s -> s) -> Pause s ()
mutate f = Do (L (f :? Ret))

yield :: Pause s ()
yield = Do (R (() :? Ret))

step然后,该函数赋予策略树的含义.它是一个控制操作符,从另一个构建一个计算(可能).

step :: s -> Pause s () -> (s, Maybe (Pause s ()))
step s (Ret ())            = (s, Nothing)
step s (Do (L (f  :? k)))  = step (f s) (k ())
step s (Do (R (() :? k)))  = (s, Just (k ()))

该step函数运行策略,直到它完成a Ret,或者它产生,随着状态变化状态.

一般方法如下:将命令(根据值进行交互)与控制操作符分开(操作计算); 在命令的签名上构建免费的"策略树"单元(摇动手柄); 通过策略树的递归来实现控制操作符.

Answer 4

与您的类型签名完全不符,但肯定很简单:

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, UndecidableInstances #-}
import Control.Monad.State

newtype ContinuableT m a = Continuable { runContinuable :: m (Either a (ContinuableT m a)) }
instance Monad m => Monad (ContinuableT m) where
    return = Continuable . return . Left
    Continuable m >>= f = Continuable $ do
        v <- m
        case v of
            Left  a -> runContinuable (f a)
            Right b -> return (Right (b >>= f))

instance MonadTrans ContinuableT where
    lift m = Continuable (liftM Left m)

instance MonadState s m => MonadState s (ContinuableT m) where
    get = lift get
    put = lift . put

yield :: Monad m => ContinuableT m a -> ContinuableT m a
yield = Continuable . return . Right

step :: ContinuableT (State s) a -> s -> (Either a (ContinuableT (State s) a), s)
step = runState . runContinuable

-- mutate unnecessary, just use modify

Answer 5

{-# LANGUAGE TupleSections #-}
newtype Pause s x = Pause (s -> (s, Either x (Pause s x)))

instance Monad (Pause s) where
  return x = Pause (, Left x)

  Pause k >>= f = Pause $ \s -> let (s', v) = k s in
                                case v of
                                  Left x -> step (f x) s'
                                  Right x -> (s', Right (x >>= f))

mutate :: (s -> s) -> Pause s ()
mutate f = Pause (\s -> (f s, Left ()))

yield :: Pause s ()
yield = Pause (, Right (return ()))

step :: Pause s x -> s -> (s, Either x (Pause s x))
step (Pause x) = x

这就是我写这个的方式.我给出step了一些更一般的定义,它可以命名runPause.实际上在思考step导致我的定义类型Pause.

在monad-coroutine包中你会发现一个普通的monad变压器.该Pause s单子是一样的Coroutine (State s) Id.您可以将协同程序与其他monad结合使用.

相关:http://themonadreader.files.wordpress.com/2010/01/issue15.pdf中的提示单子

Answer 6

注意:这个答案是可以作为一个有文化的Haskell文件的要点.

我非常喜欢这个练习.我试着这样做而没有看到答案,这是值得的.这花了我相当长的时间,但结果令人惊讶地接近其他两个答案,以及monad-coroutine库.所以我想这是解决这个问题的一种自然方式.没有这个练习,我不明白monad-coroutine是如何工作的.

为了增加一些额外的价值,我将解释最终导致我解决方案的步骤.

认识到州的monad

由于我们正在处理状态,因此我们寻找可以由状态monad有效描述的模式.特别s - s是s -> (s, ()),它是同构的,所以它可以被替换State s ().并且s -> x -> (s, y)可以翻转类型的功能,x -> (s -> (s, y))实际上x -> State s y.这导致我们更新签名

mutate :: State s () -    Pause s ()
step   :: Pause s () -    State s (Maybe (Pause s ()))

概括

我们的Pausemonad目前由州政府参与.但是,现在我们看到我们并不需要任何状态,也不会使用状态monad的任何细节.所以我们可以尝试制作一个由任何monad参数化的更通用的解决方案:

mutate :: (Monad m) =    m () -> Pause m ()
yield  :: (Monad m) =    Pause m ()
step   :: (Monad m) =    Pause m () -> m (Maybe (Pause m ()))

此外,我们还可以尝试做mutate并step允许任何类型的值更普遍,而不仅仅是().通过认识到这Maybe a是同构的,Either a ()我们可以最终将我们的签名概括为

mutate :: (Monad m) =    m a -> Pause m a
yield  :: (Monad m) =    Pause m ()
step   :: (Monad m) =    Pause m a -> m (Either (Pause m a) a)

这样就step返回了计算的中间值.

Monad变压器

现在,我们看到我们实际上正试图从monad中创建一个monad - 添加一些额外的功能.这就是通常所说的monad变压器.此外,mutate的签名是完全一样的电梯从MonadTrans.最有可能的是,我们正走在正确的轨道上.

最后的单子

该step函数似乎是我们monad中最重要的部分,它定义了我们需要的东西.也许,这可能是新的数据结构？我们试试吧:

import Control.Monad
import Control.Monad.Cont
import Control.Monad.State
import Control.Monad.Trans

data Pause m a
    = Pause { step :: m (Either (Pause m a) a) }

如果该Either部分是Right,它只是一个monadic值,没有任何暂停.这导致我们如何实现简单的事情 - lift 来自MonadTrans以下的功能:

instance MonadTrans Pause where
    lift k = Pause (liftM Right k)

而且mutate只是一个专业化:

mutate :: (Monad m) => m () -> Pause m ()
mutate = lift

如果该Either部分是Left,它表示暂停后的继续计算.那么让我们为此创建一个函数:

suspend :: (Monad m) => Pause m a -> Pause m a
suspend = Pause . return . Left

现在yield计算很简单,我们只是暂停一个空计算:

yield :: (Monad m) => Pause m ()
yield = suspend (return ())

尽管如此,我们仍然缺少最重要的部分.该Monad实例.我们来解决它.实施return很简单,我们只是解除内在的monad.实施>>=有点棘手.如果原始Pause值只是一个简单的值(Right y),那么我们只需将其f y作为结果包装.如果它是一个可以继续(Left p)的暂停计算,我们递归地下降到它.

instance (Monad m) => Monad (Pause m) where
    return x = lift (return x) -- Pause (return (Right x))
    (Pause s) >>= f
        = Pause $ s >>= \x -> case x of
            Right y     -> step (f y)
            Left p      -> return (Left (p >>= f))

测试

让我们尝试制作一些使用和更新状态的模型函数,在计算内部产生:

test1 :: Int -> Pause (State Int) Int
test1 y = do
            x <- lift get
            lift $ put (x * 2)
            yield
            return (y + x)

调试monad的辅助函数 - 将其中间步骤打印到控制台:

debug :: Show s => s -> Pause (State s) a -> IO (s, a)
debug s p = case runState (step p) s of
                (Left next, s')     ->  print s' >> debug s' next
                (Right r, s')       ->  return (s', r)    

main :: IO ()
main = do
    debug 1000 (test1 1 >>= test1 >>= test1) >>= print

结果是

2000
4000
8000
(8000,7001)

正如所料.

协同程序和monad-coroutine

我们实现的是一个非常通用的monadic解决方案,它实现了Coroutines.也许并不奇怪,有人有这个想法:-),并创建了monad-coroutine包.不足为奇的是,它与我们创造的非常相似.

该软件包进一步概括了这一想法.持续计算存储在任意仿函数中.这允许暂停许多变化如何使用暂停的计算.例如,要将值传递给resume(我们调用step)的调用者,或者等待提供值继续,等等.