haskell monads state-monad

Confusión sobre el código de la mónada estatal en "Learn you a Haskell"



monads state-monad (4)

Estoy tratando de entender Haskell usando el libro en línea Learn you a Haskell for great Good .

Según mi conocimiento, he podido entender las mónadas hasta que llegué al capítulo de introducción de la mónada estatal .

Sin embargo, el código presentado y que afirma ser la implementación de Monad del tipo de Estado (no he podido ubicarlo en Hoogle) parece demasiado para mí.

  • Para empezar, no entiendo la lógica detrás de esto, es decir, por qué debería funcionar y cómo el autor consideró esta técnica (¿se pueden sugerir artículos relevantes o artículos técnicos?)

  • En la línea 4, se sugiere que la función f toma 1 parámetro.
    Sin embargo, unas pocas líneas hacia abajo se nos presenta con pop, que no tiene parámetros!

  • Para extenderse en el punto 1, ¿qué está tratando de lograr el autor utilizando una función para representar al Estado?

Cualquier ayuda para entender lo que está pasando es muy apreciada.

Editar

A quien le interese,

Las respuestas a continuación cubren mi pregunta a fondo.
Una cosa que me gustaría agregar sin embargo:

Después de leer un artículo sugerido a continuación, encontré la respuesta a mi segundo punto anterior: durante todo ese tiempo asumí que la función pop se usaría como:
stuff >>= pop ya que en el tipo de enlace el segundo parámetro es la función, mientras que el uso correcto es este pop >>= stuff , lo que me di cuenta después de leer de nuevo cómo se traduce la notación a la simple bind-lambdas.

La mónada State es esencialmente

type State s a = s -> (a,s)

una función de un estado ( s ) a un par del resultado deseado ( a ) y un nuevo estado. La implementación hace que el subproceso del estado sea implícito y maneja el paso y la actualización del estado por usted, por lo que no hay riesgo de pasar accidentalmente el estado incorrecto a la siguiente función.

Por lo tanto, una función que toma k > 0 argumentos, uno de los cuales es un estado y devuelve un par de algo y un nuevo estado, en la mónada del State s convierte en una función que toma k-1 argumentos k-1 y devuelve una acción monádica (que básicamente es una función tomando un argumento, el estado, aquí).

En la configuración no estatal, pop toma un argumento, la pila, que es el estado. Por lo tanto, en el entorno monádico, el pop convierte en una acción de State Stack Int que no tiene argumentos explícitos.

El uso de la mónada State lugar de un pase de estado explícito permite un código más limpio con menos oportunidades de error, eso es lo que logra la mónada State . Todo se podría hacer sin él, simplemente sería más engorroso y propenso a errores.

La mónada State representa cálculos con estado, es decir, cálculos que utilizan valores de, y tal vez modifican, algún estado externo. Cuando secuencia los cálculos con estado juntos, los cálculos posteriores pueden dar resultados diferentes dependiendo de cómo los cálculos anteriores modificaron el estado.

Como las funciones en Haskell deben ser puras (es decir, no tienen efectos secundarios), simulamos el efecto del estado externo exigiendo que cada función tome un parámetro adicional que represente el estado actual del mundo y devuelva un valor adicional, que represente el estado modificado. En efecto, el estado externo se transmite a través de una secuencia de cálculos, como en esta abominación de un diagrama que acabo de dibujar en MSPaint:

Observe cómo cada caja (que representa un cálculo) tiene una entrada y dos salidas.

Si observa la instancia de Monad para el State , verá que la definición de (>>=) le indica cómo realizar este proceso. Dice que para vincular un cálculo con estado c0 a una función f que toma los resultados de un cálculo con estado y devuelve otro cálculo con estado, hacemos lo siguiente:

  1. Ejecute c0 utilizando el estado inicial s0 para obtener un resultado y un nuevo estado: (val, s1)
  2. Alimente val a la función f para obtener un nuevo cálculo con estado, c1
  3. Ejecutar el nuevo cálculo c1 con el estado modificado s1

¿Cómo funciona esto con funciones que ya toman n argumentos? Debido a que todas las funciones en Haskell tienen un currículum de forma predeterminada, simplemente agregamos un argumento adicional (para el estado) al final, y en lugar del valor de retorno normal, la función ahora devuelve un par cuyo segundo elemento es el estado recién modificado. Así que en lugar de

f :: a -> b

ahora tenemos

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

Podrías elegir pensar como

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

que es lo mismo en Haskell (ya que la composición de la función es asociativa a la derecha) que dice " f es una función que toma un argumento de tipo a y devuelve un cálculo con estado". Y eso es realmente todo lo que hay en la mónada State .

Soy un novato total de Haskell y no pude entender bien el código de State Monad en ese libro, también. Pero permítame agregar mi respuesta aquí para ayudar a alguien en el futuro.

Respuestas:

  • ¿Qué están tratando de lograr con la mónada estatal?

    Componiendo funciones que manejan computación con estado.
    por ejemplo, push 3 >>= /_ -> push 5 >>= /_ -> pop

  • ¿Por qué pop no toma parámetros, mientras que se sugiere la función f toma 1 parámetro?

    pop no toma argumentos porque está envuelto por el State .
    la función no adaptada cuyo tipo es s -> (a, s) toma un argumento. Lo mismo ocurre con el push .
    puedes desenvolver con runState .

    runState pop :: Stack -> (Int, Stack) runState (push 3) :: Stack -> ((), Stack)

    si te refieres al lado derecho de la >>= con la "función f ", la f será como /a -> pop o /a -> push 3 , no solo pop .


Explicación larga:

Estas 3 cosas me ayudaron a entender un poco más el ejemplo de State Monad y el ejemplo de Stack.

  • Considere los tipos de argumentos para el operador de enlace ( >>= )

    La definición del operador bind en Monad typeclass es esta

    (>>=) :: (Monad m) => m a -> (a -> m b) -> m b

    En el ejemplo de Stack, m es State Stack .
    Si mentalmente reemplazamos m con State Stack , la definición puede ser así.

    (>>=) :: State Stack a -> (a -> State Stack b) -> State Stack b

    Por lo tanto, el tipo de argumento del lado izquierdo para el operador de vinculación será State Stack a .
    Y el del lado derecho será a -> State Stack b .

  • Traducir notación a operador de enlace

    Aquí está el código de ejemplo usando notación do en el libro.

    stackManip :: State Stack Int stackManip = do push 3 pop pop

    Se puede traducir al siguiente código con el operador de enlace.

    stackManip :: State Stack Int stackManip = push 3 >>= /_ -> pop >>= /_ -> pop

    Ahora podemos ver cuál será el lado derecho del operador de enlace.
    Sus tipos son a -> State Stack b .

    (/_ -> pop) :: a -> State Stack Int (/_ -> push 3) :: a -> State Stack ()


  • Reconocer la diferencia entre (State s) y (State h) en la declaración de instancia

    Aquí está la declaración de instancia para el Estado en el libro.

    instance Monad (State s) where return x = State $ /s -> (x,s) (State h) >>= f = State $ /s -> let (a, newState) = h s (State g) = f a in g newState

    Teniendo en cuenta los tipos con el ejemplo de pila, el tipo de (State s) será

    (State s) :: State Stack s :: Stack

    Y el tipo de (State h) será

    (State h) :: State Stack a h :: Stack -> (a, Stack)

    (State h) es el argumento del lado izquierdo del operador de enlace y su tipo es State Stack a como se describe anteriormente.

    Entonces, ¿por qué h convierte en Stack -> (a, Stack) ?
    Es el resultado de la comparación de patrones con el constructor de valores de estado que se define en el envoltorio newtype. Lo mismo ocurre con el (State g) .

    newtype State s a = State { runState :: s -> (a,s) }

    En general, el tipo de h es s ->(a, s) , representación del cálculo con estado. Cualquiera de los siguientes podría ser la h en el ejemplo de pila.

    runState pop :: Stack -> (Int, Stack) runState (push 3) :: Stack -> ((), Stack) runState stackManip :: Stack -> (Int, Stack)

    Eso es.

Respuesta corta:

  1. Se pretende que el estado explote las características de las mónadas para simular un estado de sistema similar a un imperativo con variables locales. La idea básica es ocultar dentro de la mónada la actividad de tomar el estado actual y devolver el nuevo estado junto con un resultado intermedio en cada paso (y aquí tenemos s -> (a,s) .
  2. No confunda las funciones arbitrarias con las envueltas dentro del State . El primero puede tener el tipo que desee (siempre que produzcan algún State a si quiere usarlos en la mónada estatal). El último tiene funciones de tipo s -> (a,s) : esta es la capa de paso de estado administrada por la mónada.
  3. Como dije, la función envuelta dentro del State realidad se produce por medio de (>>=) y se return tal como están definidas para la instancia de Monad (State s) . Su función es transmitir el estado a través de las llamadas de su código.

El punto 3 también es la razón por la cual el parámetro de estado desaparece de las funciones realmente utilizadas en la mónada de estado.

Respuesta larga:

La Mónada del estado se ha estudiado en diferentes artículos y existe también en el marco de Haskell (no recuerdo las buenas referencias en este momento, las agregaré lo antes posible).

Esta es la idea que sigue: considere un tipo de data MyState = ... cuyos valores mantienen el estado actual del sistema.

Si desea pasarlo a través de un grupo de funciones, debe escribir cada función de tal manera que tome al menos el estado actual como parámetro y le devuelva un par con su resultado (dependiendo del estado y la otra entrada). parámetros) y el nuevo estado (posiblemente modificado). Bueno, esto es exactamente lo que el tipo de estado de la mónada le dice: s -> (a, s) . En nuestro ejemplo, s es MyState y está destinado a transmitir el estado del sistema.

La función envuelta en el State no toma parámetros, excepto del estado actual, que es necesario para producir como resultado el nuevo estado y un resultado intermedio. Las funciones con más parámetros que viste en los ejemplos no son un problema, porque cuando los usas en la notación de do dentro de la mónada, los aplicarás a todos los parámetros "extra" necesarios, lo que significa que cada uno de ellos resulta en una función parcialmente aplicada cuyo único parámetro restante es el estado; La instancia de la mónada para el State hará el resto.

Si observa el tipo de funciones (en realidad, dentro de las mónadas se denominan acciones) que se pueden usar en la mónada, verá que el tipo de resultado está encuadrado dentro de la mónada: este es el punto que le indica que una vez que les asigna todos los parámetros, en realidad no le devolverán el resultado, sino que (en este caso) una función s -> (a,s) que se ajustará a las leyes de composición de la mónada.

El cálculo se ejecutará pasando a todo el bloque / composición el primer estado inicial del sistema.

Finalmente, las funciones que no toman parámetros tendrán un tipo como State a donde a es su tipo de retorno: si observa el constructor de valores para State , verá nuevamente que esta es en realidad una función s -> (a,s) .