haskell-暂停单子

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 ()))

yield monad是一种状态monad(因此具有明显的语义step)。 通常,像这样的monad具有某种“运行”功能,该功能运行计算并让您退回最终状态。 但是Pause是不同的:它提供了step函数,该函数运行计算直到调用神奇的yield函数。 在这里,计算被暂停,向调用者返回足够的信息,以便稍后继续计算。

要获得更大的威力,请执行以下操作:允许呼叫者修改yield呼叫之间的状态。 (例如,上面的类型签名应允许这样做。)


用例:编写执行复杂功能的代码通常很容易,但是使用一个完整的PITA对其进行转换以在其操作中也输出中间状态。 如果您希望用户能够在执行过程中进行某些更改,那么事情就会变得非常复杂。

实施思路:

  • 显然,可以使用线程,锁和yield来完成。但是我们可以做得更好吗? ;-)

  • 用连续单调疯狂吗?

  • 也许是某种作家monad,其中yield只是记录当前状态,然后我们可以通过遍历日志中的状态来“假装”为step。 (显然,这阻止了在步骤之间更改状态,因为我们现在并没有真正“暂停”任何内容。)

6个解决方案
62 votes

注意:您没有向自己提供直接访问此monad当前状态Pause s的权限。

Pause s只是mutateyield操作上的免费单子。 直接实现,您将获得:

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)

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

使其更快。

现在,这些实现很容易推论,但是它们没有最快的运营模型。 特别是,(>> =)的左相关用法会产生渐近变慢的代码。

为了解决这个问题,您可以将Codensity单子应用到您现有的免费单子上,或者直接使用“无教会”单子,这两种方法我都在我的博客中进行了详细介绍。

[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编码版本的结果是,您可以轻松推断数据类型的模型,但仍可以得到快速评估模型。

Edward KMETT answered 2019-10-05T00:20:02Z
54 votes

当然; 您只需让任何计算要么以结果结束,要么暂停自身,给出要在恢复上使用的动作以及当时的状态:

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延续,或添加其余计算以在暂停时完成。

ehird answered 2019-10-05T00:18:06Z
31 votes

使用免费的monad,这是我的处理方式。 嗯,那是什么? 它们是在节点处具有动作,在叶子处具有值的树,其中step的行为就像植树一样。

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

在数学中为这样的事情写F * X并不罕见,因此我的名字很怪异。 要创建实例,只需要将step映射为即可:任何Ret都可以。

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

那只是“在所有叶子上应用step,并在生成的树中应用嫁接”。 这些罐形树代表了交互式计算的策略:整棵树涵盖了与环境的所有可能交互,并且环境选择了树中要遵循的路径。 他们为什么免费? 它们只是一棵树,上面没有有趣的等式理论,它们说明哪些策略与其他策略等效。

现在,我们有一个制作函子的工具包,它对应于我们可能想执行的一堆命令。 这东西

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

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

捕获了在输入类型为Ret和输出类型为t的一个命令后获取step中的值的想法。为此,您需要在s中选择一个输入,并说明如何在2555121633455506506中给定命令输出的情况下继续到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)

因此,step表示修改和屈服之间的选择。 任何简单命令的签名(根据值与世界进行通信而不是操纵计算)都可以通过这种方式转化为函子。 我必须手动做这件事很麻烦!

那给了我你的单子:修改和收益签名的免费单子。

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

我可以将Modify和yield命令定义为先执行再返回。 除了协商step的虚拟输入外,这仅仅是机械的。

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为止,或者它屈服,并随即改变状态。

通用方法是这样的:将命令(根据值进行交互)与控制运算符(操纵计算)分开; 在命令签名上建立免费的“策略树” monad(摇动手柄); 通过递归策略树来实现控制运算符。

pigworker answered 2019-10-05T00:21:50Z
11 votes

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

{-# 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
Daniel Wagner answered 2019-10-05T00:22:17Z
8 votes
{-# 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

我就是这样写的。 我给了Pause s一个更通用的定义,它的名字也叫Coroutine (State s) Id。实际上,对step类型的思考使我想到了Pause

在monad-coroutine程序包中,您将找到通用的monad变压器。 Pause s单声道与Coroutine (State s) Id相同。您可以将协程与其他单声道组合。

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

sdcvvc answered 2019-10-05T00:22:58Z
8 votes

注意:此答案可从Gist的Haskell识字文件中获得。

我很喜欢这个练习。 我试着不看答案就做,这是值得的。 我花了相当长的时间,但是结果出奇地接近其他两个答案以及monad-coroutine库。 因此,我认为这是解决该问题的自然方法。 没有这项练习,我将无法理解monad-coroutine的工作原理。

为了增加一些附加值,我将解释最终导致我找到解决方案的步骤。

识别状态单子

由于我们正在处理状态,因此我们在寻找可以由状态monad有效描述的模式。 特别是stepreturn是同构的,因此可以用>>=替代。类型Pause的功能可以转换为Right y,实际上是f y。这导致我们更新了签名。

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

概括

我们的step monad目前已由该州参数化。 但是,现在我们看到,我们实际上并不需要状态,也不需要使用状态monad的任何细节。 因此,我们可以尝试制定一种更通用的解决方案,该解决方案可以通过任何monad进行参数化:

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

另外,我们可以尝试通过允许任何类型的值(而不只是>>=)使stepreturn更通用。并意识到PauseRight y是同构的,我们最终可以将签名概括为

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变压器。 此外,step的签名与return的举升完全相同。很可能,我们走在正确的轨道上。

最后的单子

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) }

如果step部分为return,则仅是一元值,没有任何暂停。 这引导我们如何实现简单的东西->>=来自Pause的函数:

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

step只是一个专业化:

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

如果step部分为return,则表示暂停后的继续计算。 因此,我们为此创建一个函数:

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

现在step进行计算很简单,我们只是用一个空计算:

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

尽管如此,我们仍缺少最重要的部分。 step实例。 修复它。 实现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-协程

我们实现的是实现协程的相当通用的单子解决方案。 也许并不奇怪,有人在:-)之前就有了这个主意,并创建了monad-协程包。 毫不奇怪,它与我们创建的内容非常相似。

该软件包进一步推广了该想法。 连续的计算存储在任意函子中。 这允许挂起许多变化,以处理挂起的计算。 例如,将值传递给resume的调用者(我们将其称为step),或等待提供的值继续使用,等等。

Petr Pudlák answered 2019-10-05T00:25:58Z
translate from https://stackoverflow.com:/questions/10236953/the-pause-monad