статичности мира, у нас появляются фазы: до обновления и после обновления. Но представьте, что обнов-
ление происходит локально, мы постоянно меняем только одно значение, при этом за время обновления ни
одна другая переменная не может пользоваться промежуточными значениями и обновления происходят с
помощью чистых функций. Представьте функцию, которая принимает значение, выделяет внутри себя па-
мять, и при построении результата начинает обновлять значение внутри этой памяти (с помощью чистых
функций) и считать что-то ещё полезное на основе этих обновлений, как только вычисления закончатся, па-
мять стирается, и возвращается значение. Будет ли такая функция чистой? Интуиция подсказывает, что да.
Это было доказано, но для реализации этого требуется небольшой трюк на уровне типов. Получается, что
не смотря на то, что функция содержит побочные эффекты, она является чистой, поскольку все побочные
эффекты локальны, они происходят только внутри вызова функции и только в самой функции.
Для симуляции обновления значения в Haskell нам нужно решить две проблемы. Как упорядочить обнов-
ление значения? И как локализовать его? В императивных языках порядок вычисления выражений строго
связан с порядком следования выражений, на примитивном уровне, грубо упрощая, можно сказать, что вы-
числитель читает код как ленту и выполняет выражение за выражением. В Haskell всё совсем по-другому. Мы
можем писать функции в любом порядке, также в любом порядке мы можем объявлять локальные перемен-
ные в where или let-выражениях. Компилятор определяет порядок редукции синонимов по функциональным
Монада изменяемых значений ST | 117
зависимостям. Синоним f не будет раскрыт раньше синонима g только в том случае, если результат g тре-
буется в f. Но с обновлением значения этот вариант не пройдёт, посмотрим на выражение:
fun :: Int -> Int
fun arg =
let mem = new arg
x
= read mem
y
= x + 1
??
= write mem y
z
= read mem
in z
Предполагается, что в этой функции мы получаем значение arg, выделяем память mem c помощью спе-
циальной функции new, которая принимает начальное значение, которое будет храниться в памяти. Затем
читаем из памяти, прибавляем к значению единицу, снова записываем в память, потом опять читаем из па-
мяти, сохранив значение в переменной z, и в самом конце возвращаем ответ. Налицо две проблемы: z не
зависит от y, поэтому мы можем считать значение z в любой момент после инициализации памяти и вторая
проблема: что должна возвращать функция write?
Для того чтобы упорядочить эти вычисления мы воспользуемся типом State. Каждое выражение будет
принимать фиктивное состояние и возвращать его. Тогда функция fun запишется так:
fun :: Int -> State s Int
fun arg = State $ s0 ->
let (mem, s1)
= runState (new arg)
s0
((),
s2)
= runState (write mem arg)
s1
(x,
s3)
= runState (read mem)
s2
y
= x + 1
((),
s4)
= runState (write mem y)
s3
(z,
s5)
= runState (read mem)
s4
in (z, s5)
new
:: a -> State s (Mem a)
write
:: Mem a -> a -> State s ()
read
:: Mem a -> State s a
Тип Mem параметризован типом значения, которое хранится в памяти. В этом варианте мы не можем
изменить порядок следования выражений, поскольку нам приходится передовать состояние. Мы могли бы
записать это выражение гораздо короче с помощью методов класса Monad, но мне хотелось подчеркнуть как
передача состояния навязывает порядок вычисления. Функция write теперь возвращает пустой кортеж. Но
порядок не теряется за счёт состояния. Пустой кортеж намекает на то, что единственное назначение функции
write – это обновление состояния.
Однако этого не достаточно. Мы хотим, чтобы обновление значения было скрыто от пользователя в чистой
функции. Мы хотим, чтобы тип функции fun не содержал типа State. Для этого нам откуда-то нужно взять
начальное значение состояния. Мы можем решить эту проблему, зафиксировав тип s. Пусть это будет тип
FakeState, скрытый от пользователя.
module Mutable(
Mutable, Mem, purge,
new, read, write)
where
newtype Mutable a = Mutable (State FakeState a)
data FakeState = FakeState
purge :: Mutable a -> a
purge (Mutable a) = fst $ runState a FakeState
new
:: a -> Mutable (Mem a)
read
:: Mem a -> Mutable a
write
:: Mem a -> a -> Mutable ()
Мы предоставим пользователю лишь тип Mutable без конструктора и функцию purge, которая “очища-
ет” значение от побочных эффектов и примитивные функции для работы с памятью. Также мы определим
экземпляры классов типа State для Mutable, сделать это будет совсем не трудно, ведь Mutable – это просто
118 | Глава 7: Функторы и монады: примеры
обёртка. С помощью этих экземпляров пользователь сможет комбинировать вычисления, которые связаны с
изменением памяти. Пока вроде всё хорошо, но обеспечиваем ли мы локальность изменения значений? Нам
важно, чтобы, один раз начав работать с памятью типа Mem, мы не смогли бы нигде воспользоваться этой па-
мятью после выполнения функции purge. Оказывается, что мы можем разрушить локальность. Посмотрите
на пример:
let mem = purge allocate
in
purge (read mem)
Мы возвращаем из функции purge ссылку на память и спокойно пользуемся ею в другой ветке Mutable—
вычислений. Можно ли этого избежать? Оказывается, что можно. Причём решение весьма элегантно. Мы