suma - pedir valores en haskell

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

Question

Estoy tratando de captar la Mónada estatal y con este propósito quería escribir un código monádico que generaría una secuencia de números aleatorios utilizando un generador lineal congruente (probablemente no es bueno, pero mi intención es aprender la mónada estatal, no construir una buena biblioteca RNG).

El generador es solo esto (quiero generar una secuencia de Bool s por simplicidad):

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, esta es solo una regla de actualización para la semilla que (según Recetas numéricas) debe generar una secuencia pseudoaleatoria de Int s. Ahora, si quiero generar números aleatorios secuencialmente lo 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, así que podría evitar esta repetición usando una mónada estatal:

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 finalmente:

getNRandSt n = replicateM n nextVal 

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

Ok, esto funciona bien y dame una lista de n Bools pseudo-aleatorias para cada semilla dada. Pero...

Puedo leer lo que he hecho (basado principalmente en 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 sucede detrás de las funciones de notación y monádica (como replicateM).

¿Alguien puede 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 lo pasa al siguiente cálculo, pero esto se basa en la lectura de este do-sugar como si fuera inglés.

¿Cómo desugar realmente esta función a las funciones originales >> = y de retorno paso a paso?

2 - No pude entender qué hacen exactamente las funciones de put y get . Puedo adivinar que "empaquetan" y "desempaquetan" el estado. Pero la mecánica detrás del do-sugar todavía es difícil de alcanzar.

Bueno, cualquier otra observación general sobre este código es muy bienvenida. A veces me he dado cuenta de que con Haskell puedo crear un código que funcione y hacer lo que espero que haga, pero no puedo "seguir la evaluación", como estoy acostumbrado a hacer con los programas imperativos.

Answer 1

En primer lugar, su ejemplo es demasiado complicado porque no necesita almacenar el val en la mónada estatal; Sólo la semilla es el estado persistente. En segundo lugar, creo que tendrá más suerte si, en lugar de utilizar la mónada estándar del estado, vuelva a implementar toda la mónada estatal y sus operaciones, con sus tipos. Creo que aprenderás más de esta manera. Aquí hay un par de declaraciones para comenzar:

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

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

Entonces puedes escribir tus propios conectivos:

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 los problemas de desugar, la notación que está utilizando es bastante sofisticada. Pero desugaring es un procedimiento mecánico de línea a vez. Hasta donde puedo descifrar, su código debería desugarse así (volviendo a sus tipos y código originales, con los que no estoy de acuerdo):

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

Para hacer que la estructura de anidación sea un poco más clara, me he tomado grandes libertades con la sangría.

Answer 2

La mónada estatal parece un poco confusa al principio; hagamos lo que Norman Ramsey sugirió y veamos cómo implementar desde cero. ¡Advertencia, esto es bastante largo!

Primero, el estado tiene dos parámetros de tipo: el tipo de los datos de estado contenidos y el tipo del resultado final del cálculo . Usaremos stateData y result respectivamente como variables de tipo para ellos aquí. Esto tiene sentido si lo piensas; La característica definitoria de un cálculo basado en estado es que modifica un estado mientras produce una salida.

Menos obvio es que el constructor de tipos toma una función de un estado a un estado modificado y el resultado, de este modo:

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

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

Teniendo esto en cuenta, no deberíamos sorprendernos al encontrar que la función runState utilizada para ejecutar un cálculo en la mónada estatal en realidad no es más que un elemento de acceso para la propia función envuelta, y podría definirse así:

runState (State f) = f

Entonces, ¿qué significa cuando define una función que devuelve un valor de Estado? Ignoremos por un momento el hecho de que el Estado es una mónada, y solo miremos los tipos subyacentes. Primero, considere 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 de result es Bool , por lo que la función envuelta por el constructor de datos debe tener el tipo Int -> (Bool, Int) . Ahora, imagine una versión sin estado de len2State obviamente, tendría el tipo String -> Bool . Entonces, ¿cómo haría para convertir una función de este tipo en una que devuelva un valor que se ajuste a una envoltura estatal?

Bueno, obviamente, la función convertida tendrá que tomar un segundo parámetro, un Int represente el valor del estado. También necesita devolver un valor de estado, otro Int . Como en realidad no estamos haciendo nada con el estado en esta función, solo hagamos lo obvio: pasarlo por completo. Aquí hay una función con forma de estado, definida en términos de la versión sin 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. Generalicemos la conversión para que podamos pasar el valor del resultado y convertir cualquier cosa en una función similar a un estado.

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 uno con convert , ya que escribimos eso para pasar el estado. Mantengámoslo simple y escribamos una función para sobrescribir el estado con un nuevo valor. ¿Qué tipo de tipo necesitaría? Necesitará un Int para el nuevo valor de estado y, por supuesto, tendrá que devolver una función stateData -> (result, stateData) , porque eso es lo que necesita nuestra envoltura estatal. Sobrescribir el valor del estado realmente no tiene un valor de result razonable fuera del cálculo del estado, por lo que nuestro resultado aquí será simplemente () , la tupla de elemento cero que representa "sin valor" en Haskell.

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

¡Eso fue fácil! Ahora, hagamos algo con los datos de ese estado. Reescribamos len2State desde arriba en algo más sensato: compararemos la longitud de la cadena con el valor del estado actual.

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

¿Podemos generalizar esto en un convertidor y una función sin estado, como hicimos antes? No tan fácil. Nuestra función len tendrá que tomar el estado como un argumento, pero no queremos que sepa sobre el estado. Torpe, por cierto. Sin embargo, podemos escribir una función de ayuda rápida que maneje todo por nosotros: le daremos una función que necesita usar el valor de estado, y pasará el valor y luego empaquetaremos todo de nuevo en una función con forma de estado. dejando a len ninguno el más sabio.

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: ¿qué pasa si queremos unir estas funciones? Digamos que queremos usar lenState en una cadena, luego duplicar el valor del estado si el resultado es falso, luego verificar la cadena nuevamente y finalmente devolver el valor verdadero si alguna de las verificaciones lo hizo. Tenemos todas las partes que necesitamos para esta tarea, pero escribir todo sería un dolor. ¿Podemos realizar una función que automáticamente encadene dos funciones para que cada una retorne funciones similares a un estado? ¡Cosa segura! Solo debemos asegurarnos de que tome como argumentos dos cosas: la función de Estado devuelta por la primera función y una función que toma el tipo de result la función anterior como un argumento. Veamos 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 lo que está haciendo es aplicar la primera función de estado a algunos datos de estado, luego aplicar la segunda función al resultado y los datos de estado modificados. Simple, ¿verdad?

Ahora, la parte interesante: entre chainStates y chainStates , ¡casi podríamos convertir cualquier combinación de funciones sin estado en una función habilitada por el estado! Lo único que necesitamos ahora es un reemplazo para useState que devuelva los datos del estado como su resultado, para que chainStates pueda pasarlo a las funciones que no saben nada sobre el truco que estamos haciendo. Además, usaremos lambdas para aceptar el resultado de las funciones anteriores y darles nombres temporales. De acuerdo, hagamos que esto suceda:

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 pruébalo

> 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 similares a las del Estado y nos mantiene alejados de ellas, por lo que ninguna de nuestras funciones ingeniosas que hemos construido nos ayudará con la realidad. ¿O lo harán? En un giro sorprendente, resulta que la mónada de estado real proporciona las mismas funciones, con 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éntico a chainStates, pero no había una buena manera de definirlo usando chainStates. Entonces, para resumir, podemos reescribir el ejemplo final utilizando el estado real :

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 bien, todos confitados con la notación equivalente 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 3

Tienes un par de respuestas geniales. Lo que hago cuando trabajo con la mónada estatal es, en mi mente, reemplazar el State sa con s -> (s,a) (después de todo, eso es realmente lo que es).

A continuación, obtiene un tipo de enlace que se parece a:

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

y ves que bind es solo un tipo especializado de operador de composición de funciones, como (.)

Escribí un blog / tutorial sobre la mónada estatal here . Probablemente no sea particularmente bueno, pero me ayudó a asimilar las cosas un poco mejor al escribirlas.