(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
Мы будем решать эту задачу рекурсивно. Представим, что мы знаем водостоки для всех точек кроме
данной. Для каждой точки мы можем узнать в какую сторону из неё стекает вода. При этом водосток для
следующей точки такой же как и для текущей. Если же из данной точки вода никуда не течёт, то она сама
является водостоком. Мы определим эту функцию через комбинатор неподвижной точки 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 по данной точке на карте вычисляет соседнюю точку, в которую стекает вода.