Учебник по Haskell

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)