Учебник по Haskell

сания, затем он скажет разверну сначала sum’, эта функция запросит первый элемент списка, что приведёт

к вызову filter. Фильтр будет запрашивать следующий элемент списка у подчинённых ему функций до

тех пор, пока предикат p не вернёт True на одном из них. Всё это время функция map будет вытягивать из

produce по одному элементу. Причём память, выделенная на промежуточные не нужные значения (на них

p вернул False) будет переиспользована. Как только sum’ прибавит первый элемент, она запросит следую-

щий, проснётся фильтр и так далее. Вся функция будет работать в постоянном ограниченном объёме памяти,

который не зависит от величины списка longList!

Примерам ленивых вычислений будет посвящена отдельная глава, а пока приведём один пример. Найдём

корень уравнения с помощью метода неподвижной точки. У нас есть функция f :: a -> a, и нам нужно

найти решение уравнения:

f x = x

Можно начать с какого-нибудь стартового значения, и подставлять, подставлять, подставлять его в f до

тех пор, пока значение не перестанет изменяться. Так мы найдём решение.

x1 = f x0

x2 = f x1

x3 = f x2

...

до тех пор пока abs (x[N] - x[N-1]) <= eps

Первое наблюдение: функция принимает не произвольные значения, а те для которых имеет смысл опе-

рации: минус, поиск абсолютного значения и сравнение на больще/меньше. Тип нашей функции:

f :: (Ord a, Num a) => a -> a

Ленивые вычисления позволяют нам отделить шаг генерации решений, от шага проверки сходимости.

Сначала мы сделаем список всех подстановок функции f, а затем найдём в этом списке два соседних элемента

расстояние между которыми достаточно мало. Итак первый шаг, генерируем всю последовательность:

Пример ленивых вычислений | 151

xNs = iterate f x0

Мы воспользовались стандартной функцией iterate из Prelude. Теперь ищем два соседних числа:

converge :: (Ord a, Num a) => a -> [a] -> a

converge eps (a:b:xs)

| abs (a - b) <= eps

= a

| otherwise

= converge eps (b:xs)

Поскольку список бесконечный мы можем не проверять случаи для пустого списка. Итоговое решение:

roots :: (Ord a, Num a) => a -> a -> (a -> a) -> a

roots eps x0 f = converge eps $ iterate f x0

За счёт ленивых вычислений функции converge и iterate работают синхронно. Функция converge запра-

шивает новое значение и iterate передаёт его, но только одно! Найдём решение какого-нибудь уравнения.

Запустим интерпретатор. Мы ленимся и не создаём новый модуль для такой “большой” функции. Опреде-

ляем её сразу в интерпретаторе.

Prelude> let converge eps (a:b:xs) = if abs (a-b)<=eps then a else converge eps (b:xs) Prelude> let roots eps x0 f = converge eps $ iterate f x0

Найдём корень уравнения:

x( x − 2) = 0

x 2 − 2 x = 0

1 x 2 = x

2

Prelude> roots 0.001 5 (\x -> x*x/2)

Метод завис, остаётся только нажать ctrl+c для остановки. На самом деле есть одно условие для сходи-

мости метода. Метод сойдётся, если модуль производной функции f меньше единицы. Иначе есть возмож-

ность, что мы будем бесконечно генерировать новые подстановки. Вычислим производную нашей функции:

d 1 x 2 = x

dx 2

Нам следует ожидать решения в интервале от минус единицы до единицы:

Prelude> roots 0.001 0.5 (\x -> x*x/2)

3.0517578125e-5

Мы нашли решение, корень равен нулю. В этой записи Ne-5 означает N · 10 − 5

9.5 Краткое содержание

В этой главе мы узнали о том как происходят вычисления в Haskell. Мы узнали, что они ленивые. Всё

вычисляется как можно позже и как можно меньше. Такие вычисления называются вычислениями по необ-

ходимости.

Также мы узнали о вычислениях по значению и вычислениях по имени.

• В вычислениях по значению редукция проводится от листьев дерева выражения к корню

• В вычислениях по имени редукция проводится от корня дерева выражения к листьям.

152 | Глава 9: Редукция выражений

Вычисление по необходимости является улучшением вычисления по имени. Мы не дублируем выражения

во время применения. Мы сохраняем значения в памяти и подставляем в функцию ссылки на значения. После

вычисления значения происходит его обновление в памяти. Так если в одном месте выражение уже было

вычислено и мы обратимся к нему по ссылке из другого места, то мы не будем перевычислять его, а просто

считаем готовое значение.

Мы познакомились с терминологией процесса вычислений. Выражение может находится в нормальной

форме. Это значит что оно вычислено. Может находится в слабой заголовочной нормальной форме. Это значит,

что мы знаем хотя бы один конструктор в корне выражения. Также возможно выражение ещё не вычислялось,

тогда оно является отложенным (thunk).

Суть ленивых вычислений заключается в том, что они происходят синхронно. Если у нас есть композиция

двух функций:

g ( f x)

Внутренняя функция f не начнёт вычисления до тех пор пока значения не понадобятся внешней функции

g. О последствиях этого мы остановимся подробнее в отдельной главе. Значения могут потребоваться только

при сопоставлении с образцом. Когда мы хотим узнать какое из уравнений нам выбрать.