Миран Липовача - Изучай Haskell во имя добра!
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 () просто сохраняет состояние как есть и ничего не делает.
Получение и установка состояния
Модуль Control.Monad.State определяет класс типов под названием MonadState, в котором присутствуют две весьма полезные функции: get и put. Для монады State функция get реализована вот так:
get = state $ s –> (s, s)
Она просто берёт текущее состояние и представляет его в качестве результата.
Функция put принимает некоторое состояние и создаёт функцию с состоянием, которая заменяет им текущее состояние:
put newState = state $ s –> ((), newState)
Поэтому, используя их, мы можем посмотреть, чему равен текущий стек, либо полностью заменить его другим стеком – например, так:
stackyStack :: State Stack ()
stackyStack = do
stackNow <– get
if stackNow == [1,2,3]
then put [8,3,1]
else put [9,2,1]
Также можно использовать функции get и put, чтобы реализовать функции pop и push. Вот определение функции pop:
pop :: State Stack Int
pop = do
(x:xs) <– get
put xs
return x
Мы используем функцию get, чтобы получить весь стек, а затем – функцию put, чтобы новым состоянием были все элементы за исключением верхнего. После чего прибегаем к функции return, чтобы представить значение x в качестве результата.
Вот определение функции push, реализованной с использованием get и put:
push :: Int –> State Stack ()
push x = do
xs <– get
put (x:xs)
Мы просто используем функцию get, чтобы получить текущее состояние, и функцию put, чтобы установить состояние в такое же, как наш стек с элементом x на вершине.
Стоит проверить, каким был бы тип операции >>=, если бы она работала только со значениями монады State:
(>>=) :: State s a –> (a –> State s b) –> State s b
Видите, как тип состояния s остаётся тем же, но тип результата может изменяться с a на b? Это означает, что мы можем «склеивать» вместе несколько вычислений с состоянием, результаты которых имеют различные типы, но тип состояния должен оставаться тем же. Почему же так?.. Ну, например, для типа Maybe операция >>= имеет такой тип:
(>>=) :: Maybe a –> (a –> Maybe b) –> Maybe b
Логично, что сама монада Maybe не изменяется. Не имело бы смысла использовать операцию >>= между двумя разными монадами. Для монады State монадой на самом деле является State s, так что если бы этот тип s был различным, мы использовали бы операцию >>= между двумя разными монадами.
