La monade de la pause

Les monades peuvent faire beaucoup de choses incroyables et folles. Ils peuvent créer des variables contenant une superposition de valeurs. Ils peuvent vous permettre d’accéder aux données du futur avant de le calculer. Ils peuvent vous permettre d’écrire des mises à jour destructives, mais pas vraiment. Et puis la suite monad vous permet de briser les esprits! Habituellement le vôtre. 😉

Mais voici un défi: pouvez-vous faire une monade qui peut être interrompue ?

 données Pause sx
 instance Monad (Pause s)
 muter :: (s -> s) -> Pause s ()
 rendement :: Pause s ()
 step :: s -> Pause s () -> (s, Maybe (Pause s ()))

La monade Pause est une sorte de monade d’état (donc mutate , avec la sémantique évidente). Normalement, une monade comme celle-ci a une sorte de fonction “run”, qui exécute le calcul et vous remet l’état final. Mais Pause est différent: il fournit une fonction step , qui exécute le calcul jusqu’à ce qu’il appelle la fonction de yield magique. Ici, le calcul est suspendu, renvoyant à l’appelant suffisamment d’informations pour reprendre le calcul ultérieurement.

Pour plus de précision: autorisez l’appelant à modifier l’état entre les appels d’ step . (Les signatures de type ci-dessus devraient permettre cela, par exemple.)


Cas d’utilisation: Il est souvent facile d’écrire du code qui fait quelque chose de complexe, mais un PITA total pour le transformer afin de générer également les états intermédiaires dans son fonctionnement. Si vous voulez que l’utilisateur puisse changer quelque chose à mi-parcours, les choses se compliquent très vite.

Idées de mise en œuvre:

  • Evidemment, cela peut être fait avec des threads, des verrous et des IO . Mais pouvons-nous faire mieux? 😉

  • Quelque chose de fou avec une monade de continuation?

  • Peut-être une sorte de monade d’écrivain, où le yield ne fait que consigner l’état actuel, puis nous pouvons “faire semblant” de le faire en itérant sur les états du journal. (Évidemment, cela empêche de modifier l’état entre les étapes, car nous ne faisons pas vraiment de “pause” pour le moment.)

Sûr; vous laissez simplement n’importe quel calcul soit finir avec un résultat, soit se suspendre, donnant une action à utiliser sur le CV, avec l’état à la fois:

 data Pause sa = Pause { runPause :: s -> (PauseResult sa, s) } data PauseResult sa = Done a | Suspend (Pause sa) instance Monad (Pause s) where return a = Pause (\s -> (Done a, s)) m >>= k = Pause $ \s -> case runPause ms of (Done a, s') -> runPause (ka) s' (Suspend m', s') -> (Suspend (m' >>= k), s') get :: Pause ss 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 ms = case runPause ms of (Done _, s') -> (Nothing, s') (Suspend m', s') -> (Just m', s') 

L’instance Monad ne fait que séquencer les choses de la manière habituelle, en passant le résultat final à la suite k , ou en ajoutant le rest du calcul à effectuer en suspension.

Remarque: vous ne vous êtes fourni aucun access direct à l’état actuel de cette monade.

Pause s est juste une monade libre sur les opérations de mutate et de yield . Implémenté directement vous obtenez:

 data Pause sa = Return a | Mutate (s -> s) (Pause sa) | Yield (Pause sa) instance Monad (Pause s) where return = Return Return a >>= k = ka Mutate fp >>= k = Mutate f (p >>= k) Yield p >>= k = Yield (p >>= k) 

avec quelques constructeurs intelligents pour vous donner l’API souhaitée:

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

et la fonction d’étape pour le conduire

 step :: s -> Pause s () -> (s, Maybe (Pause s ())) step s (Mutate fk) = step (fs) k step s (Return ()) = (s, Nothing) step s (Yield k) = (s, Just k) 

Vous pouvez également définir cela directement en utilisant

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

(de mon paquet ‘gratuit’) avec

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

alors nous avons déjà une monade pour la pause

 type Pause s = Free (Op s) 

et juste besoin de définir les constructeurs intelligents et stepper.

Faire plus vite

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

Pour contourner ce problème, vous pouvez appliquer la monade Codensity à votre monade gratuite existante ou utiliser directement la monade «Church free» , 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 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.

Voici comment j’y vais, en utilisant des monades gratuites . Euh, qu’est-ce qu’ils sont? Ce sont des arbres avec des actions aux nœuds 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, vous devez simplement être quelque chose que vous pouvez cartographier: tout Functor fera.

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

C’est juste “appliquer k à toutes les feuilles et greffer dans les arbres résultants”. Ces arbres peuvent représenter des stratégies de calcul interactif: l’arbre complet couvre toutes les interactions possibles avec l’environnement, et l’environnement choisit le chemin à suivre dans l’arbre. Pourquoi sont-ils gratuits ? Ce ne sont que des arbres, sans théorie équationnelle intéressante, indiquant quelles stratégies sont équivalentes à d’autres stratégies.

Maintenant, avons un kit pour faire des Functors qui correspondent à un tas de commandes que nous pourrions vouloir faire. Cette chose

 data (:>>:) stx = 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 une commande avec le type d’entrée s et le type de sortie t . Pour ce faire, vous devez choisir une entrée dans s et expliquer comment continuer à la valeur de x la sortie de la commande dans t . Pour mapper une fonction sur une telle chose, vous la placez sur la suite. Jusqu’à présent, équipement 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 valeur pour les commandes que nous voulons pouvoir faire!

Maintenant, assurez-vous que nous pouvons offrir un choix entre ces commandes. On peut montrer qu’un choix entre foncteurs donne un foncteur. Plus d’équipement standard.

 data (:+:) fgx = L (fx) | R (gx) 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. Toute signature de commandes simples (communiquer avec le monde en termes de valeurs plutôt que de manipuler des calculs) peut être transformée en un foncteur de cette manière. C’est un problème que je dois le faire à la main!

Cela me donne votre monade: la monade libre sur la signature de modification et de rendement.

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

Je peux définir les commandes de modification et de rendement en tant que one-do-then-return. En dehors de la négociation de la saisie factice pour le yield , c’est juste mécanique.

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

La fonction step donne alors un sens aux arbres de stratégie. C’est un opérateur de contrôle qui construit 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 (fs) (k ()) step s (Do (R (() :? k))) = (s, Just (k ())) 

La fonction step exécute la stratégie jusqu’à ce qu’elle se termine par un Ret ou qu’elle cède en mutant l’état au fur et à mesure.

La méthode générale est la suivante: séparer les commandes (en termes de valeurs) des opérateurs de contrôle (calculs de manipulation); construire la monade libre des “arbres de stratégie” sur la signature des commandes (lancer la poignée); implémenter les opérateurs de contrôle par récursivité sur les arbres de stratégie.

Ne correspond pas exactement à votre type de signature, mais c’est très simple:

 {-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, UndecidableInstances #-} import Control.Monad.State newtype ContinuableT ma = Continuable { runContinuable :: m (Either a (ContinuableT ma)) } instance Monad m => Monad (ContinuableT m) where return = Continuable . return . Left Continuable m >>= f = Continuable $ do v <- m case v of Left a -> runContinuable (fa) Right b -> return (Right (b >>= f)) instance MonadTrans ContinuableT where lift m = Continuable (liftM Left m) instance MonadState sm => MonadState s (ContinuableT m) where get = lift get put = lift . put yield :: Monad m => ContinuableT ma -> ContinuableT ma 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 sx = Pause (s -> (s, Either x (Pause sx))) instance Monad (Pause s) where return x = Pause (, Left x) Pause k >>= f = Pause $ \s -> let (s', v) = ks in case v of Left x -> step (fx) s' Right x -> (s', Right (x >>= f)) mutate :: (s -> s) -> Pause s () mutate f = Pause (\s -> (fs, Left ())) yield :: Pause s () yield = Pause (, Right (return ())) step :: Pause sx -> s -> (s, Either x (Pause sx)) step (Pause x) = x 

C’est comme ça que je l’ai écrit. J’ai donné à step un peu plus de définition générale, cela pourrait être aussi bien nommé runPause . En fait, la reflection sur le type de step me mène à la définition de la Pause .

Dans le paquet monad-coroutine , vous trouverez un transformateur monad général. La monade de Pause s est la même que celle de Coroutine (State s) Id . Vous pouvez combiner des coroutines avec d’autres monades.

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

Remarque: Cette réponse est disponible sous forme de fichier Haskell alphabétisé chez Gist.

J’ai bien aimé cet exercice. J’ai essayé de le faire sans regarder les réponses, et cela en valait la peine. Cela m’a pris beaucoup de temps, mais le résultat est étonnamment proche de deux autres réponses, ainsi que de la bibliothèque monad-coroutine . Donc, je suppose que c’est une solution un peu naturelle à ce problème. Sans cet exercice, je ne comprendrais pas comment fonctionne vraiment monad-coroutine .

Pour append une valeur supplémentaire, je vais vous expliquer les étapes qui m’ont finalement conduit à la solution.

Reconnaître la monade d’état

Puisque nous traitons avec des états, nous recherchons des modèles qui peuvent être efficacement décrits par la monade d’état. En particulier, s - s est isomorphe à s -> (s, ()) , il pourrait donc être remplacé par State s () . Et la fonction de type s -> x -> (s, y) peut être retournée à x -> (s -> (s, y)) , qui est en fait x -> State sy . Cela nous amène à mettre à jour les signatures

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

Généralisation

Notre monade Pause est actuellement paramétrée par l’état. Cependant, nous voyons maintenant que nous n’avons pas vraiment besoin de l’état pour quoi que ce soit, ni que nous utilisons des détails de la monade d’état. On pourrait donc essayer de faire une solution plus générale paramétrée par n’importe quelle monade:

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

En outre, nous pourrions essayer de faire mutate et faire un step plus général en autorisant tout type de valeur, pas seulement () . Et en se rendant compte que Maybe aMaybe a est isomorphe à Either a () nous pouvons enfin généraliser nos signatures à

 mutate :: (Monad m) = ma -> Pause ma yield :: (Monad m) = Pause m () step :: (Monad m) = Pause ma -> m (Either (Pause ma) a) 

de sorte que cette step renvoie la valeur intermédiaire du calcul.

Transformateur Monad

Maintenant, nous voyons que nous essayons de faire une monade à partir d’une monade – ajoutez des fonctionnalités supplémentaires. C’est ce qu’on appelle généralement un transformateur monad . De plus, la signature de MonadTrans est exactement la même que celle de MonadTrans . Très probablement, nous sums sur la bonne voie.

La monade finale

La fonction step semble être la partie la plus importante de notre monade, elle définit exactement ce dont nous avons besoin. Peut-être que cela pourrait être la nouvelle structure de données? Essayons:

 import Control.Monad import Control.Monad.Cont import Control.Monad.State import Control.Monad.Trans data Pause ma = Pause { step :: m (Either (Pause ma) a) } 

Si l’une Either l’ Either partie est Right , c’est juste une valeur monadique, sans aucune suspension. Cela nous amène à implémenter la chose facile – la fonction lift de MonadTrans :

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

et mutate est simplement une spécialisation:

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

Si l’une Either l’ Either partie est à Left , elle représente le calcul continu après une suspension. Alors créons une fonction pour cela:

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

Le calcul est simple, nous suspendons avec un calcul vide:

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

Pourtant, nous manquons la partie la plus importante. L’instance de Monad Fixons le problème. La mise en œuvre du return est simple, nous levons simplement la monade intérieure. Implémenter >>= est un peu plus compliqué. Si la valeur de Pause origine n’était qu’une simple valeur ( Right y ), alors nous avons simplement envelopper le résultat. Si c’est un calcul en pause qui peut être poursuivi ( Left p ), nous y rentrons récursivement.

 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 (fy) Left p -> return (Left (p >>= f)) 

Essai

Essayons de créer une fonction de modèle qui utilise et met à jour l’état, c’est-à-dire:

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

Et une fonction d'assistance qui corrige la monade - imprime ses étapes intermédiaires à la console:

 debug :: Show s => s -> Pause (State s) a -> IO (s, a) debug sp = 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 

Le résultat est

 2000 4000 8000 (8000,7001) 

comme prévu.

Coroutines et monad -coroutine

Ce que nous avons mis en œuvre est une solution monadique assez générale qui implémente Coroutines . Peut-être pas surprenant, quelqu'un a eu l'idée avant :-), et a créé le paquet monad-coroutine . De manière moins surprenante, cela ressemble beaucoup à ce que nous avons créé.

Le paquet généralise l'idée encore plus loin. Le calcul continu est stocké dans un foncteur arbitraire. Cela permet de suspendre de nombreuses variantes sur la façon de travailler avec des calculs suspendus. Par exemple, pour transmettre une valeur à l'appelant de resume (que nous avons appelé step ), ou pour attendre qu'une valeur soit fournie pour continuer, etc.