Haskell Language
State Monad

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


Wprowadzenie

Monady stanowe są rodzajem monad, które niosą ze sobą stan, który może ulec zmianie podczas każdego uruchomienia obliczeniowego monady. Implementacje mają zwykle postać State sa która reprezentuje obliczenia, które przenoszą i potencjalnie modyfikują stan typu s i dają wynik typu a , ale termin „monada stanu” może ogólnie odnosić się do dowolnej monady, która niesie stan. Pakiet mtl i transformers zapewniają ogólne implementacje monad państwowych.

Uwagi

Nowo przybyli do Haskell często unikają monady State i traktują ją jak tabu - tak jak rzekomą korzyścią z programowania funkcjonalnego jest unikanie stanu, więc czy nie stracicie tego, kiedy używacie State ? Bardziej szczegółowy widok polega na tym, że:

  • Stan może być użyteczny w małych, kontrolowanych dawkach ;
  • Typ State zapewnia bardzo precyzyjną kontrolę dawki.

Powodem jest to, że jeśli masz action :: State sa , to mówi ci, że:

  • action jest wyjątkowa, ponieważ zależy od stanu;
  • Stan ma typ s , więc na action nie może mieć wpływu żadna stara wartość w twoim programie - tylko s lub pewna wartość osiągalna z niektórych s ;
  • runState :: State sa -> s -> (a, s) nakłada „barierę” wokół działania stanowego, tak że nie można zaobserwować jego skuteczności spoza tej bariery.

Jest to dobry zestaw kryteriów określających, czy należy użyć opcji State w danym scenariuszu. Chcesz, aby Twój kod minimalizował zakres stanu , zarówno wybierając wąski typ dla s i ustawiając runState jak najbliżej „dolnej części” (tak, aby na twoje działania mogła mieć wpływ jak najmniej możliwy.

Numeracja węzłów drzewa za pomocą licznika

Mamy taki typ danych drzewa: 

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

I chcemy napisać funkcję, która przypisuje liczbę do każdego węzła drzewa z licznika rosnącego: 

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

Długa droga

Najpierw zrobimy to na dłuższą metę, ponieważ całkiem ładnie ilustruje mechanikę niskiego poziomu monady 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'

Refaktoryzacja

Podziel licznik na akcję postIncrement

Tę część, w której get ting bieżący licznik, a następnie put ting counter + 1, można podzielić na akcję postIncrement , podobnie jak wiele języków w stylu C: 

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

Podziel ścieżkę drzewa na funkcję wyższego rzędu

Logikę chodzenia po drzewie można podzielić na własne funkcje, takie jak: 

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'

Za pomocą tego i funkcji postIncrement możemy przepisać 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)

Użyj klasy Traversable

mapTreeM rozwiązanie mapTreeM można łatwo przepisać na instancję klasy Traversable : 

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

Zauważ, że wymagało to od nas zastosowania Applicative (operator <*> ) zamiast Monad .

Z tym, teraz możemy napisać tag jak profesjonalista: 

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)

Pamiętaj, że działa to dla każdego typu Traversable , nie tylko naszego typu Tree !

Pozbycie się Traversable boilerplate

GHC ma rozszerzenie DeriveTraversable które eliminuje potrzebę pisania powyższej instancji: 

{-# 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
Licencjonowany na podstawie CC BY-SA 3.0
Nie związany z Stack Overflow