Pause 모나드

Pause 모나드

---

모나드는 놀랍고 미친 일을 많이 할 수 있습니다. 값의 중첩을 유지하는 변수를 만들 수 있습니다. 이를 통해 계산하기 전에 미래의 데이터에 액세스 할 수 있습니다. 파괴적인 업데이트를 작성할 수 있지만 실제로는 그렇지 않습니다. 그리고 연속 모나드는 사람들의 마음 을 깨뜨릴 수 있습니다 ! 일반적으로 자신의 것입니다. ;-)

그러나 여기에 도전이 있습니다. 일시 중지 할 수있는 모나드를 만들 수 있습니까?

데이터 일시 중지 sx
인스턴스 Monad (Pause s)
mutate :: (s-> s)-> Pause s ()
수익률 :: Pause s ()
step :: s-> Pause s ()-> (s, Maybe (Pause s ()))

Pause모나드 (따라서 상태 모나드의 종류 mutate명백한 의미론). 일반적으로 이와 같은 모나드는 계산을 실행하고 최종 상태를 되 돌리는 일종의 "실행"함수를 가지고 있습니다. 그러나 Pause다릅니다. step마법 yield함수를 호출 할 때까지 계산을 실행 하는 함수를 제공 합니다. 여기서 계산이 일시 중지되어 나중에 계산을 재개하기에 충분한 정보가 호출자에게 반환됩니다.

추가 경악 : 발신자가 step통화 사이의 상태를 수정할 수 있도록 허용 합니다. (예를 들어 위의 유형 서명은이를 허용해야합니다.)

---

사용 사례 : 복잡한 작업을 수행하는 코드를 작성하는 것은 종종 쉽지만 전체 PITA를 변환 하여 작업에서 중간 상태를 출력 하기도 합니다. 사용자가 실행 도중에 무언가 를 변경할 수 있도록 하려면 상황이 매우 빠르게 복잡해집니다.

구현 아이디어 :

• 분명히 스레드, 잠금 및 IO. 그러나 우리는 더 잘할 수 있습니까? ;-)

• 연속 모나드에 미쳤나요?

• 아마도 어떤 종류의 라이터 모나드로, yield현재 상태를 기록한 다음 로그의 상태 step를 반복 하여 "가장"할 수 있습니다 . (분명히 이것은 우리가 실제로 아무것도 "일시 중지"하지 않기 때문에 단계 사이의 상태 변경을 배제합니다.)

---

확실한; 계산이 결과로 완료되거나 자체적으로 일시 중지되어 당시의 상태와 함께 재개에 사용할 작업을 제공합니다.

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연속 또는 계산의 나머지 현탁액에 행해질 추가.

---

참고 : 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

이미 Pause 용 모나드가 있습니다.

type Pause s = Free (Op s)

스마트 생성자와 스테퍼를 정의하기 만하면됩니다.

더 빠르게 만듭니다.

이제 이러한 구현은 추론하기 쉽지만 가장 빠른 운영 모델이 없습니다. 특히 (>> =)의 왼쪽 관련 사용은 점근 적으로 느린 코드를 생성합니다.

이를 우회하기 위해 Codensity 모나드를 기존 무료 모나드에 적용하거나 'Church free' 모나드를 직접 사용할 수 있습니다.이 두 가지 모두 제 블로그에서 자세히 설명합니다.

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 모나드를 적용한 결과 데이터 유형에 대한 모델에 대해 쉽게 추론 할 수 있으며 여전히 빠른 평가 모델을 얻을 수 있습니다.

---

무료 모나드를 사용하는 방법은 다음과 같습니다 . 어, 음, 뭐야? 그것들은 마디에서 행동을하고 잎에서 가치를 갖는 나무이며, >>=나무 접목처럼 행동합니다.

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생성 된 나무의 모든 잎과 접목에 적용 "하는 것입니다. 트리는 대화 형 계산을위한 전략 을 나타낼 수 있습니다 . 전체 트리는 환경과의 가능한 모든 상호 작용을 다루고 환경은 트리에서 따라야 할 경로를 선택합니다. 왜 무료 입니까? 그것들은 어떤 전략이 다른 전략과 동등하다고 말하는 흥미로운 방정식 이론이없는 나무 일뿐입니다.

이제 우리가 할 수있는 많은 명령에 해당하는 Functor를 만들기위한 키트를 만들어 보겠습니다. 이거

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수정과 항복 사이의 선택을 나타냅니다. 간단한 명령의 모든 서명 (계산을 조작하는 것이 아니라 값의 관점에서 세계와 통신)은 이런 방식으로 펑터로 바뀔 수 있습니다. 손으로해야한다는 게 귀찮아요!

그것은 나에게 당신의 모나드를 준다 : 수정과 양보의 서명에 대한 자유 모나드.

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

수정 및 양보 명령을 일회성 반환으로 정의 할 수 있습니다. 에 대한 더미 입력을 협상하는 것 외에는 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

---

{-# 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.

In the monad-coroutine package you will find a general monad transformer. The Pause s monad is the same as Coroutine (State s) Id. You can combine coroutines with other monads.

Related: the Prompt monad in http://themonadreader.files.wordpress.com/2010/01/issue15.pdf

---

Note: This answer is available as a literate Haskell file at Gist.

I quite enjoyed this exercise. I tried to do it without looking at the answers, and it was worth it. It took me considerable time, but the result is surprisingly close to two of the other answers, as well as to monad-coroutine library. So I guess this is somewhat natural solution to this problem. Without this exercise, I wouldn't understand how monad-coroutine really works.

To add some additional value, I'll explain the steps that eventually led me to the solution.

Recognizing the state monad

Since we're dealing with states, it we look for patterns that can be effectively described by the state monad. In particular, s - s is isomorphic to s -> (s, ()), so it could be replaced by State s (). And function of type s -> x -> (s, y) can be flipped to x -> (s -> (s, y)), which is actually x -> State s y. This leads us to updated signatures

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

Generalization

Our Pause monad is currently parametrized by the state. However, now we see that we don't really need the state for anything, nor we use any specifics of the state monad. So we could try to make a more general solution that is parametrized by any monad:

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

Also, we could try to make mutate and step more general by allowing any kind of value, not just (). And by realizing that Maybe a is isomorphic to Either a () we can finally generalize our signatures to

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)

so that step returns the intermediate value of the computation.

Monad transformer

Now, we see that we're actually trying to make a monad from a monad - add some additional functionality. This is what is usually called a monad transformer. Moreover, mutate's signature is exactly the same as lift from MonadTrans. Most likely, we're on the right track.

The final monad

The step function seems to be the most important part of our monad, it defines just what we need. Perhaps, this could be the new data structure? Let's try:

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

If the Either part is Right, it's just a monadic value, without any suspensions. This leads us how to implement the easist thing - the lift function from MonadTrans:

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

and mutate is simply a specialization:

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

If the Either part is Left, it represents the continued computation after a suspension. So let's create a function for that:

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

Now yielding a computation is simple, we just suspend with an empty computation:

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

Still, we're missing the most important part. The Monad instance. Let's fix it. Implementing return is simple, we just lift the inner monad. Implementing >>= is a bit trickier. If the original Pause value was only a simple value (Right y), then we just wrap f y as the result. If it is a paused computation that can be continued (Left p), we recursively descend into it.

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

Testing

Let's try to make some model function that uses and updates state, yielding while inside the computation:

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

And a helper function that debugs the monad - prints its intermediate steps to the console:

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

The result is

2000
4000
8000
(8000,7001)

as expected.

Coroutines and monad-coroutine

What we have implemented is a quite general monadic solution that implements Coroutines. Perhaps not surprisingly, someone had the idea before :-), and created the monad-coroutine package. Less surprisingly, it's quite similar to what we created.

The package generalizes the idea even further. The continuing computation is stored inside an arbitrary functor. This allows suspend many variations how to work with suspended computations. For example, to pass a value to the caller of resume (which we called step), or to wait for a value to be provided to continue, etc.

참고URL : https://stackoverflow.com/questions/10236953/the-pause-monad