Учебник по 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-

вычислений. Можно ли этого избежать? Оказывается, что можно. Причём решение весьма элегантно. Мы

можем построить типы Mem и Mutable так, чтобы ссылке на память не удалось просочиться через функцию

purge. Для этого мы вернёмся к общему типу State c двумя параметрами. Причём первый первый параметр

мы прицепим и к Mem:

data

Mem

s a = ..

newtype Mutable s a = ..

new

:: a -> Mutable s (Mem s a)

write

:: Mem s a -> a -> Mutable s ()

read

:: Mem s a -> Mutable s a

Теперь при создании типы Mem и Mutable связаны общим параметром s. Посмотрим на тип функции purge

purge :: (forall s. Mutable s a) -> a

Она имеет необычный тип. Слово forall означает “для любых”. Это слово называют квантором всеобщ-

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

фиктивного состояния. Как дополнительный forall может нам помочь? Функция purge забывает тип фик-