Учебник по Haskell

В этом примере мы рассмотрим одну интересную технику рекурсивных вычислений, которая называется

мемоизацией (memoization). Она заключается в том, что мы запоминаем все значения, с которыми вызывалась

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

если значение ещё не вычислялось, вычисляем его и сохраняем.

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

храняем все значения функции в некотором контейнере, а затем обращаемся к элементам. При этом значения

сохраняются в контейнере и не перевычисляются. Это происходит за счёт ленивых вычислений. Что интерес-

но вычисляются не все значения, а лишь те, которые нам действительно нужны, те которые мы извлекаем из

контейнера хотя бы один раз.

Посмотрим на такой классический пример. Вычисление чисел Фибоначчи. Каждое последующее число

ряда Фибоначчи равно сумме двух предыдущих. Наивное определение выглядит так:

fib :: Int -> Int

fib 0 = 0

fib 1 = 1

fib n = fib (n-1) + fib (n-2)

В этом определении число вычислений растёт экспоненциально. Для того чтобы вычислить fib n нам

нужно вычислить fib (n-1) и fib (n-2), для того чтобы вычислить каждое из них нам нужно вычислить

ещё два числа, и так вычисления удваиваются на каждом шаге. Если мы вызовем в интерпретаторе fib 40,

то вычислитель зависнет. Что интересно в этой функции вычисления пересекаются, они могут быть пере-

использованы. Например для вычисления fib (n-1) и fib (n-2) нужно вычислить fib (n-2) (снова), fib

(n-3), fib (n-3) (снова) и fib (n-4).

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

раз:

fib’ :: Int -> Int

fib’ n = fibs !! n

where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Попробуем вычислить для 40:

*Fib> fib’ 40

102334155

*Fib> fib’ 4040

700852629

Вычисления происходят мгновенно. Если задача состоит из множества подзадач, которые самоподобны

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

пользовании мемоизации. Такие задачи называются задачами динамического программирования. Вычисление

чисел Фибоначчи яркий пример задачи динамического программирования.

Рассмотрим такую задачу. Дана прямоугольная “карта местности”, в каждой клетке целым числом ука-

зана высота точки. Необходимо разметить местность по следующим правилам:

• Из каждой клетки карты вода стекает не более чем в одном из четырёх возможных направлений (“се-

вер”, “юг”, “запад”, “восток”).

• Если у клетки нет ни одного соседа с высотой меньше её собственной высоты, то эта клетка – водосток,

и вода из неё никуда дальше не течёт.

• Иначе вода из текущей клетки стекает на соседнюю клетку с минимальной высотой.

• Если таких соседей несколько, то вода стекает по первому из возможных направлений из списка “на

север”, “на запад”, “на восток”, “на юг”.

Все клетки из которых вода стекает в один и тот же водосток принадлежат к одному бассейну водосбо-

ра. Необходимо отметить на карте все бассейны. Решение этой задачи встретилось мне в статье Дмитрия

Астапова “Рекурсия+мемоизация = динамическое программирование”. Здесь оно и приводится с незначи-

тельными изменениями.

Карта местности представлена в виде двумерного массива, в каждой клетке которого отмечена высота

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

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

при обходе карты сверху вниз, слева направо. Например:

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