Изучай Haskell во имя добра!

type Stack = [Int]

pop :: Stack –> (Int, Stack)

pop (x:xs) = (x, xs)

push :: Int –> Stack –> ((), Stack)

push a xs = ((), a:xs)

При проталкивании в стек в качестве результата мы использовали значение (), поскольку проталкивание элемента на вершину стека не несёт какого-либо существенного результирующего значения – его основная задача заключается в изменении стека. Если мы применим только первый параметр функции push, мы получим вычисление с состоянием. Функция pop уже является вычислением с состоянием вследствие своего типа.

Давайте напишем небольшой кусок кода для симуляции стека, используя эти функции. Мы возьмём стек, протолкнём в него значение 3, а затем вытолкнем два элемента просто ради забавы. Вот оно:

stackManip :: Stack –> (Int, Stack)

stackManip stack = let

   ((), newStack1) = push 3 stack

   (a , newStack2) = pop newStack1

   in pop newStack2

Мы принимаем стек, а затем выполняем выражение push 3 stack, что даёт в результате кортеж. Первой частью кортежа является значение (), а второй частью является новый стек, который мы называем newStack1. Затем мы выталкиваем число из newStack1, что даёт в результате число a (равно 3), которое мы протолкнули, и новый стек, названный нами newStack2. Затем мы выталкиваем число из newStack2 и получаем число и новый стек. Мы возвращаем кортеж с этим числом и новым стеком. Давайте попробуем:

ghci> stackManip [5,8,2,1]

(5,[8,2,1])

Результат равен 5

, а новый стек – [8,2,1]. Обратите внимание, как функция stackManip сама является вычислением с состоянием. Мы взяли несколько вычислений с состоянием и как бы «склеили» их вместе. Хм-м, звучит знакомо.

Предшествующий код функции stackManip несколько громоздок, потому как мы вручную передаём состояние каждому вычислению с состоянием, сохраняем его, а затем передаём следующему. Не лучше ли было бы, если б вместо того, чтобы передавать стек каждой функции вручную, мы написали что-то вроде следующего:

stackManip = do

   push 3

   a <– pop

   pop

Ла-адно, монада State позволит нам делать именно это!.. С её помощью мы сможем брать вычисления с состоянием, подобные этим, и использовать их без необходимости управлять состоянием вручную.

Монада 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).