getSink :: HeightMap -> Coord -> Maybe Coord
getSink arr (x, y)
| null sinks = Nothing
| otherwise
= Just $ snd $ minimum $ map (i -> (arr! i, i)) sinks
where sinks = filter p [(x+1, y), (x—1, y), (x, y—1), (x, y+1)]
p i
= inRange (bounds arr) i && arr ! i < arr ! (x, y)
В функции разметки мы воспользуемся ассоциативным массивом из модуля Data.Map. Функция nub из
модуля Data.List убирает из списка повторяющиеся элементы. Затем мы составляем список пар из коорди-
нат водостоков и меток и в самом конце размечаем исходный массив:
label :: SinkMap -> LabelMap
label a = fmap (m M.! ) a
where m = M. fromList $ flip zip [’a’ .. ] $ nub $ elems a
11.4 Ленивее некуда
Мы выяснили, что значение может редуцироваться только при сопоставлении с образцом и в специальной
функции seq. Функцию seq мы можем применять, а можем и не применять. Но кажется, что в декомпозиции
мы не можем уйти от необходимости проведения хотя бы одной редукции. Оказывается можем, в Haskell для
этого предусмотрены специальные ленивые образцы (lazy patterns). Они обозначаются знаком тильда:
lazyHead :: [a] -> a
lazyHead ~(x:xs) = x
Перед скобками сопоставления с образцом пишется символ тильда. Этим мы говорим вычислителю: до-
верься мне, здесь точно такой образец, можешь даже не проверять дальше. Он и правда дальше не пойдёт.
Например если мы напишем такое определение:
lazySafeHead :: [a] -> Maybe a
lazySafeHead ~(x:xs) = Just x
lazySafeHead []
= Nothing
Если мы подставим в эту функцию пустой список мы получим ошибку времени выполнения, вычислитель
доверился нам в первом уравнении, а мы его обманули. Сохраним в модуле Strict и проверим:
Prelude Strict> :! ghc —make Strict
[1 of 1] Compiling Strict
( Strict. hs, Strict. o )
Strict. hs:67:0:
Warning: Pattern match(es) are overlapped
In the definition of ‘lazySafeHead’: lazySafeHead [] = …
Prelude Strict> :l Strict
Ok, modules loaded: Strict.
Prelude Strict> lazySafeHead [1,2,3]
Just 1
Prelude Strict> lazySafeHead []
Just *** Exception: Strict. hs:(67,0)—(68,29): Irrefutable
pattern failed for pattern (x : xs)
При компиляции нам даже сообщили о том, что образцы в декомпозиции пересекаются. Но мы были
упрямы и напоролись на ошибку, если мы поменяем образцы местами, то всё пройдёт гладко:
Prelude Strict> :! ghc —make Strict
[1 of 1] Compiling Strict
( Strict. hs, Strict. o )
Prelude Strict> :l Strict
Ok, modules loaded: Strict.
Prelude Strict> lazySafeHead []
Nothing
188 | Глава 11: Ленивые чудеса
Отметим, что сопоставление с образцом в let и where выражениях является ленивым. Функцию lazyHead
мы могли бы написать и так:
lazyHead a = x
where (x:xs) = a
lazyHead a =
let (x:xs) = a
in
x
Посмотрим как используются ленивые образцы при построении потоков, или бесконечных списков. Мы
будем представлять функции одного аргумента потоками значений с одинаковым шагом. Так мы будем пред-
ставлять непрерывные функции дискретными сигналами. Считаем, что шаг дискретизации (или шаг между
соседними точками) нам известен.
f : R > R ? fn = f ( n? ) ,
n = 0 , 1 , 2 , …
Где ? – шаг дискретизации, а n пробегает все натуральные числа. Определим функцию решения диффе-
ренциальных уравнений вида:
dx = f( t)
dt
x(0) = ?
x
Символ ? x означает начальное значение функции x. Перейдём к дискретным сигналам:
xn?xn? 1 = f
?
n,
x 0 = ?
x
Где ? – шаг дискретизации, а x и f – это потоки чисел, индекс n пробегает от нуля до бесконечности
по всем точкам функции, превращённой в дискретный сигнал. Такой метод приближения дифференциаль-
ных уравнений называют методом Эйлера. Теперь мы можем выразить следующий элемент сигнала через
предыдущий.
xn = xn? 1 + ? fn, x 0 = ?
x
Закодируем это уравнение:
— шаг дискретизации
dt :: Fractional a => a
dt = 1e-3
— метод Эйлера
int :: Fractional a => a -> [a] -> [a]
int x0 (f:fs) = x0 : int (x0 + dt * f) fs
Смотрите в функции int мы принимаем начальное значение x0 и поток всех значений функции пра-
вой части уравнения, поток значений функции f( t). Мы помещаем начальное значение в первый элемент
результата, а остальные значения получаем рекурсивно.
Определим две вспомогательные функции:
time :: Fractional a => [a]
time = [0, dt .. ]
dist :: Fractional a => Int -> [a] -> [a] -> a
dist n a b = ( / fromIntegral n) $
foldl’ (+) 0 $ take n $ map abs $ zipWith (—) a b
Функция time пробегает все значения отсчётов шага дискретизации по времени. Это тождественная функ-
ция представленная в виде потока с шагом dt.
Функция проверки результата dist принимает два потока и по ним считает расстояние между ними. Эта
функция говорит, что расстояние между двумя потоками в n первых точках равно сумме модулей разности
между значениями потоков. Для того чтобы оценить среднее расхождение, мы делим в конце результат на
число точек.
Также импортируем для удобства символьный синоним для fmap из модуля Control.Applicative.
Ленивее некуда | 189
import Control.Applicative(( ))
…
Проверим функцию int. Для этого сохраним все новые функции в модуле Stream. hs. Загрузим модуль
в интерпретатор и вычислим производную какой-нибудь функции. Найдём решение для правой части кон-