暂停monad
Monads可以做许多惊人的，疯狂的事情。 他们可以创buildvariables来保存值的叠加。 在计算之前，它们可以让您访问未来的数据。 他们可以让你写破坏性的更新，但不是真的。 然后继续monad让你打破人心！ 通常你自己的。 😉
但是，这是一个挑战：你能制造一个可以暂停的monad吗？
数据暂停sx 实例Monad（暂停） mutate ::（s - > s） - >暂停s（） yield :: Pause s（） step :: s - > Pause s（） - >（s，Maybe（Pause s（）））
Pause monad是一种状态monad（因此mutate ，明显的语义）。 通常像这样的monad具有某种“运行”function，它运行计算并将您返回到最终状态。 但Pause是不同的：它提供了一个step函数，它运行计算，直到它调用魔术yield函数。 这里的计算暂停，返回给调用者足够的信息以稍后恢复计算。
对于额外的awesomness：允许调用者修改step之间的状态。 （例如上面的types签名应该允许这样做。）
用例：编写复杂的代码通常很容易，但总的PITA将其转换为在其操作中也输出中间状态。 如果你希望用户能够通过执行中途改变某些事情，事情变得非常复杂。
实施思路：
-
显然可以通过线程，锁和
IO来完成。 但是我们可以做得更好吗？ 😉 -
疯狂的继续单子吗？
-
也许某种作家monad，
yield只是logging当前状态，然后我们可以通过遍历日志中的状态来“伪装”来step它。 （显然，这排除了改变步骤之间的状态，因为现在我们并不真正“暂停”任何东西。）
当然; 你只要让任何一个计算结果结束，或暂停自己，给予一个行动，用于恢复，以及当时的状态：
data Pause sa = Pause { runPause :: s -> (PauseResult sa, s) } data PauseResult sa = Done a | Suspend (Pause sa) instance Monad (Pause s) where return a = Pause (\s -> (Done a, s)) m >>= k = Pause $ \s -> case runPause ms of (Done a, s') -> runPause (ka) s' (Suspend m', s') -> (Suspend (m' >>= k), s') get :: Pause ss 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 ms = case runPause ms of (Done _, s') -> (Nothing, s') (Suspend m', s') -> (Just m', s')
Monad实例只是以正常的方式对事物进行sorting，将最终的结果传递给k延续，或者添加其余的计算来完成暂停。
注意：你自己没有直接访问这个monad中的当前状态。
Pause s只是一个免费的monad而不是mutate和yield操作。 直接执行你会得到：
data Pause sa = Return a | Mutate (s -> s) (Pause sa) | Yield (Pause sa) instance Monad (Pause s) where return = Return Return a >>= k = ka Mutate fp >>= 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 ())
和步进function来驱动它
step :: s -> Pause s () -> (s, Maybe (Pause s ())) step s (Mutate fk) = step (fs) k step s (Return ()) = (s, Nothing) step s (Yield k) = (s, Just k)
你也可以直接使用
data Free fa = Pure a | Free (f (Free fa))
（从我的'免费'包）与
data Op sa = Mutate (s -> s) a | Yield a
那么我们已经有一个monad的暂停
type Pause s = Free (Op s)
只需要定义智能构造函数和步进器。
使其更快。
现在，这些实现很容易推理，但他们没有最快的操作模式。 特别是，（>> =）的左边关联使用产生渐近较慢的代码。
为了解决这个问题，你可以将Codensity monad应用到你现有的免费monad上，或者直接使用“Church of 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编码版本的结果是，您可以很容易地推断出数据types的模型，并且您仍然可以获得快速的评估模型。
这是我如何去使用免费的单子。 呃，他们是什么？ 他们是树上的节点和价值观在树叶，与>>=像树移植行事。
data f :^* x = Ret x | Do (f (f :^* x))
在math中为这样的事物写F * X并不罕见，因此我的胡思乱想的中缀式名字。 做一个实例，你只需要f就可以映射出来：任何Functor都可以做。
instance Functor f => Monad ((:^*) f) where return = Ret Ret x >>= k = kx Do ffx >>= k = Do (fmap (>>= k) ffx)
这只是“在所有的叶子上施加k ，并在所得到的树木中移植”。 这些树可以代表交互式计算的策略 ：整个树覆盖了与环境的每一个可能的交互，并且环境select树中的哪条path遵循。 他们为什么免费 ？ 他们只是树木，没有什么有趣的均衡理论，说哪些策略等同于哪些策略。
现在让我们有一个工具箱来制作Functor，它对应于我们可能想要做的一堆命令。 这东西
data (:>>:) stx = s :? (t -> x) instance Functor (s :>>: t) where fmap k (s :? f) = s :? (k . f)
捕获了在inputtypes为s和输出types为t 一个命令后获得x值的想法。 要做到这一点，你需要在sselect一个input，并解释如何在t输出命令的输出来继续x的值。 为了在这样的事物上映射一个函数，可以将它应用到这个延续上。 到目前为止，标准设备。 对于我们的问题，我们现在可以定义两个函子：
type Modify s = (s -> s) :>>: () type Yield = () :>>: ()
这就像我刚刚写下了我们希望能够执行的命令的值types！
现在让我们确保我们可以提供这些命令之间的select 。 我们可以certificate函数之间的select会产生函子。 更标准的设备。
data (:+:) fgx = L (fx) | R (gx) 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表示修改和产出之间的select。 简单命令的任何签名 （通过值而不是操作计算与世界通信）都可以通过这种方式变成函子。 这是一个麻烦，我必须手工做！
这给了我你的monad：修改和收益签名的免费monad。
type Pause s = (:^*) (Modify s :+: Yield)
我可以把修改和yield命令定义为一个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 (fs) (k ()) step s (Do (R (() :? k))) = (s, Just (k ()))
step函数运行该策略，直到它以Ret完成，或者产生，随着状态的变化而变化。
一般的方法是这样的：从控制操作符 （操作计算）中分离命令 （根据值交互）; 通过命令的签名构build“战略树”的免费monad（启动句柄）; 在策略树上recursion实现控制操作符。
不完全匹配您的types签名，但肯定很简单：
{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, UndecidableInstances #-} import Control.Monad.State newtype ContinuableT ma = Continuable { runContinuable :: m (Either a (ContinuableT ma)) } instance Monad m => Monad (ContinuableT m) where return = Continuable . return . Left Continuable m >>= f = Continuable $ do v <- m case v of Left a -> runContinuable (fa) Right b -> return (Right (b >>= f)) instance MonadTrans ContinuableT where lift m = Continuable (liftM Left m) instance MonadState sm => MonadState s (ContinuableT m) where get = lift get put = lift . put yield :: Monad m => ContinuableT ma -> ContinuableT ma 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
{-# LANGUAGE TupleSections #-} newtype Pause sx = Pause (s -> (s, Either x (Pause sx))) instance Monad (Pause s) where return x = Pause (, Left x) Pause k >>= f = Pause $ \s -> let (s', v) = ks in case v of Left x -> step (fx) s' Right x -> (s', Right (x >>= f)) mutate :: (s -> s) -> Pause s () mutate f = Pause (\s -> (fs, Left ())) yield :: Pause s () yield = Pause (, Right (return ())) step :: Pause sx -> s -> (s, Either x (Pause sx)) step (Pause x) = x
我就是这样写的。 我给出了一些更一般的定义，可以命名为runPause 。 实际上考虑steptypes导致我定义Pause 。
在monad-coroutine软件包中，您将find一个通用monad变压器。 Pause s monad与Coroutine (State s) Id 。 你可以把协程和其他monad结合起来。
相关： http ://themonadreader.files.wordpress.com/2010/01/issue15.pdf中的提示单子
注意：这个答案在Gist中是一个有识字的Haskell文件。
我很喜欢这个练习。 我试图做到这一点，没有看到答案，这是值得的。 这花了我相当长的时间，但结果令人惊讶地接近其他两个答案，以及monad-coroutine库。 所以我想这是对这个问题的自然解决scheme。 没有这个练习，我不会理解monad-coroutine是如何工作的。
为了增加一些额外的价值，我将解释最终导致我的解决scheme的步骤。
认识到国家单子
由于我们正在处理国家，我们寻找可以由国家monad有效描述的模式。 特别是， s - s与s -> (s, ())是同构s -> (s, ()) ，所以它可以被State s ()取代。 并且typess -> x -> (s, y)函数可以被翻转为x -> (s -> (s, y)) ，这实际上是x -> State sy 。 这导致我们更新签名
mutate :: State s () - Pause s () step :: Pause s () - State s (Maybe (Pause s ()))
概括
Pause monad目前是由状态参数化的。 但是，现在我们看到，我们并不真的需要任何东西，也没有使用任何国家单子的细节。 所以我们可以试着制定一个更通用的解决scheme，通过任何monad参数化：
mutate :: (Monad m) = m () -> Pause m () yield :: (Monad m) = Pause m () step :: (Monad m) = Pause m () -> m (Maybe (Pause m ()))
另外，我们可以尝试通过允许任何types的值（而不仅仅是()来进行mutate和更一般化。 而且通过认识到Maybe a同构于Either a ()我们终于可以概括我们的签名
mutate :: (Monad m) = ma -> Pause ma yield :: (Monad m) = Pause m () step :: (Monad m) = Pause ma -> m (Either (Pause ma) a)
使step返回计算的中间值。
Monad变压器
现在，我们看到我们实际上正在尝试从monad中创build一个monad – 添加一些额外的function。 这就是通常所说的monad变压器 。 而且， mutate的签名与MonadTrans 提升完全一样。 最有可能的是，我们正在走上正轨。
最后的monad
step函数似乎是monad中最重要的部分，它定义了我们需要的东西。 也许，这可能是新的数据结构？ 咱们试试吧：
import Control.Monad import Control.Monad.Cont import Control.Monad.State import Control.Monad.Trans data Pause ma = Pause { step :: m (Either (Pause ma) a) }
如果Either部分都是Right ，那么这只是一个单值，没有任何暂停。 这导致我们如何实现简单的东西 – MonadTrans的liftfunction：
instance MonadTrans Pause where lift k = Pause (liftM Right k)
而mutate只是一个专业化：
mutate :: (Monad m) => m () -> Pause m () mutate = lift
如果Either一部分是Left ，则表示暂停后的继续计算。 所以我们来创build一个函数：
suspend :: (Monad m) => Pause ma -> Pause ma suspend = Pause . return . Left
现在yield一个计算很简单，我们暂停一个空的计算：
yield :: (Monad m) => Pause m () yield = suspend (return ())
不过，我们却错过了最重要的部分。 Monad实例。 我们来修复它。 实现return很简单，我们只是解除内部monad。 实现>>=有点棘手。 如果原来的Pause值只是一个简单的值（ Right y ），那么我们只是把fy结果。 如果它是一个可以继续的暂停计算（ Left p ），我们recursion地下降到它。
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 (fy) Left p -> return (Left (p >>= f))
testing
让我们试着做一些使用和更新状态的模型函数，在计算里面产生：
test1 :: Int -> Pause (State Int) Int test1 y = do x <- lift get lift $ put (x * 2) yield return (y + x)
另外还有一个debuggingmonad的帮助函数 – 将其中间步骤输出到控制台：
debug :: Show s => s -> Pause (State s) a -> IO (s, a) debug sp = 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解决scheme，实现协程 。 也许并不奇怪，有人有这个想法之前:-)，并创build了monad-coroutine软件包。 不足为奇的是，它与我们创build的非常相似。
该软件包进一步概括了这个想法。 继续的计算被存储在一个任意的函子里面。 这允许暂停许多变化如何处理暂停的计算。 例如， 将一个值传递给 resume （我们称为step ）的调用者，或者等待提供一个值继续等等。
