и для вычисления последующих подзадач используются решения из предыдущих, стоит задуматься об ис-
пользовании мемоизации. Такие задачи называются задачами динамического программирования. Вычисление
чисел Фибоначчи яркий пример задачи динамического программирования.
Рассмотрим такую задачу. Дана прямоугольная “карта местности”, в каждой клетке целым числом ука-
зана высота точки. Необходимо разметить местность по следующим правилам:
• Из каждой клетки карты вода стекает не более чем в одном из четырёх возможных направлений (“се-
вер”, “юг”, “запад”, “восток”).
• Если у клетки нет ни одного соседа с высотой меньше её собственной высоты, то эта клетка – водосток,
и вода из неё никуда дальше не течёт.
• Иначе вода из текущей клетки стекает на соседнюю клетку с минимальной высотой.
• Если таких соседей несколько, то вода стекает по первому из возможных направлений из списка “на
север”, “на запад”, “на восток”, “на юг”.
Все клетки из которых вода стекает в один и тот же водосток принадлежат к одному бассейну водосбо-
ра. Необходимо отметить на карте все бассейны. Решение этой задачи встретилось мне в статье Дмитрия
Астапова “Рекурсия+мемоизация = динамическое программирование”. Здесь оно и приводится с незначи-
тельными изменениями.
Карта местности представлена в виде двумерного массива, в каждой клетке которого отмечена высота
точки, нам необходимо получить двумерный массив того же размера, который вместо высот содержит метки
водостоков. Мы будем отмечать их буквами латинского алфавита в том порядке, в котором они встречаются
при обходе карты сверху вниз, слева направо. Например:
186 | Глава 11: Ленивые чудеса
1 2 3 4 5 6
a a a b b b
7 8 9 2 4 5
a a b b b b
3 5 3 3 6 7
->
c c d b b e
6 4 5 5 3 1
f g d b e e
2 2 4 5 3 7
f g g h h e
Для представления двумерного массива мы воспользуемся типом Array из стандартного модуля
Data.Array. Тип Array имеет два параметра:
data Array i a
Первый указывает на индекс, а второй на содержание. Массивы уже встречались нам в главе о типе ST.
Напомню, что подразумевается, что этот тип является экземпляром класса Ix, который описывает целочис-
ленные индексы, вспомним его определение:
class Ord a => Ix a where
range
:: (a, a) -> [a]
index
:: (a, a) -> a -> Int
inRange
:: (a, a) -> a -> Bool
rangeSize
:: (a, a) -> Int
Первый аргумент у всех этих функций это пара, которая представляет верхнюю и нижнюю грань после-
довательности. Попробуйте догадаться, что делают методы этого класса по типам и именам.
Для двумерного массива индекс будет задаваться парой целых чисел:
import Data.Array
type Coord = (Int, Int)
type HeightMap = Array Coord Int
type SinkMap
= Array Coord Coord
Значение типа HeightMap хранит карту высот, значение типа SinkMap хранит в каждой координате, ту
точку, которая является водостоком для данной точки. Нам необходимо построить функцию:
flow :: HeightMap -> SinkMap
Мы будем решать эту задачу рекурсивно. Представим, что мы знаем водостоки для всех точек кроме
данной. Для каждой точки мы можем узнать в какую сторону из неё стекает вода. При этом водосток для
следующей точки такой же как и для текущей. Если же из данной точки вода никуда не течёт, то она сама
является водостоком. Мы определим эту функцию через комбинатор неподвижной точки fix.:
flow :: HeightMap -> SinkMap
flow arr = fix $ result -> listArray (bounds arr) $
map (x -> maybe x (result ! ) $ getSink arr x) $
range $ bounds arr
getSink :: HeightMap -> Coord -> Maybe Coord
Мы ищем решение в виде неподвижной точки функции, которая принимает карту стоков и возвращает
карту стоков. Функция getSink по данной точке на карте вычисляет соседнюю точку, в которую стекает вода.
Эта функция частично определена, поскольку для водостоков нет такой соседней точки, в которую бы утекала
вода. Функция listArray конструирует значение типа Array из списка значений. Первым аргументом она
принимает диапазон значений для индексов. Размеры массива совпадают с размерами карты высот, поэтому
первым аргументом мы передаём bounds arr.
Теперь разберёмся с тем как заполняются значения в список. Сначала мы создаём список координат
исходной карты высот с помощью выражения:
range $ bounds arr
После этого мы по координатам точек находим водостоки, причём сразу для всех точек. Это происходит
в лямбда-функции:
x -> maybe x (result ! ) $ getSink arr x
Водосборы | 187
Мы принимаем текущую координату и с помощью функции getSink находим соседнюю точку, в которую
убегает вода. Если такой точки нет, то в следующем выражении мы вернём исходную точку, поскольку в этом
случае она и будет водостоком, а если такая соседняя точка всё-таки есть мы спросим результат из будущего.
Мы обратимся к результату (result ! ), посмотрим каким окажется водосток для соседней точки и вернём
это значение. Поскольку за счёт ленивых вычислений значения результирующего массива вычисляются лишь
один раз, после того как мы найдём водосток для данной точки этим результатом смогут воспользоваться
все соседние точки. При этом порядок обращения к значениям из будущих вычислений не играет роли.
Осталось только определить функцию поиска ближайшего стока и функцию разметки.