Вкусные вычисления с состоянием

Haskell является чистым языком, и вследствие этого наши програм- мы состоят из функций, которые не могут изменять какое бы то ни было глобальное состояние или переменные – они могут только производить какие-либо вычисления и возвращать результаты. На самом деле данное огра-

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

Тем не менее некото- рые задачи по своей при- роде обладают состоя- нием, поскольку зависят от какого-то состояния, изменяющегося с течени- ем времени. Хотя это не

проблема для Haskell, такие вычисления могут быть немного уто- мительными для моделирования. Вот почему в языке Haskell есть монада State, благодаря которой решение задач с внутренним со- стоянием становится сущим пустяком – и в то же время остаётся красивым и чистым.

Когда мы разбирались со случайными числами в главе 9, то имели дело с функциями, которые в качестве параметра прини- мали генератор случайных чисел и возвращали случайное число и новый генератор случайных чисел. Если мы хотели сгенери- ровать несколько случайных чисел, нам всегда приходилось ис- пользовать генератор случайных чисел, который возвращала предыдущая функция вместе со своим результатом. Например, чтобы создать функцию, которая принимает значение типа StdGen и трижды «подбрасывает монету» на основе этого генератора, мы делали следующее:

threeCoins:: StdGen –> (Bool, Bool, Bool) threeCoins gen =

 

let (firstCoin, newGen) = random gen (secondCoin, newGen') = random newGen (thirdCoin, newGen'') = random newGen'

in (firstCoin, secondCoin, thirdCoin)

Эта функция принимает генератор gen, а затем вызов random gen возвращает значение типа Bool наряду с новым генератором. Для подбрасывания второй монеты мы используем новый генера- тор, и т. д.

В большинстве других языков нам не нужно было бы возвра- щать новый генератор вместе со случайным числом. Мы могли бы просто изменить имеющийся! Но поскольку Haskell является чис- тым языком, этого сделать нельзя, поэтому мы должны были взять какое-то состояние, создать из него результат и новое состояние, а затем использовать это новое состояние для генерации новых ре- зультатов.

Можно подумать, что для того, чтобы не иметь дела с вычисле- ниями с состоянием вручную подобным образом, мы должны были бы отказаться от чистоты языка Haskell. К счастью, такую жертву приносить не нужно, так как существует специальная небольшая мо- нада под названием State. Она превосходно справляется со всеми этими делами с состоянием, никоим образом не влияя на чистоту, благодаря которой программирование на языке Haskell настолько оригинально и изящно.

 

Вычисления с состоянием

Чтобы лучше продемонстрировать вычисления с внутренним со- стоянием, давайте просто возьмём и дадим им тип. Мы скажем, что вычисление с состоянием – это функция, которая принимает некое состояние и возвращает значение вместе с неким новым состояни- ем. Данная функция имеет следующий тип:

s –> (a, s)

Идентификатор s обозначает тип состояния; a – это результат вычислений с состоянием.

ПРИМЕЧАНИЕ. В большинстве других языков присваивание зна- чения может рассматриваться как вычисление с состоянием. На- пример, когда мы выполняем выражение x = 5 в императивном

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

Это вычисление с состоянием – функцию, которая принимает состояние и возвращает результат и новое состояние – также мож- но воспринимать как значение с контекстом. Действительным зна- чением является результат, тогда как контекстом является то, что мы должны предоставить некое исходное состояние, чтобы фак- тически получить этот результат, и то, что помимо результата мы также получаем новое состояние.

 

Стеки и чебуреки

Предположим, мы хотим смоделировать стек. Стек – это структура данных, которая содержит набор элементов и поддерживает ровно две операции:

® проталкивание элемента в стек (добавляет элемент на вер- хушку стека);

® выталкивание элемента из стека (удаляет самый верхний элемент из стека).

Для представления нашего стека будем использовать список,

«голова» которого действует как вершина стека. Чтобы решить эту задачу, создадим две функции:

® функция pop будет принимать стек, выталкивать один эле- мент и возвращать его в качестве результата. Кроме того, она возвращает новый стек без вытолкнутого элемента;

® функция push будет принимать элемент и стек, а затем про- талкивать этот элемент в стек. В качестве результата она бу- дет возвращать значение () вместе с новым стеком.

Вот используемые функции:

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

До сих пор каждый раз, когда мы реализовывали операцию >>=, сразу же после извлечения результата из монадического значения мы применяли к нему функцию 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 () просто сохраняет состоя- ние как есть и ничего не делает.