потока чисел 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 Свёртка
Свёртку значения можно представить как процесс, который заменяет в дереве значения все конструкторы