В функции разметки мы воспользуемся ассоциативным массивом из модуля 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. Загрузим модуль
в интерпретатор и вычислим производную какой-нибудь функции. Найдём решение для правой части кон-
станты и проверим, что у нас получилась тождественная функция:
*Stream> dist 1000 time $ int 0 $ repeat 1
7.37188088351104e-17
Функции практически совпадают, порядок ошибки составляет 10 ? 16. Так и должно быть для линейных
функций. Посмотрим, что будет если в правой части уравнения стоит тождественная функция:
*Stream> dist 1000 ((t -> t^2/2) time) $ int 0 time
2.497500000001403e-4
Решение этого уравнения равно функции t 2 . Здесь мы видим, что результаты уже не такие хорошие.
2
Есть функции, которые определяются рекурсивно в терминах дифференциальных уравнений, например
экспонента будет решением такого уравнения:
dx = x
dt
? t
x( t) = x(0) +
x( ? ) d?
0
Опишем это уравнение в Haskell:
e = int 1 e
Наше описание копирует исходное математическое определение. Добавим это уравнение в модуль Stream
и проверим результаты:
*Stream> dist 1000 (map exp time) e
^CInterrupted.
К сожалению вычисление зависло. Нажмём ctrl+c и разберёмся почему. Для этого распишем вычисление
потока чисел e:
e
— раскроем e
=>
int 1 e
— раскроем int, во втором варгументе
— int стоит декомпозиция,
=>
int 1 e@(f:fs)
— для того чтобы узнать какое уравнение
— для int выбрать нам нужно раскрыть
— второй аргумент, узнать корневой
— конструктор, раскроем второй аргумент:
=>
int 1 (int 1 e)
=>
int 1 (int 1e@(f:fs))
— такая же ситуация
=>
int 1 (int 1 (int 1 e))
Проблема в том, что первый элемент решения мы знаем, мы передаём его первым аргументом и присо-
единяем к решению, но справа от знака равно. Но для того чтобы перейти в правую часть вычислителю нужно
проверить все аргументы, в которых есть декомпозиция. И он начинает проверять, но слишком рано. Нам
бы хотелось, чтобы он сначала присоединил к решению первый аргумент, а затем выполнял бы вычисления
следующего элемента.
C помощью ленивых образцов мы можем отложить декомпозицию второго аргумента на потом:
int :: Fractional a => a -> [a] -> [a]
int x0 ~(f:fs) = x0 : int (x0 + dt * f) fs
Теперь мы видим:
*Stream> dist 1000 (map exp time) e
4.988984990735441e-4
190 | Глава 11: Ленивые чудеса
Вычисления происходят. С помощью взаимно-рекурсивных функций мы можем определить функции си-
нус и косинус:
sinx = int 0 cosx
cosx = int 1 (negate sinx)
Эти функции описывают точку, которая бегает по окружности. Вот математическое определение:
