État Monad, des séquences de nombres aléatoires et le code monadique

Question

Je suis en train de saisir l'Etat Monade et dans ce but que je voulais écrire un code monadique qui générerait une séquence de nombres aléatoires à l'aide d'un générateur congruence linéaire (probablement pas bon, mais mon intention est juste d'apprendre l'Etat Monad, ne pas construire une bonne bibliothèque de RNG).

Le générateur est juste ce (je veux générer une séquence de Bools pour simplifier):

type Seed = Int

random :: Seed -> (Bool, Seed)
random seed = let (a, c, m) = (1664525, 1013904223, 2^32)  -- some params for the LCG
                  seed' = (a*seed + c) `mod` m
              in  (even seed', seed')   -- return True/False if seed' is even/odd 

Ne vous inquiétez pas les chiffres, c'est juste une règle de mise à jour pour la semence qui (selon Numerical Recipes) devrait générer une séquence pseudo-aléatoire de Ints. Maintenant, si je veux générer des nombres aléatoires de manière séquentielle, je ferais:

rand3Bools :: Seed -> ([Bool], Seed)
rand3Bools seed0  = let (b1, seed1) = random seed0
                        (b2, seed2) = random seed1
                        (b3, seed3) = random seed2
                    in  ([b1,b2,b3], seed3)

Ok, donc je pourrais éviter ce passe-partout en utilisant un État Monad:

import Control.Monad.State

data Random {seed :: Seed, value :: Bool}

nextVal = do 
   Random seed val <- get 
   let seed' = updateSeed seed
       val'  = even seed'
   put (Random seed' val')
   return val'

updateSeed seed = let (a,b,m) = (1664525, 1013904223, 2^32) in (a*seed + c) `mod` m

Et enfin:

getNRandSt n = replicateM n nextVal 

getNRand :: Int -> Seed -> [Bool]
getNRand   n seed = evalState (getNRandStates n) (Random seed True)

Ok, cela fonctionne très bien et me donner une liste de n Bools pseudo-aléatoire pour chaque semence donnée. Mais ...

Je peux lire ce que je l'ai fait (principalement basé sur cet exemple: http://www.haskell.org/pipermail/beginners/2008-September/000275.html ) et de le reproduire à faire d'autres choses. Mais je ne pense pas que je puisse comprendre ce qui se passe réellement derrière le do-notation et les fonctions monadiques (comme replicateM).

Quelqu'un peut-il me aider avec certains de ces doutes?

1 - J'ai essayé de desugar la fonction nextval pour comprendre ce qu'il fait, mais je ne pouvais pas. Je devine qu'il extrait l'état actuel, il met à jour, puis passer l'état d'avance pour le prochain calcul, mais ce n'est basé sur la lecture de ce faire-sucre comme si elle était l'anglais.

Comment puis-je desugar vraiment cette fonction à l'original >> = et retour fonctions étape par étape?

2 - Je ne pouvais pas saisir exactement ce que les fonctions de put et get font. Je peux deviner qu'ils « pack » et « déballer » l'état. Mais la mécanique derrière le do-sucre est encore difficile à atteindre pour moi.

Eh bien, d'autres remarques générales sur ce code sont les bienvenus. Je suis tombé parfois avec Haskell que je peux créer un code qui fonctionne et faire ce que je pense à faire, mais je ne peux pas « suivre l'évaluation » que je suis habitué à faire des programmes impératifs.

Answer 1

Le monade de l'Etat n'a pas l'air confus genre d'abord; faisons comme Norman Ramsey a suggéré, et à pied à la façon de mettre en œuvre à partir de zéro. Attention, cela est assez long!

Tout d'abord, l'État a deux paramètres de type: le type de contient des données d'état et le type de résultat final du calcul . Nous allons utiliser stateData et result respectivement comme des variables de type pour eux ici. Cela est logique si vous pensez à ce sujet; la caractéristique d'un calcul basé État est qu'elle modifie un état tout en produisant un signal de sortie.

Moins évidente est que le constructeur de type prend une fonction d'un état à un état modifié et le résultat, comme suit:

newtype State stateData result = State (stateData -> (result, stateData))

Ainsi, alors que la monade est appelé « État », la valeur réelle enveloppée par la monade est celle de un calcul basé État , pas la valeur réelle de l'état contenu.

En gardant cela à l'esprit, nous ne devrions pas être surpris de constater que la fonction runState utilisée pour exécuter un calcul dans la monade de l'Etat est en fait rien de plus qu'un accesseur pour la fonction enveloppée elle-même, et peut être défini comme ceci:

runState (State f) = f

Alors, qu'est-ce que cela signifie lorsque vous définissez une fonction qui renvoie une valeur d'état? Ignorons un instant le fait que l'État est une monade, et il suffit de regarder les types sous-jacents. Considérons d'abord cette fonction (qui ne fait pas vraiment quoi que ce soit avec l'état):

len2State :: String -> State Int Bool
len2State s = return ((length s) == 2)

Si vous regardez la définition de l'Etat, nous pouvons voir que le type de l'stateData est Int, et le type de result est Bool, de sorte que la fonction enveloppée par le constructeur de données doit avoir le Int -> (Bool, Int) type. Maintenant, imaginez une version d'État moins len2State - De toute évidence, il aurait le type String -> Bool. Alors, comment voulez-vous aller sur la conversion d'une telle fonction en un retour d'une valeur qui s'insère dans un emballage de l'État?

Eh bien, évidemment, la fonction convertie devra prendre un second paramètre, un Int représentant la valeur d'état. Il a également besoin de retourner une valeur d'état, un autre Int. Étant donné que nous ne faisons pas quoi que ce soit avec l'Etat dans cette fonction, faisons juste la chose évidente - passe qui int droit à travers. Voici une fonction en forme de l'Etat, défini en termes de la version État moins:

len2 :: String -> Bool
len2 s = ((length s) == 2)

len2State :: String -> (Int -> (Bool, Int))
len2State s i = (len2' s, i)

Mais c'est un peu stupide et inutile. Généralisons la conversion pour que nous puissions passer la valeur du résultat, et tourner quoi que ce soit en fonction comme État.

convert :: Bool -> (Int -> (Bool, Int))
convert r d = (r, d)

len2 s = ((length s) == 2)

len2State :: String -> (Int -> (Bool, Int))
len2State s = convert (len2 s)

Et si nous voulons une fonction qui change l'état? Il est évident que nous ne pouvons pas construire un avec convert, puisque nous avons écrit que pour passer l'état à travers. Gardons simple et écrire une fonction pour remplacer l'état avec une nouvelle valeur. Quel genre de type aurait-il besoin? Il aura besoin d'un Int pour la nouvelle valeur d'état, et bien sûr devront retourner une stateData -> (result, stateData) fonction, parce que ce que nos besoins wrapper de l'État. Écrasement la valeur d'état n'a pas vraiment une valeur raisonnable result en dehors du calcul de l'Etat, donc notre résultat ici sera juste (), le tuple zéro élément qui représente « aucune valeur » dans Haskell.

overwriteState :: Int -> (Int -> ((), Int))
overwriteState newState _ = ((), newState)

C'était facile! Maintenant, en fait faire quelque chose avec ces données d'état. Réécrivons len2State d'en haut dans quelque chose de plus raisonnable. Nous allons comparer la longueur de chaîne à la valeur de l'état actuel

lenState :: String -> (Int -> (Bool, Int))
lenState s i = ((length s) == i, i)

Peut-on généraliser ce dans un convertisseur et une fonction moins d'Etat, comme nous l'avons fait avant? Pas tout à fait aussi facilement. Notre fonction len devra prendre l'Etat comme un argument, mais nous ne voulons pas de « connaître » l'état. Maladroits, en effet. Cependant, nous pouvons écrire une fonction d'assistance rapide qui gère tout pour nous: nous allons lui donner une fonction qui a besoind'utiliser la valeur d'état, et ça va passer la valeur et l'emballage puis tout remonter dans une fonction en forme de l'État ne laissant len le plus sage.

useState :: (Int -> Bool) -> Int -> (Bool, Int)
useState f d = (f d, d)

len :: String -> Int -> Bool
len s i = (length s) == i

lenState :: String -> (Int -> (Bool, Int))
lenState s = useState (len s)

Maintenant, la partie la plus délicate - si nous voulons chaîne ces fonctions ensemble? Disons que nous voulons utiliser lenState sur une chaîne, puis double la valeur d'état si le résultat est faux, puis vérifiez la chaîne à nouveau, et enfin revenir vrai si la vérification a fait. Nous avons toutes les pièces dont nous avons besoin pour cette tâche, mais il écrit tout en serait une douleur. Peut-on faire une fonction que les chaînes automatiquement ensemble deux fonctions que chaque retour des fonctions comme l'État? Chose sûre! Nous avons juste besoin pour vous assurer qu'il prend comme arguments deux choses: la fonction d'état retourné par la première fonction et une fonction qui prend le type result de fonction avant comme argument. Voyons voir comment il se trouve:

chainStates :: (Int -> (result1, Int)) -> (result1 -> (Int -> (result2, Int))) -> (Int -> (result2, Int))
chainStates prev f d = let (r, d') = prev d
                       in f r d'

Tout cela est fait application de la première fonction d'état à des données d'état, puis en appliquant la deuxième fonction au résultat et les données d'état modifiées. Simple, non?

Maintenant, la partie intéressante: Entre chainStates et convert, nous devrions presque pouvoir tourner toute combinaison de fonctions moins d'État en fonction activée-État! La seule chose dont nous avons besoin est maintenant un remplacement pour useState qui renvoie les données d'état comme résultat, de sorte que chainStates peut le transmettre aux fonctions qui ne connaissent rien au sujet de l'affaire nous tirer sur eux. Nous utiliserons également lambdas pour accepter le résultat des fonctions précédentes et leur donner des noms temporaires. D'accord, nous allons y arriver:

extractState :: Int -> (Int, Int)
extractState d = (d, d)

chained :: String -> (Int -> (Bool, Int))
chained str = chainStates  extractState         $ \state1 ->
              let check1 = (len str state1) in
              chainStates (overwriteState (
                  if check1 
                  then state1 
                  else state1 * 2))             $ \ _ ->
              chainStates  extractState         $ \state2 ->
              let check2 = (len str state2) in
              convert (check1 || check2)

Et essayer:

> chained "abcd" 2
(True, 4)
> chained "abcd" 3
(False, 6)
> chained "abcd" 4
(True, 4)
> chained "abcdef" 5
(False, 10)

Bien sûr, nous ne pouvons pas oublier que l'Etat est en fait une monade qui enveloppe les fonctions comme l'État et nous éloigne d'eux, donc aucune de nos fonctions astucieuses que nous avons construit nous aider à la vraie chose. Ou vont-ils? Dans une torsion choquant, il se trouve que la monade réelle de l'Etat fournit toutes les mêmes fonctions, sous différents noms:

runState (State s) = s
return r = State (convert r)
(>>=) s f = State (\d -> let (r, d') = (runState s) d in
                         runState (f r) d')
get = State extractState
put d = State (overwriteState d)

Notez que >> = est presque identique à chainStates, mais il n'y avait pas de bonne façon de le définir en utilisant chainStates. Donc, pour envelopper les choses, on peut réécrire l'exemple final en utilisant réel État:

chained str = get                               >>= \state1 ->
              let check1 = (len str state1) in
              put (if check1 
                  then state1 else state1 * 2)  >>= \ _ ->
              get                               >>= \state2 ->
              let check2 = (len str state2) in
              return (check1 || check2)

Ou, tout confite avec l'équivalent notation do:

chained str = do
        state1 <- get
        let check1 = len str state1
        _ <- put (if check1 then state1 else state1 * 2)
        state2 <- get
        let check2 = (len str state2)
        return (check1 || check2)

Answer 2

Tout d'abord, votre exemple est trop compliqué, car il n'a pas besoin de stocker le val dans la monade de l'État; que la semence est l'état persistant. Deuxièmement, je pense que vous aurez plus de chance si au lieu d'utiliser l'état standard monade, vous réimplémenter tous les monade de l'Etat et de ses opérations vous-même, avec leurs types. Je pense que vous en apprendrez plus de cette façon. Voici quelques déclarations pour vous aider à démarrer:

data MyState s a = MyState (s -> (s, b))

get :: Mystate s s
put :: s -> Mystate s ()

Ensuite, vous pouvez écrire vos propres conjonctions:

unit :: a -> Mystate s a
bind :: Mystate s a -> (a -> Mystate s b) -> Mystate s b

Enfin

data Seed = Seed Int
nextVal :: Mystate Seed Bool

---

En ce qui concerne votre désucrage trouble, la notation do que vous utilisez est assez sophistiqué. Mais désucrage est une procédure mécanique ligne par ligne à temps. Pour autant que je peux faire, votre code devrait desugar comme celui-ci (retour à vos types d'origine et le code qui je ne partage pas):

 nextVal = get >>= \ Random seed val ->
                      let seed' = updateSeed seed
                          val'  = even seed'
                      in  put (Random seed' val') >>= \ _ -> return val'

Afin de rendre la structure d'imbrication un peu plus clair, j'ai pris des libertés importantes relatives à l'indentation.

Answer 3

Vous avez un couple de grandes réponses. Ce que je fais lorsque vous travaillez avec la monade de l'Etat est dans mon esprit remplacer State s a avec s -> (s,a) (après tout, c'est vraiment ce qu'il est).

Vous obtenez alors un type de liaison qui ressemble à:

(>>=) :: (s -> (s,a)) ->
         (a -> s -> (s,b)) ->
         (s -> (s,b))

et vous voyez qui se lient est juste un type spécialisé de l'opérateur de composition de fonction, comme (.)

J'ai écrit un blog / tutoriel sur la monade de l'Etat ici . Il est sans doute pas particulièrement bon, mais m'a aidé à Grok choses un peu mieux en l'écrivant.