Ленивые вычисления.

Небольшой фрагмент книги «Functional Programming in CLEAN» в моем вольном переводе.

Метод вычисления выражений, используемый Clean, носит название ленивые вычисления (ЛВ). Это означает, что вычисляются только те части выражения, которые непосредственно необходимы для получения результата. Антоним ЛВ — энергичные вычисления (strict, eager). В этом случае, перед расчетом результата обязательно вычисляются значения всех аргументов функции.
Благодаря ЛВ в языке Clean доступна такая абстракция как бесконечные списки:
[1..] — это бесконечная последовательность натуральных чисел, начинающаяся с 1.
Кроме этого, ЛВ имеют много других преимуществ, рассмотрим к примеру определение простого числа:
prime :: Int -> Bool
prime x = divisors x == [1,x],
где функция divisors x определяет список всех делителей x.
Неужели эта функция будет определять все делители и, затем, сравнивать их с со списком [1,x]? Как бы не так! При вызове prime 30 произойдет следующее. Для начала, будет определен первый делитель: 1. Это значение будет сравниваться с первым элементом списка [1,30]. Результат пока истинен. Затем будет определен второй делитель: 2. Это число сравнивается со вторым элементом списка [1,30]: они не равны. Оператор == знает, что два списка не равны, если встречается хотя бы один несовпадающий элемент. Поэтому немедленно будет возвращено значение «ложь». Остальные делители никогда не будут вычисляться!
Ленивое поведение оператора == следует из его определения. Рекурсивная строка из определения оператора для списков выглядит так:
(==) [x:xs] [y:ys] = x==y && xs==ys
Т.е. если x==y возвращает «ложь», нет необходимости вычислять xs==ys, результат заведомо будет «ложь». Это, опять же, следует из определения оператора &&:
(&&) False x = False
(&&) True x = x
Если левый аргумент — «ложь», правый можно не вычислять.
Аргумент называется энергичным, когда без его вычисления невозможно вычислить и функцию. Для оператора + оба аргумента энергичные, т.к. без них нельзя вычислить их сумму. В Clean существует способ явного определения энергичных аргументов с помощью знака !, хотя в большинстве случаев компилятор сам способен это определить.
Прим. Подобная оптимизация возможна и в императивных языках, но в этом случае необходимо явно формулировать условия окончания вычислений. Далее следует более сложный и неочевидный пример.
С использованием бесконечных списков можно получить определение всех простых чисел:
filter prime [2..]
Функция filter возвращает только те элементы входного списка, которые отвечают заданным условиям (в данном случае условие — функция prime).
Функция prime ищет делители числа, если такие делители достаточно большие, это может занять много времени. Использование функции iterate позволяет написать максимально эффективный алгоритм. Определение функции iterate следующее:
iterate :: (a->a) a -> [a]
iterate f x = [x: iterate f (f x)]
Т.е. она формирует бесконечный список значений результатов последовательного применения функции f к x.
Данный метод также начинается с бесконечного списка [2..]:
[2,3,4,5,6,7,8,9,10,11,…
Первый элемент, 2, может быть сохранен в списке простых. Затем, 2 и все числа, для которых 2 является делителем, могут быть вычеркнуты. Вот, что остается:
[3,5,7,9,11,13,15,17,19,21,…
Первое число, 3 – это простое число. Оно, и все числа, для которых оно делитель, могут быть вычеркнуты:
[5,7,11,13,17,19,23,25,29,31,…
Тот же процесс можно повторить и для 5:
[7,11,13,17,19,23,29,31,37,41,…
И т.д., и т.д. Функция «вычеркнуть все числа, для которых первый элемент является делителем» всегда применяется к предыдущему результату:
iterate crossout [2..]
where
crossout [x:xs] = filter (not o multiple x) xs
multiple x y = divisible y x
Функцию divisible можно определить как:
divisible t n = t rem n == 0
Т.к. начальное значение – бесконечный список, то результатом этого будет бесконечный список бесконечных списков. Этот супер-список будет выглядеть так:
[[2,3,4,5,6,7,8,9,10,11,12,13,14,…
,[3,5,7,9,11,13,15,17,19,21,23,25,27,…
,[5,7,11,13,17,19,23,25,29,31,35,37,41,…
,[7,11,13,17,19,23,29,31,37,41,43,47,49,…
,[11,13,17,19,23,29,31,37,41,43,47,51,53,…
,…
Вы никогда не сможете увидеть все это в целом, если вы попытаетесь вычислить это, вы не выйдете за пределы первого списка. Но для видимого результата. Необходимо завершить начатое: требуемые простые числа — это первые элементы каждого из списков. Т.е. список простых чисел определяется путем взятия голов (hd) каждого из списков:
primenums :: [Int]
primenums = map hd (iterate crossout [2..])
where
crossout [x:xs] = filter (not o (multiple x)) xs
Трудно представить, какое значение будет вычисляться в какой момент времени. Но это и не нужно: в процессе программирования мы считаем, что бесконечные списки реально существуют, все остальное оптимизируется благодаря ЛВ.
Данный метод вычисления простых чисел носит название решета Эратосфена.
Прим. В языке D 2.0. есть поддержка ленивых вычислений, см. Lazy функции

И еще немного о ленивых вычислениях:

Генераторы Python и ленивые вычисления