станты и проверим, что у нас получилась тождественная функция:
*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)
Эти функции описывают точку, которая бегает по окружности. Вот математическое определение:
dx
=
y
dt
dy
=
?x
dt
x(0)
=
0
y(0)
=
1
Проверим в интерпретаторе:
*Stream> dist 1000 (sin time) sinx
1.5027460329809257e-4
*Stream> dist 1000 (cos time) cosx
1.9088156807382827e-4
Так с помощью ленивых образцов нам удалось попасть в правую часть уравнения для функции int, не рас-
крывая до конца аргументы в левой части. С помощью этого мы могли ссылаться в сопоставлении с образцом
на значение, которое ещё не было вычислено.
11.5 Краткое содержание
Ленивые вычисления повышают модульность программ. Мы можем в одной части программы создать все
возможные решения, а в другой выбрать лучшие по какому-либо признаку. Также мы посмотрели на инте-
ресную технику написания рекурсивных функций, которая называется мемоизацией. Мемоизация означает,
что мы не вычисляем повторно значения некоторой функции, а сохраняем их и используем в дальнейших
вычислениях. Мы узнали новую синтаксическую конструкцию. Оказывается мы можем не только бороться с
ленью, но и поощрять её. Лень поощряется ленивыми образцами. Они отменяют приведение к слабой заголо-
вочной нормальной форме при декомпозиции аргументов. Они пишутся как обычные образцы, но со знаком
тильда:
lazyHead ~(x:xs) = x
Мы говорим вычислителю: поверь мне, это значение может иметь только такой вид, потом посмотришь
так ли это, когда значения тебе понадобятся. Поэтому ленивые образцы проходят сопоставление с образцом
в любом случае.
Сопоставление с образцом в let и where выражениях является ленивым. Функцию lazyHead мы могли бы
написать и так:
lazyHead a = x
where (x:xs) = a
lazyHead a =
let (x:xs) = a
in
x
11.6 Упражнения
Мы побывали на выставке ленивых программ. Присмотритесь ещё раз к решениям задач этой главы и
подумайте какую роль сыграли ленивые вычисления в каждом из случаев, какие мотивы обыгрываются в
этих примерах. Также подумайте каким было бы решение, если бы в Haskell использовалась стратегия вы-
числения по значению. Критически настроенные читатели могут с помощью профилирования проверить
эффективность программ из этой главы.
Краткое содержание | 191
Глава 12
Структурная рекурсия
Структурная рекурсия определяет способ построения и преобразования значений по виду типа (по со-
ставу его конструкторов). Функции, которые преобразуют значения мы будем называть свёрткой (fold), а
функции которые строят значения – развёрткой (unfold). Эта рекурсия встречается очень часто, мы уже поль-
зовались ею и не раз, но в этой главе мы остановимся на ней поподробнее.
12.1 Свёртка
Свёртку значения можно представить как процесс, который заменяет в дереве значения все конструкторы
на подходящие по типу функции.
Логические значения
Вспомним определение логических значений:
data Bool = True | False
У нас есть два конструктора-константы. Любое значение типа Bool может состоять либо из одного кон-
структора True, либо из одного конструктора False. Функция свёртки в данном случае принимает две кон-