*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!