Unknown - haskell-notes

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 ::( Orda, Numa) =>a ->a

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

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

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

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

xNs =iterate f x0

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

converge ::( Orda, Numa) =>a ->[a] ->a

converge eps (a :b :xs)

|abs (a -b) <=eps

=a

|otherwise

=converge eps (b :xs)

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

roots ::( Orda, Numa) =>a ->a ->(a ->a) ->a

roots eps x0 f =converge eps $iterate f x0

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

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

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

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

Prelude> letconverge eps (a :b :xs) = ifabs (a -b) <=eps thena elseconverge eps (b :xs) Prelude> letroots 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: Редукция выражений

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

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

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

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

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

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