Haskell Language
State Monad

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


Einführung

Zustandsmonaden sind eine Art Monade, die einen Zustand aufweist, der sich bei jedem Berechnungslauf in der Monade ändern kann. Implementierungen haben normalerweise die Form State sa die eine Berechnung darstellt, die einen Status vom Typ s trägt und möglicherweise modifiziert und ein Ergebnis vom Typ a . Der Begriff "State Monad" kann sich jedoch im Allgemeinen auf jede Monade beziehen, die einen State trägt. Das Paket mtl und transformers bietet allgemeine Implementierungen von Zustandsmonaden.

Bemerkungen

Haskells Neuankömmlinge scheuen sich oft vor der State Monade und behandeln sie wie ein Tabu - wie der behauptete Vorteil der funktionalen Programmierung ist die Vermeidung des Staates. Verlieren Sie das also nicht, wenn Sie State ? Eine differenziertere Ansicht ist die:

  • Zustand kann in kleinen, kontrollierten Dosen nützlich sein;
  • Der State bietet die Möglichkeit, die Dosis sehr genau zu steuern.

Die Gründe sind, dass, wenn Sie action :: State sa , dies Folgendes sagt:

  • action ist etwas Besonderes, weil sie von einem Staat abhängt;
  • Der Status hat s , so dass die action nicht durch einen alten Wert in Ihrem Programm beeinflusst werden kann - nur ein s oder ein von einigen s erreichbarer Wert.
  • runState :: State sa -> s -> (a, s) eine "Barriere" um die zustandsbehaftete Aktion, so dass ihre Wirksamkeit nicht von außerhalb dieser Barriere beobachtet werden kann.

Dies ist also ein guter Satz von Kriterien für die Verwendung von State in einem bestimmten Szenario. Sie möchten sehen, dass Ihr Code den Umfang des Status minimiert , indem Sie einen schmalen Typ für s runState und runState so nahe wie möglich an "bottom" setzen (so dass Ihre Aktionen durch so wenig wie beeinflusst werden können) möglich.

Nummerieren der Knoten eines Baums mit einem Zähler

Wir haben einen Baumdatentyp wie folgt: 

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

Und wir möchten eine Funktion schreiben, die jedem Knoten des Baums eine Nummer von einem inkrementierenden Zähler zuweist: 

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

Der weite Weg

Zuerst machen wir den langen Weg, da dies die niedere Mechanik der State Monad recht gut veranschaulicht. 

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'

Umgestaltung

Trennen Sie den Zähler in eine postIncrement-Aktion

Das Bit , wo wir sind get ting die aktuellen Zähler und dann put ting Zähler + 1 abspalten in eine werden kann postIncrement Aktion, ähnlich wie viele C-Stil Sprachen zur Verfügung stellen: 

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

Teilen Sie den Baumschritt in eine Funktion höherer Ordnung auf

Die Tree-Walk-Logik kann wie folgt in eine eigene Funktion aufgeteilt werden: 

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'

Mit dieser und der postIncrement Funktion können Sie tagStep neu 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)

Verwenden Sie die Klasse Traversable

Die mapTreeM Lösung kann leicht in eine Instanz der Klasse Traversable umgeschrieben werden: 

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

Beachten Sie, dass dies die Verwendung von Applicative (Operator <*> ) anstelle von Monad erforderlich machte.

Damit können wir nun tag wie ein Profi schreiben: 

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)

Beachten Sie, dass dies für jeden Traversable Typ funktioniert, nicht nur für unseren Tree !

Erste des befreien Traversable vorformulierten

GHC hat eine Erweiterung von DeriveTraversable , die das Schreiben der obigen Instanz DeriveTraversable : 

{-# 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
Lizenziert unter CC BY-SA 3.0
Nicht angeschlossen an Stack Overflow