Монада State
Модуль Control.Monad.State предоставляет тип newtype, который оборачивает вычисления с состоянием. Вот его определение:
newtype State s a = State { runState :: s –> (a, s) }
Тип State s a – это тип вычисления с состоянием, которое манипулирует состоянием типа s и имеет результат типа a.
Как и модуль Control.Monad.Writer, модуль Control.Monad.State не экспортирует свой конструктор значения. Если вы хотите взять вычисление с состоянием и обернуть его в newtype State, используйте функцию state, которая делает то же самое, что делал бы конструктор State.
Теперь, когда вы увидели, в чём заключается суть вычислений с состоянием и как их можно даже воспринимать в виде значений с контекстами, давайте рассмотрим их экземпляр класса Monad:
instance Monad (State s) where
return x = State $ s –> (x, s)
(State h) >>= f = State $ s –> let (a, newState) = h s
(State g) = f a
in g newState
Наша цель использования функции return состоит в том, чтобы взять значение и создать вычисление с состоянием, которое всегда содержит это значение в качестве своего результата. Поэтому мы просто создаём анонимную функцию s –> (x, s). Мы всегда представляем значение x в качестве результата вычисления с состоянием, а состояние остаётся неизменным, так как функция return должна помещать значение в минимальный контекст. Потому функция return создаст вычисление с состоянием, которое представляет определённое значение в качестве результата, а состояние сохраняет неизменным.
А что насчёт операции >>=? Ну что ж, результатом передачи вычисления с состоянием функции с помощью операции >>= должно быть вычисление с состоянием, верно? Поэтому мы начинаем с обёртки newtype State, а затем вызываем анонимную функцию. Эта анонимная функция будет нашим новым вычислением с состоянием. Но что же в ней происходит? Нам каким-то образом нужно извлечь значение результата из первого вычисления с состоянием. Поскольку прямо сейчас мы находимся в вычислении с состоянием, то можем передать вычислению с состоянием h наше текущее состояние s, что в результате даёт пару из результата и нового состояния: (a, newState).
До сих пор каждый раз, когда мы реализовывали операцию >>=, сразу же после извлечения результата из монадического значения мы применяли к нему функцию f, чтобы получить новое монадическое значение. В случае с монадой Writer после того, как это сделано и получено новое монадическое значение, нам по-прежнему нужно позаботиться о контексте, объединив прежнее и новое моноидные значения с помощью функции mappend. Здесь мы выполняем вызов выражения f a и получаем новое вычисление с состоянием g. Теперь, когда у нас есть новое вычисление с состоянием и новое состояние (известное под именем newState), мы просто применяем это вычисление с состоянием g к newState. Результатом является кортеж из окончательного результата и окончательного состояния!
Итак, при использовании операции >>= мы как бы «склеиваем» друг с другом два вычисления, обладающих состоянием. Второе вычисление скрыто внутри функции, которая принимает результат предыдущего вычисления. Поскольку функции pop и push уже являются вычислениями с состоянием, легко обернуть их в обёртку State:
import Control.Monad.State
pop :: State Stack Int
pop = state $ (x:xs) –> (x, xs)
push :: Int –> State Stack ()
push a = state $ xs –> ((), a:xs)
Обратите внимание, как мы задействовали функцию state, чтобы обернуть функцию в конструктор newtype State, не прибегая к использованию конструктора значения State напрямую.
Функция pop – уже вычисление с состоянием, а функция push принимает значение типа Int и возвращает вычисление с состоянием. Теперь мы можем переписать наш предыдущий пример проталкивания числа 3 в стек и выталкивания двух чисел подобным образом:
import Control.Monad.State
stackManip :: State Stack Int
stackManip = do
push 3
a <– pop
pop
Видите, как мы «склеили» проталкивание и два выталкивания в одно вычисление с состоянием? Разворачивая его из обёртки newtype, мы получаем функцию, которой можем предоставить некое исходное состояние:
ghci> runState stackManip [5,8,2,1]
(5,[8,2,1])
Нам не требовалось привязывать второй вызов функции pop к образцу a, потому что мы вовсе не использовали этот образец. Значит, это можно было записать вот так:
stackManip :: State Stack Int
stackManip = do
push 3
pop
pop
Очень круто! Но что если мы хотим сделать что-нибудь посложнее? Скажем, вытолкнуть из стека одно число, и если это число равно 5, просто протолкнуть его обратно в стек и остановиться. Но если число не равно 5, вместо этого протолкнуть обратно 3 и 8. Вот он код:
stackStuff :: State Stack ()
stackStuff = do
a <– pop
if a == 5
then push 5
else do
push 3
push 8
Довольно простое решение. Давайте выполним этот код с исходным стеком:
ghci> runState stackStuff [9,0,2,1,0] ((),[8,3,0,2,1,0])
Вспомните, что выражения do возвращают в результате монадические значения, и при использовании монады State одно выражение do является также функцией с состоянием. Поскольку функции stackManip и stackStuff являются обычными вычислениями с состоянием, мы можем «склеивать» их вместе, чтобы производить дальнейшие вычисления с состоянием:
moreStack :: State Stack ()
moreStack = do
a <– stackManip
if a == 100
then stackStuff
else return ()
Если результат функции stackManip при использовании текущего стека равен 100, мы вызываем функцию stackStuff; в противном случае ничего не делаем. Вызов return () просто сохраняет состояние как есть и ничего не делает.