Unknown - haskell-notes

ление происходит локально, мы постоянно меняем только одно значение, при этом за время обновления ни

одна другая переменная не может пользоваться промежуточными значениями и обновления происходят с

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

мять, и при построении результата начинает обновлять значение внутри этой памяти (с помощью чистых

функций) и считать что-то ещё полезное на основе этих обновлений, как только вычисления закончатся, па-

мять стирается, и возвращается значение. Будет ли такая функция чистой? Интуиция подсказывает, что да.

Это было доказано, но для реализации этого требуется небольшой трюк на уровне типов. Получается, что

не смотря на то, что функция содержит побочные эффекты, она является чистой, поскольку все побочные

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

Для симуляции обновления значения в Haskell нам нужно решить две проблемы. Как упорядочить обнов-

ление значения? И как локализовать его? В императивных языках порядок вычисления выражений строго

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

числитель читает код как ленту и выполняет выражение за выражением. В Haskell всё совсем по-другому. Мы

можем писать функции в любом порядке, также в любом порядке мы можем объявлять локальные перемен-

ные в whereили let-выражениях. Компилятор определяет порядок редукции синонимов по функциональным

Монада изменяемых значений ST | 117

зависимостям. Синоним f не будет раскрыт раньше синонима g только в том случае, если результат g тре-

буется в f. Но с обновлением значения этот вариант не пройдёт, посмотрим на выражение:

fun :: Int -> Int

fun arg =

letmem =new arg

x

=read mem

y

=x +1

??

=write mem y

z

=read mem

inz

Предполагается, что в этой функции мы получаем значение arg, выделяем память mem c помощью спе-

циальной функции new, которая принимает начальное значение, которое будет храниться в памяти. Затем

читаем из памяти, прибавляем к значению единицу, снова записываем в память, потом опять читаем из па-

мяти, сохранив значение в переменной z, и в самом конце возвращаем ответ. Налицо две проблемы: z не

зависит от y, поэтому мы можем считать значение z в любой момент после инициализации памяти и вторая

проблема: что должна возвращать функция write?

Для того чтобы упорядочить эти вычисления мы воспользуемся типом State. Каждое выражение будет

принимать фиктивное состояние и возвращать его. Тогда функция fun запишется так:

fun :: Int -> States 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 -> States ( Mema)

write

:: Mema ->a -> States ()

read

:: Mema -> States a

Тип Memпараметризован типом значения, которое хранится в памяти. В этом варианте мы не можем

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

записать это выражение гораздо короче с помощью методов класса Monad, но мне хотелось подчеркнуть как

передача состояния навязывает порядок вычисления. Функция write теперь возвращает пустой кортеж. Но

порядок не теряется за счёт состояния. Пустой кортеж намекает на то, что единственное назначение функции

write – это обновление состояния.

Однако этого не достаточно. Мы хотим, чтобы обновление значения было скрыто от пользователя в чистой

функции. Мы хотим, чтобы тип функции fun не содержал типа State. Для этого нам откуда-то нужно взять

начальное значение состояния. Мы можем решить эту проблему, зафиксировав тип s. Пусть это будет тип

FakeState, скрытый от пользователя.

module Mutable(

Mutable, Mem, purge,

new, read, write)

where

newtype Mutablea = Mutable( State FakeStatea)

data FakeState = FakeState

purge :: Mutablea ->a

purge ( Mutablea) =fst $runState a FakeState