*Tree> inDiap (5, 8) tree2
[6,7,5,8,6,7,5,6,7,5]
*Tree> inDiap (0, 3) tree2
[2,2,2]
7.5 Монада изменяемых значений ST
Возможно читатели, для которых “родным” является один из императивных языков, немного заскучали
по изменяемым значениям. Мы говорили, что в Haskell ничего не изменяется, мы даём всё более и более
сложные имена статическим значениям, а потом вычислитель редуцирует имена к настоящим значениям.
Но есть алгоритмы, которые очень элегантно описываются в терминах изменяемых значений. Примером
такого алгоритма может быть быстрая сортировка. Задача состоит в перестановке элементов массива так,
чтобы на выходе любой последующий элемент массива был больше предыдущего (для списков эту задачу
решают функции sort и sortBy).
Само по себе явление обновления значения является побочным эффектом. Оно ломает представление о
статичности мира, у нас появляются фазы: до обновления и после обновления. Но представьте, что обнов-
ление происходит локально, мы постоянно меняем только одно значение, при этом за время обновления ни
одна другая переменная не может пользоваться промежуточными значениями и обновления происходят с
помощью чистых функций. Представьте функцию, которая принимает значение, выделяет внутри себя па-
мять, и при построении результата начинает обновлять значение внутри этой памяти (с помощью чистых
функций) и считать что-то ещё полезное на основе этих обновлений, как только вычисления закончатся, па-
мять стирается, и возвращается значение. Будет ли такая функция чистой? Интуиция подсказывает, что да.
Это было доказано, но для реализации этого требуется небольшой трюк на уровне типов. Получается, что
не смотря на то, что функция содержит побочные эффекты, она является чистой, поскольку все побочные
эффекты локальны, они происходят только внутри вызова функции и только в самой функции.
Для симуляции обновления значения в 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 в любой момент после инициализации памяти и вторая