La monade Pause

Question

Les monades peuvent faire beaucoup de choses étonnantes et folles. Elles peuvent créer des variables qui contiennent une superposition de valeurs. Elles peuvent vous permettre d'accéder à des données du futur avant de les calculer. Elles peuvent vous permettre d'écrire des mises à jour destructives, mais pas vraiment. Et puis la monade continuation vous permet de briser l'esprit des gens ! Habituellement le vôtre. ;-)

Mais voici un défi : Pouvez-vous créer une monade qui peut être interrompu ?

data Pause s x
instance Monad (Pause s)
mutate :: (s -> s) -> Pause s ()
yield :: Pause s ()
step :: s -> Pause s () -> (s, Maybe (Pause s ()))

Le site Pause est une sorte de monade d'état (donc mutate avec la sémantique évidente). Normalement, une monade comme celle-ci possède une sorte de fonction "run", qui exécute le calcul et vous renvoie l'état final. Mais Pause est différent : il fournit un step qui exécute le calcul jusqu'à ce qu'elle appelle la fonction magique yield fonction. Ici, le calcul est mis en pause, renvoyant à l'appelant suffisamment d'informations pour reprendre le calcul plus tard.

Pour plus d'efficacité : Permettez à l'appelant de modifier l'état entre step appels. (Les signatures de type ci-dessus devraient le permettre, par exemple).

---

Cas d'utilisation : Il est souvent facile d'écrire du code qui fait quelque chose de complexe, mais c'est un véritable casse-tête de le transformer pour qu'il puisse aussi être utilisé pour d'autres applications. sortie les états intermédiaires de son fonctionnement. Si vous voulez que l'utilisateur puisse changement quelque chose à mi-chemin de l'exécution, les choses deviennent très vite complexes.

Idées de mise en œuvre :

• Évidemment il peut être fait avec des threads, des verrous et des IO . Mais pouvons-nous faire mieux ? ;-)

• Quelque chose d'insensé avec une monade de continuation ?

• Peut-être une sorte de monade d'écriture, où yield enregistre juste l'état actuel, et ensuite nous pouvons "prétendre" à step en itérant sur les états du journal. (Évidemment, cela exclut la modification de l'état entre les étapes, puisque nous ne faisons pas vraiment de "pause" maintenant).

Answer 1

Note : que vous ne vous êtes pas fourni un accès direct à l'état actuel s dans cette monade.

Pause s est juste une monade libre sur les mutate y yield opérations. Mis en œuvre directement, vous obtenez :

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)

avec un couple de constructeurs intelligents pour vous donner l'API désirée :

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

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

et la fonction échelon pour la piloter

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)

Vous pouvez également le définir directement en utilisant

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

(de mon paquet "gratuit") avec

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

alors nous avons déjà une monade pour Pause

type Pause s = Free (Op s)

et il suffit de définir les constructeurs intelligents et le stepper.

Le rendre plus rapide.

Maintenant, ces implémentations sont faciles à raisonner, mais elles n'ont pas le modèle opérationnel le plus rapide. En particulier, les utilisations de (>>=) associées à gauche donnent un code asymptotiquement plus lent.

Pour contourner ce problème, vous pouvez appliquer la méthode Codensité à votre monade libre existante, ou utilisez simplement l'option L'église est libre directement, que je décris en détail sur mon blog.

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/

Le résultat de l'application de la version codée par Church de la monade Free est que vous obtenez un modèle facile à raisonner pour le type de données, et vous obtenez toujours un modèle d'évaluation rapide.

Answer 2

Bien sûr, il suffit de laisser un calcul se terminer avec un résultat, ou se suspendre, en donnant une action à utiliser lors de la reprise, ainsi que l'état à ce moment-là :

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

Le site Monad se contente d'enchaîner les choses de manière normale, en transmettant le résultat final à l'instance k la poursuite, ou l'ajout du reste du calcul à effectuer en suspension.

Answer 3

Voici comment je m'y prendrais, en utilisant gratuit monades. Euh, hum, qu'est-ce que c'est ? Ce sont des arbres avec des actions aux noeuds et des valeurs aux feuilles, avec >>= agissant comme une greffe d'arbre.

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

Il n'est pas rare d'écrire F * X pour une telle chose dans les mathématiques, d'où mon nom de type infixe grincheux. Pour créer une instance, il suffit de f pour être quelque chose que vous pouvez cartographier : tout Functor fera l'affaire.

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

C'est juste "appliquer k à toutes les feuilles et à greffer les arbres ainsi obtenus". Ces arbres de conserve représentent stratégies pour le calcul interactif : l'arbre entier couvre toutes les interactions possibles avec l'environnement, et l'environnement choisit le chemin à suivre dans l'arbre. Pourquoi gratuit ? Ce sont juste des arbres, sans aucune théorie équationnelle intéressante, qui dit quelles stratégies sont équivalentes à quelles autres stratégies.

Disposons maintenant d'un kit pour créer des foncteurs qui correspondent à un ensemble de commandes que nous pourrions vouloir être en mesure d'exécuter. Cette chose

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

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

capture l'idée d'obtenir une valeur dans x après un commande avec le type d'entrée s et le type de sortie t . Pour cela, vous devez choisir une entrée dans s et expliquer comment poursuivre jusqu'à la valeur dans x étant donné la sortie de la commande dans t . Pour faire correspondre une fonction à un tel objet, il faut l'ajouter à la suite. Jusqu'ici, le matériel standard. Pour notre problème, nous pouvons maintenant définir deux foncteurs :

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

C'est comme si je venais d'écrire les types de valeurs pour les commandes que nous voulons être en mesure de faire !

Maintenant, assurons-nous que nous pouvons offrir une choix entre ces commandes. Nous pouvons montrer qu'un choix entre des foncteurs donne un foncteur. Plus de matériel standard.

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)

Donc, Modify s :+: Yield représente le choix entre modifier et céder. Tout signature de commandes simples (communiquer avec le monde en termes de valeurs plutôt que de manipuler des calculs) peut être transformé en un foncteur de cette façon. C'est dommage que je doive le faire à la main !

Cela me donne votre monade : la monade libre sur la signature de modify et yield.

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

Je peux définir les commandes modifier et céder comme une commande faire-et-retour. En dehors de la négociation de l'entrée factice de yield c'est juste de la mécanique.

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

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

Le site step donne alors un sens aux arbres stratégiques. C'est une opérateur de contrôle en construisant un calcul (peut-être) à partir d'un autre.

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

Le site step La fonction exécute la stratégie jusqu'à ce qu'elle se termine avec un Ret ou il cède, en modifiant l'état au fur et à mesure.

La méthode générale est la suivante : séparer les commandes (interagissant en termes de valeurs) à partir de l'outil opérateurs de contrôle (manipuler les calculs) ; construire la monade libre des "arbres stratégiques" sur la signature des commandes (manier la manivelle) ; implémenter les opérateurs de contrôle par récursion sur les arbres stratégiques.

Answer 4

Il ne correspond pas exactement à vos signatures de type, mais il est certainement simple :

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

Answer 5

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

C'est comme ça que j'aurais écrit ça. J'ai donné step une définition un peu plus générale, il pourrait aussi bien être nommé runPause . En fait, en pensant au type de step me conduire à la définition de Pause .

En el monade-coroutine vous trouverez un transformateur général de monades. Le site Pause s est identique à la monade Coroutine (State s) Id . Vous pouvez combiner les coroutines avec d'autres monades.

Voir aussi : la monade Prompt dans http://themonadreader.files.wordpress.com/2010/01/issue15.pdf