暂停单子

Monads 可以做很多惊人的疯狂的事情。它们可以创建包含叠加值的变量。它们允许您在计算未来之前访问未来的数据。他们可以让你写破坏性的更新，但不是真的。然后继续单子允许你 摧毁人们的思想！通常是你自己的。;-)

但是这里有一个挑战: 你能制造一个单子，它可以是 停顿了一下吗？

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具有明显的语义)。通常，这样的单子有某种“ run”函数，它运行计算并返回最终状态。但是 Pause不同: 它提供了一个 step函数，该函数运行计算直到调用神奇的 yield函数。这里暂停计算，将足够的信息返回给调用方，以便稍后恢复计算。

为了获得更好的效果: 允许调用方修改 step调用之间的状态。(例如，上面的类型签名应该允许这样做。)

用例: 编写执行复杂操作的代码通常很容易，但是要将其转换为操作中的中间状态 输出，则需要一个完整的 PITA。如果您希望用户能够在执行过程中使用 改变，那么事情会变得非常复杂。

实施构思:

  • 显然， 可以通过线程、锁和 IO来完成。但是我们能做得更好吗? ; -)

  • 有什么疯狂的事情吗？

  • 也许是某种编写器单子，其中 yield只记录当前状态，然后我们可以通过迭代日志中的状态来“假装”step。(很明显，这就排除了在步骤之间改变状态的可能性，因为我们现在并没有真正“暂停”任何事情。)

6203 次浏览
小开
最佳答案

当然可以; 您只需让任何计算以结果结束，或者挂起自身，给出一个操作以便在恢复时使用，以及当时的状态:

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延续，或者添加在悬挂时要完成的其余计算。

小开 
{-# 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的定义。

在 ABc2软件包中，你可以找到一个通用的 monad transformer。Pause s单子与 Coroutine (State s) Id单子相同。您可以将 coroutine 与其他单子结合起来。

相关阅读: http://themonadreader.files.wordpress.com/2010/01/issue15.pdf中的 Prompt monad

小开

注意: 您没有为自己提供对这个 monad 中当前状态 s的直接访问。

Pause s只是 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

那么我们已经有了一个单子暂停

type Pause s = Free (Op s)

只需要定义智能构造函数和步进器。

让它更快。

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

为了解决这个问题，您可以将 密度 monad 应用到现有的免费 monad 上，或者直接使用 “免费教堂” 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/

应用 Church 编码版本的 Free 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应用于所有的叶子，并嫁接到所产生的树木”。这些树可以代表交互计算的 策略: 整个树覆盖与环境的每个可能的交互，环境选择树中的路径。为什么是 自由？它们只是树，没有有趣的等式理论，说明哪些策略和哪些策略是等价的。

现在，让我们有一个工具包来创建函数，它对应于我们可能希望能够执行的一系列命令。这东西

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


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

捕获在 一命令之后获取 x值的想法，输入类型为 s，输出类型为 t。为此，您需要在 s中选择一个输入，并解释如何根据 t中的命令输出继续到 x中的值。要将函数映射到这样的事物上，您可以将其附加到延续中。到目前为止，都是标准设备。对于我们的问题，我们现在可以定义两个函数:

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代表了修正和收益之间的选择。任何简单命令的 签名(通过值而不是操纵计算与世界进行通信)都可以通过这种方式转换为函数。我不得不用手做这件事，真是麻烦！

这就给了我你的单子: 自由单子上的修改和收益的签名。

type Pause s = (:^*) (Modify s :+: 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函数运行该策略，直到使用 Ret结束运行，或者在运行过程中产生状态突变。

通常的方法是这样的: 从 控制操作员(操作计算)中分离出 命令(以值的形式进行交互) ; 在命令的签名上构建“策略树”的自由单子(转动句柄) ; 通过在策略树上递归实现控制操作符。

小开

不完全匹配您的类型签名，但肯定很简单:

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

注意: 这个答案是 有空，它是 Gist 上的一个有文化的 Haskell 文件。

我很喜欢这个练习。我试着不去看答案，这是值得的。这花了我相当长的时间，但结果是惊人地接近其他两个答案，以及 单子-协同程序库。所以我想这是这个问题的自然解决方案。如果没有这个练习，我就不会理解 单子-协同程序到底是如何工作的。

为了增加一些额外的价值，我将解释最终引导我找到解决方案的步骤。

识别州单子

因为我们处理的是状态，所以我们寻找能够被状态单子有效描述的模式。特别是，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 ()))

概括

我们的 Pause单子当前由状态参数化。然而，现在我们看到，我们实际上并不需要状态来做任何事情，我们也不使用状态单子的任何细节。因此，我们可以尝试做出一个更一般的解决方案，是参数化的任何单子:

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 transformer

现在，我们看到我们实际上正在尝试从一个单子变成一个单子-添加一些额外的功能。这就是通常所说的 monad transformer。此外，mutate的签名与 MonadTrans的 抬起来完全相同。很有可能，我们的方向是对的。

最后一个单子

step函数似乎是我们单子中最重要的部分，它定义了我们所需要的。也许，这就是新的数据结构？让我们试试:

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，那么它只是一个一进制值，没有任何值 这就引导我们如何实现简单的事情-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

现在，yield0计算非常简单，我们只需用一个空值暂停 计算:

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

不过，我们还是漏掉了最重要的部分: Monad实例 它。实现 return很简单，我们只需提升内部单子。实现 >>=有点棘手。如果原始的 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)

不出所料。

协同程序和 单子-协同程序

我们实现的是一个非常通用的实现 协奏曲的一进制解决方案。也许不足为奇，有人以前就有这个想法: ——) ，并创建了 单子-协同程序软件包。不足为奇的是，它和我们创造的非常相似。

这个方案进一步概括了这个想法。连续的计算存储在一个任意的函数中。这使得 停职可以使用许多变体来处理挂起的计算。例如，到 传递一个值到 简历的调用者(我们称之为 step) ，或到 等待一个值被提供以继续，等等。


提交答案