Haskell Language
Stato Monad

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


introduzione

Le monadi di stato sono una sorta di monade che trasportano uno stato che potrebbe cambiare durante ogni computazione eseguita nella monade. Le implementazioni sono solitamente di forma State sa che rappresenta un calcolo che trasporta e potenzialmente modifica uno stato di tipo s e produce un risultato di tipo a , ma il termine "monade di stato" può generalmente riferirsi a qualsiasi monade che porta uno stato. Il pacchetto mtl e transformers fornisce implementazioni generali di monadi di stato.

Osservazioni

I nuovi arrivati ​​a Haskell spesso si allontanano dalla monade di State e la trattano come un tabù, come il presunto beneficio della programmazione funzionale è l'evitamento dello stato, quindi non lo perdi quando usi State ? Una visione più sfumata è che:

  • Lo stato può essere utile in piccole dosi controllate ;
  • Il tipo di State offre la possibilità di controllare la dose in modo molto preciso.

Il motivo è che se hai action :: State sa , questo ti dice che:

  • action è speciale perché dipende da uno stato;
  • Lo stato ha tipo s , quindi l' action non può essere influenzata da alcun vecchio valore nel tuo programma, solo una s o qualche valore raggiungibile da alcuni s ;
  • runState :: State sa -> s -> (a, s) mette una "barriera" attorno all'azione stateful, in modo che la sua efficacia non possa essere osservata dall'esterno di quella barriera.

Quindi questo è un buon insieme di criteri per decidere se utilizzare lo State in uno scenario particolare. Volete vedere che il vostro codice sta riducendo al minimo l'ambito dello stato , sia scegliendo un tipo stretto per s sia mettendo runState più vicino possibile al "fondo" (in modo che le vostre azioni possano essere influenzate da poche cose come possibile.

Numerare i nodi di un albero con un contatore

Abbiamo un tipo di dati dell'albero come questo: 

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

E desideriamo scrivere una funzione che assegni un numero a ciascun nodo dell'albero, da un contatore incrementale: 

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

La lunga strada

Per prima cosa lo faremo nel modo migliore, dal momento che illustra abbastanza bene la meccanica di basso livello della monade di 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'

refactoring

Suddividi il contatore in un'azione postIncrement

Il pezzo in cui siamo get ting il contatore corrente e quindi put contatore ting + 1 può essere liberato in un postIncrement azione, simile a quello che molti linguaggi in stile C forniscono: 

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

Suddividere la camminata dell'albero in una funzione di ordine superiore

La logica di camminata dell'albero può essere suddivisa in una sua funzione, come questa: 

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 questa e la funzione postIncrement possiamo riscrivere 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 classe Traversable

La soluzione mapTreeM sopra può essere facilmente riscritta in un'istanza della classe Traversable : 

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

Nota che questo ci obbligava a usare Applicative (l'operatore <*> ) al posto di Monad .

Con quello, ora possiamo scrivere tag come un professionista: 

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)

Nota che questo funziona per qualsiasi tipo di Traversable , non solo per il nostro tipo di Tree !

Come liberarsi del Traversable boilerplate

GHC ha un'estensione DeriveTraversable che elimina la necessità di scrivere l'istanza sopra: 

{-# 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
Autorizzato sotto CC BY-SA 3.0
Non affiliato con Stack Overflow