Monada pauzy

Uwaga: nie zapewniłeś sobie bezpośredniego dostępu do obecnego stanu s w tej monadzie.

Pause s jest tylko darmową monadą nad operacjami mutate i yield. Zaimplementowane bezpośrednio otrzymujesz:

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)

Z kilkoma inteligentnymi konstruktorami, aby dać ci pożądane API:

mutate :: (s -> s) -> Pause s ()
mutate f = Mutate f (return ())

yield :: Pause s ()
yield = Yield (return ())

I funkcja step, która go napędza

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)

Możesz również zdefiniować to bezpośrednio za pomocą

data Free f a = Pure a | Free (f (Free f a))

(z mojego 'darmowego' pakietu) z

data Op s a = Mutate (s -> s) a | Yield a

Wtedy już mamy monada na pauzę

type Pause s = Free (Op s)

I wystarczy zdefiniować inteligentne konstruktory i stepper.

Szybciej.

Teraz, te implementacje są łatwe do rozumowania, ale nie mają najszybszego modelu operacyjnego. W szczególności lewe powiązane użycie ( > > = ) daje asymptotycznie wolniejszy kod.

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/

Rezultatem zastosowania kodowanej przez Kościół wersji darmowej monady jest to, że otrzymujesz łatwy do zrozumienia model dla typu danych, a nadal otrzymujesz szybki model oceny.

Oto jak bym to zrobił, używając darmowych monad. Czym one są? Są to drzewa z akcjami na węzłach i wartościami na liściach, z >>= działającymi jak szczepienie drzew.

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

Nie jest niczym niezwykłym pisać F^*X na takie coś w matematyce, stąd moja marudna nazwa typu infix. Aby utworzyć instancję, wystarczy f być czymś, co można odwzorować: zrobi to każda Functor.

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

To po prostu "zastosuj k na wszystkie liście i przeszczep w powstałe drzewa". Drzewa mogą reprezentować strategie do obliczeń interaktywnych: całe drzewo obejmuje każdą możliwą interakcję z otoczeniem, a środowisko wybiera ścieżkę w drzewie, którą ma podążać. Dlaczego są one wolne ? To tylko drzewa, bez interesującej teorii równań, mówiące, które strategie są równoważne które inne strategie.

Teraz mamy zestaw do tworzenia funktorów, które odpowiadają kilku poleceniom we może chcesz być w stanie to zrobić. To coś

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

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

Przechwytuje ideę uzyskania wartości w x po jednym poleceniu z typem wejścia s i typem wyjścia t. Aby to zrobić, musisz wybrać wejście w s i wyjaśnić, jak kontynuować do wartości w x, biorąc pod uwagę wyjście polecenia w t. Aby odwzorować funkcję na taką rzecz, przyczepiasz ją do kontynuacji. Do tej pory standardowe wyposażenie. Dla naszego problemu możemy teraz zdefiniować dwa funktory:

type Modify s  = (s -> s) :>>: ()
type Yield     = () :>>: ()

To tak jak właśnie spisałem typy wartości dla poleceń, które chcemy wykonać!

Teraz upewnijmy się, że możemy zaoferować wybór pomiędzy tymi poleceniami. Możemy pokazać, że wybór pomiędzy funktorami daje funktor. Więcej standardowego wyposażenia.

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)

Zatem Modify s :+: Yield reprezentuje wybór pomiędzy modyfikacją a poddaniem. Każdy podpis prostych poleceń (komunikujących się ze światem pod względem wartości, a nie manipulujących obliczeniami) można obrócić do functora w ten sposób. To kłopot, że muszę to zrobić ręcznie!

To daje mi Twoją monadę: darmową monadę nad podpisem modyfikuj i plonuj.

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

Mogę zdefiniować polecenia modify i yield jako one-do-then-return. Poza negocjowaniem atrapy wejścia dla yield, to tylko mechaniczne.

mutate :: (s -> s) -> Pause s ()
mutate f = Do (L (f :? Ret))

yield :: Pause s ()
yield = Do (R (() :? Ret))

Funkcja step nadaje znaczenie drzewom strategii. Jest operatorem sterującym , konstruującym jeden (być może) z kolejny.

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

Funkcja step uruchamia strategię, dopóki nie zakończy się Ret, lub daje, mutując stan w miarę upływu czasu.

Ogólna metoda wygląda następująco: oddziel polecenia (interakcja pod względem wartości) od operatory sterowania (manipulowanie obliczeniami); zbuduj darmową monadę "drzew strategii" nad podpisem poleceń( uruchamianie uchwytu); zaimplementuj operatory sterowania przez rekurencję nad strategią drzewa.

Nie pasuje dokładnie do Twoich podpisów typu, ale na pewno proste:

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

W pakiecie monad-coroutine znajdziesz ogólny transformator monad. Monada Pause s jest taka sama jak Coroutine (State s) Id. Możesz łączyć koronki z innymi monadami.

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

Uwaga: Ta odpowiedź jest dostępna jako literat Haskell plik w Gist.

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

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

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)

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

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

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

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

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

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)