Haskell 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)