Учебник по Haskell

division (sum, leng) = sum / fromIntegral leng

Аннотации строгости | 149

Такой вот монстр. Функция seq право ассоциативна поэтому скобки будут группироваться в нужном

порядке. В этом определении мы просим вычислитель привести к СЗНФ числа, а не пары чисел, как в прошлой

версии. Для чисел СЗНФ совпадает с НФ, и всё должно пройти гладко, но сохраним это определение и

проверим результат:

Prelude Strict> :! ghc --make Strict

[1 of 1] Compiling Strict

( Strict. hs, Strict. o )

Prelude Strict> :load Strict

Ok, modules loaded: Strict.

(0.00 secs, 0 bytes)

Prelude Strict> mean’ [1 .. 1e7]

5000000.5

(0.65 secs, 1083157384 bytes)

Получилось! Скорость чуть хуже чем у sum’, но не в сто раз.

Энергичные образцы

В GHC предусмотрены специальные обозначения для принудительного приведения выражения к СЗНФ.

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

подключить их. Расширения подключаются с помощью специального комментария в самом начале модуля:

{-# LANGUAGE BangPatterns #-}

Эта запись активирует расширение языка с именем BangPatterns. Ядро языка Haskell фиксировано стан-

дартом, но каждый разработчик компилятора может вносить свои дополнения. Они подключаются через

директиву LANGUAGE:

{-# LANGUAGE

Расширение1,

Расширение2,

Расширение3 #-}

Мы заключаем директиву в специальные комментарии с решёткой, говорим LANGUAGE а затем через за-

пятую перечисляем имена расширений, которые нам понадобятся. Расширения активны только в рамках

данного модуля. Например если мы импортируем функции из модуля, в котором включены расширения, то

эти расширения не распространяются дальше на другие модули. Такие комментарии с решёткой называют

прагмами (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.

У нас в памяти уже два огромных списка. Теперь мы фильтруем весь список и в самом конце суммируем.

Было бы очень плохо заставлять энергичный вычислитель редуцировать такое выражение.

А в это время ленивый вычислитель поступит так. Сначала всё выражение будет сохранено в виде опи-