пятую перечисляем имена расширений, которые нам понадобятся. Расширения активны только в рамках
данного модуля. Например если мы импортируем функции из модуля, в котором включены расширения, то
эти расширения не распространяются дальше на другие модули. Такие комментарии с решёткой называют
прагмами (pragma).
Нас интересует расширение BangPatterns (bang – восклицательный знак, вы сейчас поймёте почему оно
так называется). Посмотрим на функцию, которая использует энергичные образцы:
iter (! sum, ! leng) a = (step + a, leng + 1)
В декомпозиции пары перед переменными у нас появились восклицательные знаки. Они говорят вычис-
лителю о том, чтобы он так уж и быть сделал ещё одно усилие и заглянул в корень значений переменных,
которые были переданы в эту функцию.
Вычислитель говорит ладно-ладно сделаю. А там числа! И получается, что они не накапливаются. С помо-
щью энергичных образцов мы можем переписать функцию mean’ через foldl’, а не выписывать её целиком:
mean’’ :: [Double] -> Double
mean’’ = division . foldl’ iter (0, 0)
where iter (! sum, ! leng) a = (sum
+ a, leng + 1)
division (sum, leng) = sum / fromIntegral leng
Проверим в интерпретаторе
*Strict> :! ghc —make Strict
[1 of 1] Compiling Strict
( Strict. hs, Strict. o )
*Strict> :l Strict
Ok, modules loaded: Strict.
(0.00 secs, 581304 bytes)
Prelude Strict> mean’’ [1 .. 1e7]
5000000.5
(0.78 secs, 1412862488 bytes)
Prelude Strict> mean’ [1 .. 1e7]
5000000.5
(0.65 secs, 1082640204 bytes)
Функция работает чуть медленнее, чем исходная версия, но не сильно.
150 | Глава 9: Редукция выражений
Энергичные типы данных
Расширение BangPatterns позволяет указывать какие значения привести к СЗНФ не только в образцах,
но и в типах данных. Мы можем создать тип:
data P a b = P ! a ! b
Этот тип обозначает пару, элементы которой обязаны находиться в СЗНФ. Теперь мы можем написать
ещё один вариант функции поиска среднего:
mean’’’ :: [Double] -> Double
mean’’’ = division . foldl’ iter (P 0 0)
where iter (P sum leng) a = P (sum
+ a) (leng + 1)
division (P sum leng) = sum / fromIntegral leng
9.4 Пример ленивых вычислений
У вас может сложиться ошибочное представление, что ленивые вычисления созданы только для того,
чтобы с ними бороться. Пока мы рассматривали лишь недостатки, вскользь упомянув о преимуществе выра-
зительности. Ленивые вычисления могут и экономить память! Мы можем строить огромные промежуточные
данные, обрабатывать их разными способами при условии, что в конце программы нам потребуется лишь
часть этих данных или конечный алгоритм будет накапливать определённую статистику.
Рассмотрим такое выражение:
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. Теперь ищем два соседних числа: