Haskell Language
Staatsmonade

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


Invoering

Staatsmonaden zijn een soort monade die een staat draagt die kan veranderen tijdens elke berekeningsrun in de monade. Implementaties hebben meestal de vorm State sa die een berekening vertegenwoordigt die een staat van type s draagt en mogelijk wijzigt en een resultaat van type a produceert, maar de term "staatsmonade" kan in het algemeen verwijzen naar elke monade die een staat draagt. Het mtl en transformers biedt algemene implementaties van staatsmonaden.

Opmerkingen

Nieuwkomers in Haskell schuwen de State vaak weg en behandelen het als een taboe - zoals het geclaimde voordeel van functioneel programmeren is het vermijden van staat, dus verlies je dat niet wanneer je State ? Een meer genuanceerd beeld is dat:

  • Status kan nuttig zijn in kleine, gecontroleerde doses ;
  • Het State biedt de mogelijkheid om de dosis zeer nauwkeurig te regelen.

De redenen zijn dat als je action :: State sa , dit je vertelt dat:

  • action is speciaal omdat het afhankelijk is van een staat;
  • De status heeft type s , dus action kan niet worden beïnvloed door een oude waarde in uw programma - alleen een s of een waarde die bereikbaar is vanaf sommige s ;
  • De runState :: State sa -> s -> (a, s) plaatst een "barrière" rond de stateful actie, zodat de effectiviteit ervan niet van buiten die barrière kan worden waargenomen.

Dus dit is een goede set criteria om State in een bepaald scenario te gebruiken. U wilt zien dat uw code het bereik van de status minimaliseert , zowel door een smal type voor s als door runState zo dicht mogelijk bij "the bottom" te plaatsen, (zodat uw acties door zo min mogelijk kunnen worden beïnvloed door mogelijk.

Nummering van de knooppunten van een boom met een teller

We hebben een boomgegevenstype zoals dit: 

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

En we willen een functie schrijven die een nummer toekent aan elke knoop van de boom, van een oplopende teller: 

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

De lange weg

Eerst zullen we het op de lange weg doen, omdat het de lage mechanica van de State heel goed illustreert. 

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

De teller opsplitsen in een postIncrement-actie

De bit waar we get Ting de huidige balie en vervolgens put ting teller + 1 kan gesplitst worden uitgeschakeld in een postIncrement actie, vergelijkbaar met wat veel C-stijl talen te bieden: 

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

Verdeel de boomgang in een hogere orde functie

De boomlooplogica kan als volgt worden opgesplitst in zijn eigen functie: 

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'

Hiermee en de functie postIncrement kunnen we tagStep herschrijven: 

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)

Gebruik de klasse Traversable

De bovenstaande mapTreeM oplossing kan eenvoudig worden herschreven in een instantie van de klasse Traversable : 

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

Merk op dat dit vereist dat we Applicative (de <*> operator) in plaats van Monad moesten gebruiken.

Daarmee kunnen we nu tag als een professional schrijven: 

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)

Merk op dat dit werkt voor elk Traversable type, niet alleen ons Tree type!

Weg met de Traversable boilerplate

GHC heeft een DeriveTraversable extensie die het schrijven van bovenstaande instantie overbodig maakt: 

{-# 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
Licentie onder CC BY-SA 3.0
Niet aangesloten bij Stack Overflow