Estado Mónada, secuencias de números aleatorios y el código monádico

Question

Estoy tratando de captar el estado mónada y con esta finalidad que quería escribir un código monádico que generaría una secuencia de números aleatorios usando un generador lineal de congruencia (probablemente no es buena, pero mi intención es sólo para aprender el Estado mónada, no construir una buena biblioteca RNG).

El generador es sólo esto (yo quiero para generar una secuencia de Bools para simplificar):

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 

No se preocupe por los números, esto es sólo una regla de actualización para la semilla que (según Numerical Recipes) debe generar una secuencia pseudo-aleatoria de Ints. Ahora, si quiero generar números aleatorios de forma secuencial que haría:

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, por lo que podría evitar esta repetitivo mediante el uso de una Mónada Estado:

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

Y por último:

getNRandSt n = replicateM n nextVal 

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

Ok, esto funciona muy bien y me da una lista de n Bools pseudo-aleatorios para cada semilla dado. Pero ...

Puedo leer lo que he hecho (principalmente en base a este ejemplo: http://www.haskell.org/pipermail/beginners/2008-September/000275.html ) y replicarlo para hacer otras cosas. Pero no creo que pueda entender lo que realmente está sucediendo detrás del do-notación y funciones monádicos (como replicateM).

¿Puede alguien ayudarme con algunas de estas dudas?

1 - He tratado de desugar la función nextval para entender lo que hace, pero no pude. Puedo adivinar que extrae el estado actual, lo actualiza y luego pasar el estado de cabeza en el próximo cálculo, pero esto es sólo basado en la lectura de este do-azúcar como si se tratara de Inglés.

¿Cómo realmente desugar esta función al original >> = y el retorno funciones paso a paso?

2 - No podía comprender lo que exactamente el put y get funciones hacen. Puedo adivinar que "pack" y "desempaquetar" el estado. Pero la mecánica detrás de la do-azúcar es siendo difícil de alcanzar para mí.

Bueno, cualquier otro observaciones generales sobre este código son muy bienvenidos. A veces me quedé con Haskell que puedo crear un código que funciona y hacer lo que espera que haga, pero no puedo "seguir la evaluación" ya que estoy acostumbrado a ver con programas imperativos.

Answer 1

La mónada Estado tiene un aspecto un poco confuso al principio; vamos a hacer como sugiere Norman Ramsey, y caminar a través de la forma de aplicar a partir de cero. Advertencia, esto es bastante larga!

En primer lugar, estado tiene dos parámetros de tipo: el tipo de los los datos de estado contenidas y el tipo de la resultado final del cálculo . Vamos a utilizar stateData y result, respectivamente, como variables de tipo para ellos aquí. Esto tiene sentido si se piensa en ello; la característica definitoria de un cálculo basado en Estado es que se modifica un estado mientras que produce una salida.

menos obvio es que el tipo de constructor toma una función desde un estado a un estado y resultado modificado, así:

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

Así, mientras que la mónada se llama "Estado", el valor real envuelta por el que la mónada es el de un cálculo basado en Estado , no el valor real del estado contenido.

Teniendo esto en mente, no hay que sorprenderse al encontrar que el runState función que se utiliza para ejecutar un cálculo en el Estado mónada es en realidad nada más que un descriptor de acceso para la misma función ajustada, y podría definirse así:

runState (State f) = f

Entonces, ¿qué quiere decir cuando se define una función que devuelve un valor de estado? Vamos a ignorar por un momento el hecho de que Estado es una mónada, y basta con ver los tipos subyacentes. En primer lugar, tenga en cuenta esta función (que en realidad no hace nada con el estado):

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

Si nos fijamos en la definición de Estado, podemos ver que aquí el tipo stateData es Int, y el tipo result es Bool, por lo que la función ajustada por el constructor de datos debe tener el tipo Int -> (Bool, Int). Ahora, imagina una versión menos Estado de len2State -, obviamente, tendría tipo String -> Bool. Entonces, ¿cómo haría usted para convertir una función de este tipo en una sola devolver un valor que encaja en un envoltorio de Estado?

Bueno, obviamente, la función convertida tendrá que tomar un segundo parámetro, un Int que representa el valor de estado. También tiene que devolver un valor de estado, otro Int. Puesto que no estamos realmente hacer nada con el estado de esta función, vamos a hacer lo obvio - que pase int justo en medio. Aquí está una función en forma de Estado, se define en términos de la versión menos Estado:

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

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

Pero eso es un poco tonto y redundante. Vamos a generalizar la conversión de manera que podemos pasar en el valor del resultado, y convertir cualquier cosa en una función de tipo estatal.

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)

¿Qué pasa si queremos una función que cambia el estado? Obviamente no podemos construir una con convert, ya escribimos que pase a través del estado. Vamos a mantenerlo simple, y escribir una función para sobrescribir el estado con un nuevo valor. ¿Qué clase de tipo sería lo necesita? Se va a necesitar un Int para el nuevo valor de estado, y por supuesto tendrá que devolver un stateData -> (result, stateData) función, porque eso es lo que necesita nuestra envoltura del Estado. Sobrescribir el valor de estado no tiene realmente un valor result sensata fuera del cómputo Estado, por lo que nuestro resultado aquí sólo se (), la tupla-elemento cero que representa "ningún valor" en Haskell.

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

Eso fue fácil! Ahora, vamos a realidad hacer algo con el que los datos de estado. Vamos a reescribir len2State desde arriba en algo más sensata:. Vamos a comparar la longitud de la cadena de valor de estado actual

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

¿Podemos generalizar esta en un convertidor y una función menos Estado, como lo hicimos antes? No es tan fácil. Nuestra función len tendrá que tomar al Estado como un argumento, pero no quiere que se "sabe de" estado. Torpe, de hecho. Sin embargo, podemos escribir una función de ayuda rápida que se encarga de todo para nosotros: vamos a darle una función que necesitautilizar el valor de estado, y que va a pasar en el valor y luego empaquetar todo de reserva en una función en forma de Estado dejando len sin enterarse.

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)

Ahora, la parte difícil - lo que si queremos cadena de estas funciones juntos? Digamos que queremos utilizar lenState en una cadena y luego doblar el valor de estado si el resultado es falso, a continuación, comprobar la cadena de nuevo, y finalmente de vuelta verdad, si bien hizo cheque. Tenemos todas las piezas que necesitamos para esta tarea, pero escribir todo hacia fuera sería un dolor. Podemos hacer una función que automáticamente cadenas juntos dos funciones que cada retorno de funciones propias del Estado? ¡Cosa segura! Sólo necesitamos para asegurarse de que toma como argumentos dos cosas: la función de estado devuelto por la primera función, y una función que toma el tipo result de la función anterior como un argumento. Vamos a ver cómo resulta:

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

Todo esto está haciendo es aplicar la primera función de estado a algunos datos de estado, a continuación, aplicar la segunda función para el estado de los datos modificados resultado y. Simple, ¿verdad?

Ahora, la parte interesante: Entre chainStates y convert, debemos casi ser capaz de convertir cualquier combinación de las funciones estatales menos en una función activada por el Estado! Lo único que necesitamos ahora es un reemplazo para useState que devuelve los datos de estado como su resultado, de manera que chainStates pueden pasar a lo largo de las funciones que no saben nada sobre el truco que estamos tirando de ellos. Además, vamos a utilizar lambdas a aceptar el resultado de las funciones anteriores y darles nombres temporales. Bueno, vamos a hacer que esto ocurra:

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)

Y probarlo:

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

Por supuesto, no podemos olvidar que el Estado es en realidad una mónada que envuelve las funciones propias del Estado y nos mantiene lejos de ellos, por lo que ninguna de nuestras funciones ingeniosas que hemos construido nos ayudará con la cosa real. O lo harán? En un giro sorprendente, resulta que la mónada estado real proporciona las mismas funciones, bajo diferentes nombres:

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)

Tenga en cuenta que >> = es casi idéntica a chainStates, pero no había una buena manera de definirla usando chainStates. Por lo tanto, para envolver las cosas, podemos reescribir el ejemplo final utilizando el real Estado:

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)

O, todo confitada con el equivalente a hacer la notación:

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

En primer lugar, su ejemplo es excesivamente complicado, ya que no necesita almacenar el val en el estado mónada; Sólo la semilla es el estado persistente. En segundo lugar, creo que va a tener mejor suerte si en lugar de utilizar la mónada estado estándar, se vuelve a poner en práctica toda la mónada estado y sus operaciones por sí mismo, con sus tipos. Creo que va a aprender más de esta manera. Aquí hay un par de declaraciones para empezar:

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

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

A continuación, puede escribir sus propios conectores:

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

Finalmente

data Seed = Seed Int
nextVal :: Mystate Seed Bool

---

En cuanto a su desugaring problemas, la notación do que está utilizando es bastante sofisticado. Pero desugaring es un procedimiento mecánico de alineación en-un-tiempo. Lo más cerca que he podido averiguar, el código debe desugar como esto (que se remonta a los tipos de originales y el código, lo que no estoy de acuerdo con):

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

Con el fin de hacer que la estructura de anidación un poco más claro, he tomado grandes libertades con la sangría.

Answer 3

Tienes un par de grandes respuestas. Lo que hago cuando se trabaja con la mónada Estado está en mi mente reemplazar State s a con s -> (s,a) (después de todo, eso es realmente lo que es).

A continuación, obtener un tipo de vinculación que se ve así:

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

y ves que se unen es sólo un tipo especializado de la función de operador de composición, como (.)

escribí un blog / tutorial sobre la mónada estado aquí . Probablemente no es particularmente buena, pero me ayudó a asimilo las cosas un poco mejor escribiéndolo.