Haskell Language
Mónada del estado

algorithm C Language C++ clojure F# Java Language GNU/Linux Python Language Regular Expressions Scala Language
Buscar..


Introducción

Las mónadas estatales son un tipo de mónada que llevan un estado que puede cambiar durante cada ejecución de cálculo en la mónada. Las implementaciones son generalmente de la forma State sa que representa un cálculo que lleva y potencialmente modifica un estado de tipo s y produce un resultado de tipo a , pero el término "mónada de estado" generalmente se refiere a cualquier mónada que lleva un estado. El paquete mtl y transformers proporciona implementaciones generales de mónadas estatales.

Observaciones

Los recién llegados a Haskell a menudo se alejan de la mónada State y la tratan como un tabú, ya que el beneficio declarado de la programación funcional es evitar el estado, así que, ¿no lo pierde cuando usa State ? Una vista más matizada es que:

  • El estado puede ser útil en pequeñas dosis controladas ;
  • El tipo de State proporciona la capacidad de controlar la dosis con mucha precisión.

Las razones son que si tienes action :: State sa , esto te dice que:

  • action es especial porque depende de un estado;
  • El estado tiene el tipo s , por lo que la action no puede verse influenciada por ningún valor antiguo en su programa; solo se puede acceder a una s o algún valor desde algunos s ;
  • El runState :: State sa -> s -> (a, s) pone una "barrera" alrededor de la acción con estado, de modo que su efectividad no se puede observar desde fuera de esa barrera.

Por lo tanto, este es un buen conjunto de criterios para utilizar el State en un escenario particular. Quiere ver que su código está minimizando el alcance del estado , tanto al elegir un tipo estrecho para s como al poner runState más cerca posible al "fondo" (para que sus acciones puedan verse influidas por tan pocas cosas como posible.

Numerar los nodos de un árbol con un contador.

Tenemos un tipo de datos de árbol como este: 

data Tree a = Tree a [Tree a] deriving Show

Y deseamos escribir una función que asigne un número a cada nodo del árbol, desde un contador incremental: 

tag :: Tree a -> Tree (a, Int)

El largo camino

Primero lo haremos a lo largo, ya que ilustra muy bien la mecánica de bajo nivel de la mónada State . 

import Control.Monad.State

-- Function that numbers the nodes of a `Tree`.
tag :: Tree a -> Tree (a, Int)
tag tree = 
    -- tagStep is where the action happens.  This just gets the ball
    -- rolling, with `0` as the initial counter value.
    evalState (tagStep tree) 0

-- This is one monadic "step" of the calculation.  It assumes that
-- it has access to the current counter value implicitly.
tagStep :: Tree a -> State Int (Tree (a, Int))
tagStep (Tree a subtrees) = do
    -- The `get :: State s s` action accesses the implicit state
    -- parameter of the State monad.  Here we bind that value to
    -- the variable `counter`.
    counter <- get 

    -- The `put :: s -> State s ()` sets the implicit state parameter
    -- of the `State` monad.  The next `get` that we execute will see
    -- the value of `counter + 1` (assuming no other puts in between).
    put (counter + 1)

    -- Recurse into the subtrees.  `mapM` is a utility function
    -- for executing a monadic actions (like `tagStep`) on a list of
    -- elements, and producing the list of results.  Each execution of 
    -- `tagStep` will be executed with the counter value that resulted
    -- from the previous list element's execution.
    subtrees' <- mapM tagStep subtrees  

    return $ Tree (a, counter) subtrees'

Refactorización

Dividir el contador en una acción postIncrement

La parte en la que nos encontramos get ting el contador actual y luego put ting contador + 1 se puede separar en una postIncrement acción, similar a lo que muchos lenguajes de tipo C proporcionan: 

postIncrement :: Enum s => State s s
postIncrement = do
    result <- get
    modify succ
    return result

Divide la caminata del árbol en una función de orden superior.

La lógica de la caminata del árbol se puede dividir en su propia función, como esta: 

mapTreeM :: Monad m => (a -> m b) -> Tree a -> m (Tree b)
mapTreeM action (Tree a subtrees) = do
    a' <- action a
    subtrees' <- mapM (mapTreeM action) subtrees
    return $ Tree a' subtrees'

Con esto y la función postIncrement podemos reescribir tagStep : 

tagStep :: Tree a -> State Int (Tree (a, Int))
tagStep = mapTreeM step
    where step :: a -> State Int (a, Int)
          step a = do 
              counter <- postIncrement
              return (a, counter)

Usa la clase Traversable

La solución mapTreeM anterior se puede reescribir fácilmente en una instancia de la clase Traversable : 

instance Traversable Tree where
    traverse action (Tree a subtrees) = 
        Tree <$> action a <*> traverse action subtrees

Tenga en cuenta que esto nos obligó a utilizar Applicative (el operador <*> ) en lugar de Monad .

Con eso, ahora podemos escribir tag como un profesional: 

tag :: Traversable t => t a -> t (a, Int)
tag init t = evalState (traverse step t) 0
    where step a = do tag <- postIncrement
                      return (a, tag)

¡Tenga en cuenta que esto funciona para cualquier tipo de Traversable , no solo para nuestro tipo de Tree !

Deshacerse de la Traversable desplazamiento de Traversable

GHC tiene una extensión DeriveTraversable que elimina la necesidad de escribir la instancia anterior: 

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

data Tree a = Tree a [Tree a]
            deriving (Show, Functor, Foldable, Traversable)


Modified text is an extract of the original Stack Overflow Documentation
Licenciado bajo CC BY-SA 3.0
No afiliado a Stack Overflow