72

モナドは多くの驚くべき、クレイジーなことをすることができます。それらは、値の重ね合わせを保持する変数を作成できます。それらはあなたがそれを計算する前にあなたが未来からのデータにアクセスすることを可能にすることができます。彼らはあなたが破壊的な更新を書くことを可能にすることができますが、実際にはそうではありません。そして、継続モナドはあなたが人々の心を壊すことを可能にします！通常はあなた自身のものです。;-)

しかし、ここに課題があります。一時停止できるモナドを作成できますか？

データ一時停止sx
インスタンスモナド（一時停止）
変異::（s-> s）->一時停止s（）
歩留まり::一時停止s（）
ステップ::s->一時停止s（）->（s、たぶん（一時停止s（）））

Pauseモナドは一種の状態モナドです（したがって、mutate明白なセマンティクスを備えています）。通常、このようなモナドには、計算を実行して最終状態を返す、ある種の「実行」関数があります。ただしPause、違います。step魔法の関数を呼び出すまで計算を実行する関数を提供しyieldます。ここで計算は一時停止され、後で計算を再開するのに十分な情報が呼び出し元に返されます。

さらに素晴らしい場合：呼び出し元が呼び出し間の状態を変更できるようにしstepます。（たとえば、上記の型署名はこれを可能にするはずです。）

ユースケース：複雑なことを行うコードを書くのは簡単なことがよくありますが、それを変換して操作の中間状態も出力するための完全なPITAです。ユーザーが実行の途中で何かを変更できるようにしたい場合、物事は非常に速く複雑になります。

実装のアイデア：

  • 明らかに、それはスレッド、ロック、およびで行うことができますIO。しかし、もっとうまくやれるでしょうか？;-)

  • 継続モナドで何かおかしなことはありますか？

  • たぶん、ある種のライターモナドで、現在の状態をログに記録するだけで、ログ内の状態を反復処理することで、そのyieldふりをすることができます。step（明らかに、これにより、ステップ間で状態を変更することはできなくなります。これは、現在、実際には何も「一時停止」していないためです。）

4

6 に答える 6

68

s注：このモナドの現在の状態に直接アクセスすることはできませんでした。

Pause smutateと操作の単なる無料のモナド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)

スマートコンストラクターとステッパーを定義する必要があります。

それをより速くします。

現在、これらの実装は簡単に推論できますが、最速の運用モデルはありません。特に、（>> =）の左関連の使用は、漸近的に遅いコードを生成します。

これを回避するには、 Codensityモナドを既存の無料モナドに適用するか、「 Churchfree 」モナドを直接使用します。どちらもブログで詳しく説明しています。

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モナドのチャーチエンコードバージョンを適用した結果、データ型のモデルについて簡単に推論でき、それでも高速な評価モデルを取得できます。

于 2012-04-19T21:51:03.083 に答える
60

もちろん; 計算を結果で終了させるか、それ自体を一時停止して、再開時に使用するアクションとその時点の状態を指定します。

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継続に渡すか、一時停止時に実行される残りの計算を追加します。

于 2012-04-19T21:46:57.017 に答える
34

これが私が無料のモナドを使ってそれをどうやってやるのかです。えーと、ええと、彼らは何ですか？それらは、ノードでのアクションとリーフでの値を持ち、>>=木の接ぎ木のように機能するツリーです。

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)

入力タイプと出力タイプの1つのコマンドのx後に値を取得するというアイデアをキャプチャします。これを行うには、で入力を選択し、でコマンドの出力を指定しての値に進む方法を説明する必要があります。そのようなもの全体に関数をマッピングするには、それを継続に追加します。これまでのところ、標準装備。私たちの問題では、2つのファンクターを定義することができます。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変更と譲歩の間の選択を表します。単純なコマンドの署名（計算を操作するのではなく、値の観点から世界と通信する）は、この方法でファンクターに変換できます。手でやらなきゃいけないのが面倒！

それは私にあなたのモナドを与えます：modifyとyieldの署名の上の無料のモナド。

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関数は戦略ツリーに意味を与えます。これは制御演算子であり、（おそらく）別の計算から1つの計算を構築します。

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、状態を変化させます。

一般的な方法は次のようになります。コマンド（値の観点から相互作用する）を制御演算子（計算を操作する）から分離します。コマンドの署名（ハンドルのクランク）の上に「戦略ツリー」の無料のモナドを構築します。戦略ツリーを再帰的に実行して、制御演算子を実装します。

于 2012-04-19T22:15:53.093 に答える
14

型署名と正確には一致しませんが、確かに単純です。

{-# 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
于 2012-04-20T02:13:25.283 に答える
11 
{-# 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。

モナドコルーチンパッケージには、一般的なモナド変換子が含まれています。モナドはPause sと同じCoroutine (State s) Idです。コルーチンを他のモナドと組み合わせることができます。

関連：http ：//themonadreader.files.wordpress.com/2010/01/issue15.pdfのプロンプトモナド

于 2012-04-19T21:50:39.467 に答える
11

注：この回答は、Gistで読み書きのできるHaskellファイルとして入手できます。

私はこの運動をとても楽しんだ。私は答えを見ずにそれをやろうとしました、そしてそれはそれだけの価値がありました。かなりの時間がかかりましたが、結果は驚くべきことに、他の2つの回答と、モナドコルーチンライブラリに近いものになっています。ですから、これはこの問題に対するやや自然な解決策だと思います。この演習がなければ、モナドコルーチンが実際にどのように機能するのか理解できません。

いくつかの付加価値を追加するために、私は最終的に解決策にたどり着いたステップを説明します。

州のモナドを認識する

状態を扱っているので、状態モナドによって効果的に記述できるパターンを探します。特に、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、計算の中間値を返します。

モナド変換子

これで、実際にモナドからモナドを作成しようとしていることがわかります。いくつかの機能を追加します。これは通常モナド変換子と呼ばれるものです。さらに、の署名はからのリフト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

yield計算を行うのは簡単です。空の計算で一時停止します。

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)

そして、モナドをデバッグするヘルパー関数-その中間ステップをコンソールに出力します：

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)

予想通り。

コルーチンとモナドコルーチン

私たちが実装したのは、コルーチンを実装する非常に一般的なモナディックソリューションです。おそらく驚くことではありませんが、誰かが以前にアイデアを持っていて、モナドコルーチンパッケージを作成しました:-)。それほど驚くことではありませんが、これは私たちが作成したものと非常によく似ています。

パッケージは、アイデアをさらに一般化します。継続的な計算は、任意のファンクター内に格納されます。これにより、中断された計算を処理する方法の多くのバリエーションを中断できます。たとえば、resumeの呼び出し元（これを呼び出しました）に値を渡したり、値が提供されるのを待って続行したりします。step

于 2012-08-31T13:06:31.120 に答える