Haskell Language
Государственная Монада

algorithm C Language C++ clojure F# Java Language GNU/Linux Python Language Regular Expressions Scala Language
Поиск…


Вступление

Государственные монады - это своего рода монада, несущая состояние, которое может измениться во время каждого прогона вычисления в монаде. Реализации обычно имеют форму State sa которая представляет собой вычисление, которое переносит и потенциально модифицирует состояние типа s и производит результат типа a , но термин «монада государства» обычно может относиться к любой монаде, которая несет состояние. Пакет mtl и transformers обеспечивает общие реализации государственных монадов.

замечания

Новички в Хаскелле часто уклоняются от State монады и рассматривают ее как табу, как заявленное преимущество функционального программирования - это избегание государства, так что вы не теряете это, когда используете State ? Более тонкий взгляд на то, что:

  • Государство может быть полезно в небольших контролируемых дозах ;
  • Тип State обеспечивает возможность очень точно контролировать дозу.

Причины, что если у вас есть action :: State sa , это говорит вам, что:

  • action особенное, потому что оно зависит от состояния;
  • Состояние имеет тип s , поэтому на action не может влиять никакое старое значение в вашей программе - только s или некоторое значение, доступное из некоторых s ;
  • runState :: State sa -> s -> (a, s) ставит «барьер» вокруг действия с состоянием, так что его эффективность не может наблюдаться извне этого барьера.

Таким образом, это хороший набор критериев для использования State в конкретном сценарии. Вы хотите видеть, что ваш код сводит к минимуму область состояния , как путем выбора узкого типа для s и путем установки runState как можно ближе к «дну» (так что на ваши действия может влиять как минимум возможный.

Нумерация узлов дерева с помощью счетчика

У нас есть такой тип данных дерева: 

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

И мы хотим написать функцию, которая присваивает номер каждому узлу дерева, от счетчика: 

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

Длинный путь

Сначала мы сделаем это очень далеко, так как он очень хорошо иллюстрирует механику низкого уровня 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'

Рефакторинг

Разделите счетчик на действие postIncrement

Бит, где мы get текущий счетчик, а затем put счетчик ting + 1, можно разделить на действие postIncrement , аналогичное тому, что предоставляют языки C-стиля: 

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

Разделите дерево в функцию более высокого порядка

Логику древовидной ходьбы можно разделить на свою собственную функцию, например: 

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'

С помощью этой и функции postIncrement мы можем переписать 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)

Использовать класс Traversable

Решение mapTreeM выше может быть легко переписано в экземпляр класса Traversable : 

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

Обратите внимание, что для этого требовалось использовать вместо Monad Applicative (оператор <*> ).

Таким образом, теперь мы можем написать tag как pro: 

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)

Обратите внимание, что это работает для любого типа Traversable , а не только для нашего типа Tree !

Избавление от шаблона Traversable

GHC имеет расширение 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
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow