Haskell Language
State Monad

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


Introduktion

Statliga monader är en typ av monad som bär ett tillstånd som kan förändras under varje beräkningskörning i monaden. Implementeringar är vanligtvis av formen State sa som representerar en beräkning som bär och potentiellt modifierar ett tillstånd av typ s och ger ett resultat av typ a , men termen "state monad" kan vanligtvis hänvisa till alla monader som bär ett tillstånd. Paketet mtl och transformers ger generella implementeringar av statliga monader.

Anmärkningar

Nykomlingar till Haskell skymmer ofta bort från State monad och behandlar det som ett tabu - som den påstådda fördelen med funktionell programmering är att undvika stat, så förlorar du inte det när du använder State ? En mer nyanserad vy är att:

  • Tillstånd kan vara användbart i små, kontrollerade doser ;
  • State ger möjlighet att kontrollera dosen mycket exakt.

Orsakerna är att om du har action :: State sa , säger detta att:

  • action är speciell eftersom den beror på ett tillstånd;
  • Tillståndet har typ s , så action kan inte påverkas av något gammalt värde i ditt program - endast ett s eller något värde som kan nås från några s ;
  • runState :: State sa -> s -> (a, s) sätter en "barriär" runt den statliga åtgärden, så att dess effektivitet inte kan observeras utanför denna barriär.

Så detta är en bra uppsättning kriterier för att använda State i ett särskilt scenario. Du vill se att din kod minimerar räckvidden för tillståndet , både genom att välja en smal typ för s och genom att sätta runState så nära "botten" som möjligt, (så att dina handlingar kan påverkas av så få saker som möjlig.

Numrering av noderna på ett träd med en räknare

Vi har en träddatatyp som denna: 

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

Och vi vill skriva en funktion som tilldelar ett nummer till varje nod i trädet, från en stegvis räknare: 

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

Den långa vägen

Först ska vi göra det den långa vägen runt, eftersom det visar State monadens låg nivå mekanik ganska snyggt. 

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

Dela ut räknaren i en postincrement-åtgärd

Den bit där vi get klicka på den aktuella räknaren och sedan put tingräknare + 1 kan delas upp i en postIncrement åtgärd, liknande det som många språk i C-stil ger: 

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

Dela upp trädet till en högre ordning

Trädvandringslogiken kan delas upp i sin egen funktion, så här: 

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'

Med denna och postIncrement funktionen kan vi skriva om 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)

Använd klassen Traversable

mapTreeM lösningen ovan kan enkelt skrivas om till en instans av klassen Traversable : 

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

Observera att detta kräver att vi använder Applicative ( <*> operatören) istället för Monad .

Med det kan vi nu skriva tag som en proff: 

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)

Observera att detta fungerar för alla Traversable typ, inte bara vår Tree typ!

Bli av med Traversable pannplattan

GHC har en DeriveTraversable förlängning som eliminerar behovet av att skriva instansen ovan: 

{-# 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
Licensierat under CC BY-SA 3.0
Inte anslutet till Stack Overflow