часть этих данных или конечный алгоритм будет накапливать определённую статистику.
Рассмотрим такое выражение:
let longList = produce x
in
sum’ $ filter p $ map f longList
Функция produce строит огромный список промежуточных данных. Далее мы преобразуем эти данные
функцией f и фильтруем их предикатом p. Всё это делается для того, чтобы посчитать сумму всех элементов
в списке. Посмотрим как повела бы себя в такой ситуации энергичная стратегия вычислений. Сначала был
бы вычислен список longList, причём полностью. Затем все элементы были бы преобразованы функцией f.
У нас в памяти уже два огромных списка. Теперь мы фильтруем весь список и в самом конце суммируем.
Было бы очень плохо заставлять энергичный вычислитель редуцировать такое выражение.
А в это время ленивый вычислитель поступит так. Сначала всё выражение будет сохранено в виде опи-
сания, затем он скажет разверну сначала 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. О последствиях этого мы остановимся подробнее в отдельной главе. Значения могут потребоваться только
при сопоставлении с образцом. Когда мы хотим узнать какое из уравнений нам выбрать.
Иногда ленивые вычисления не эффективны по расходу памяти. Это происходит когда выражение состоит
из большого числа подвыражений, которые будут вычислены в любом случае. В Haskell у нас есть способы
борьбы с ленью. Это функция seq, энергичные образцы и энергичные типы данных.
Функция seq:
seq :: a -> b -> b
Сначала приводит к слабой заголовочной форме свой первый аргумент, а затем возвращает второй.
Взрывные образцы выполняют те же функции, но они используются в декомпозиции аргументов или в объ-
явлении типа.
9.6 Упражнения
• Потренируйтесь в понимании того как происходят ленивые вычисления. Вычислите на бумаге следу-
ющие выражения (если это возможно):
– sum $ take 3 $ filter (odd . fst) $ zip [1 .. ] [1, undefined, 2, undefined, 3, undefined,
undefined]
– take 2 $ foldr (+) 0 $ map Succ $ repeat Zero
– take 2 $ foldl (+) 0 $ map Succ $ repeat Zero
• Функция seq приводит первый аргумент к СЗНФ, убедитесь в этом на таком эксперименте. Определите
тип:
data TheDouble = TheDouble { runTheDouble :: Double }
Он запаковывает действительные числа в конструктор. Определите для этого типа экземпляр класса
Num и посмотрите как быстро будет работать функция sum’ на таких числах. Как изменится скорость
если мы заменим в определении типа data на newtype? как изменится скорость, если мы вернём data,
но сделаем тип TheDouble энергичным? Поэкспериментируйте.
