Haskell Language
Etat Monad

algorithm C Language C++ clojure F# Java Language GNU/Linux Python Language Regular Expressions Scala Language
Recherche…


Introduction

Les monades d'état sont une sorte de monade qui porte un état qui peut changer pendant chaque calcul effectué dans la monade. Les implémentations sont généralement de la forme State sa qui représente un calcul qui porte et modifie potentiellement un état de type s et produit un résultat de type a , mais le terme "état monade" peut généralement se référer à toute monade qui porte un état. Le mtl et transformers fournit des implémentations générales de monades d'état.

Remarques

Les nouveaux arrivants à Haskell ont souvent peur de la monade de l' State et la traitent comme un tabou. Comme le prétendu avantage de la programmation fonctionnelle est l'évitement de l'état, ne perdez-vous pas cela lorsque vous utilisez State ? Une vue plus nuancée est que:

  • L'état peut être utile en petites doses contrôlées ;
  • Le type d' State permet de contrôler la dose très précisément.

Les raisons étant que si vous avez l' action :: State sa , cela vous dit que:

  • action est spéciale car elle dépend d'un état;
  • L'état a le type s , donc l' action ne peut pas être influencée par une ancienne valeur de votre programme - seulement une valeur s ou une valeur accessible depuis certains s ;
  • Le runState :: State sa -> s -> (a, s) place une "barrière" autour de l'action avec état, de sorte que son efficacité ne peut pas être observée en dehors de cette barrière.

Il s’agit donc d’un bon ensemble de critères pour savoir s’il faut utiliser l’ State dans un scénario particulier. Vous voulez voir que votre code minimise la portée de l’état , à la fois en choisissant un type étroit pour s et en plaçant runState plus près possible du "bas" (afin que vos actions puissent être aussi peu influencées que possible). possible.

Numérotation des nœuds d'un arbre avec un compteur

Nous avons un type de données arborescent comme ceci: 

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

Et nous souhaitons écrire une fonction qui attribue un numéro à chaque nœud de l’arbre, à partir d’un compteur incrémenté: 

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

Le long chemin

D' abord , nous le ferons long chemin, car il illustre l' State tout à fait bien la mécanique à faible niveau de monades. 

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'

Refactoring

Diviser le compteur en une action postIncrement

Le bit où nous get le compteur actuel puis put compteur + 1 peut être divisé en une action postIncrement , similaire à ce que de nombreux langages de style C fournissent: 

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

Diviser l'arbre en une fonction d'ordre supérieur

La logique de parcours d'arbre peut être divisée en sa propre fonction, comme ceci: 

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'

Avec ceci et la fonction postIncrement , nous pouvons réécrire 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)

Utilisez la classe Traversable

La solution mapTreeM ci-dessus peut être facilement réécrite dans une instance de la classe Traversable : 

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

Notez que cela nous a obligé à utiliser Applicative (l'opérateur <*> ) au lieu de Monad .

Avec ça, maintenant on peut écrire tag comme un pro: 

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)

Notez que cela fonctionne pour n'importe quel type Traversable , pas seulement notre type d' Tree !

Se débarrasser du passe-partout Traversable

GHC a une extension DeriveTraversable qui élimine le besoin d'écrire l'instance ci-dessus: 

{-# 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
Sous licence CC BY-SA 3.0
Non affilié à Stack Overflow