вычислять промежуточные результаты:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl op init = iter init
where iter res []
= res
iter res (a:as)
= iter (res ‘op‘ a) as
Такая функция называется функцией с хвостовой рекурсией (tail-recursive function). Рекурсия хвостовая
тогда, когда рекурсивный вызов функции является последним действием, которое выполняется в функции.
Посмотрите на второе уравнение функции iter. Мы вызываем функцию iter рекурсивно последним делом. В
языках с вычислением по значению часто хвостовая рекурсия имеет преимущество за счёт экономии памяти
(тот момент который мы обсуждали в самом начале). Но как видно из этого раздела в ленивых языках это не
так. Библиотечная функция sum будет накапливать выражения перед вычислением с риском исчерпать всю
доступную память, потому что она определена через foldl.
Тонкости применения seq
Хочу подчеркнуть, что функция seq не вычисляет свой первый аргумент полностью. Первый аргумент
не приводится к нормальной форме. Мы лишь просим вычислитель узнать какой конструктор находится в
корне у данного выражения. Например в выражении isZero $! infinity знак $! ничем не отличается от
простого применения мы и так будем приводить аргумент infinity к СЗНФ, когда нам понадобится узнать
какое из уравнений для isZero выбрать, ведь в аргументе функции есть сопоставление с образцом.
Посмотрим на один типичный пример. Вычисление среднего для списка чисел. Среднее равно сумме
всех элементов списка, разделённой на длину списка. Для того чтобы вычислить значение за один проход
мы будем одновременно вычислять и сумму элементов и значение длины. Также мы понимаем, что нам не
нужно откладывать вычисления, воспользуемся функцией foldl’:
mean :: [Double] -> Double
mean = division . foldl’ count (0, 0)
where count
(sum, leng) a = (sum+a, leng+1)
division (sum, leng) = sum / fromIntegral leng
Проходим по списку, копим сумму в первом элементе пары и длину во втором. В самом конце делим
первый элемент на второй. Обратите внимание на функцию fromIntegral она преобразует значения из це-
лых чисел, в какие-нибудь другие из класса Num. Сохраним это определение в модуле Strict скомпилируем
модуль и загрузим в интерпретатор, не забудьте импортировать модуль Data.List, он нужен для функции
foldl’. Посмотрим, что у нас получилось:
Prelude Strict> mean [1 .. 1e7]
5000000.5
(49.65 secs, 2476557164 bytes)
Получилось очень медленно, странно ведь порядок этой функции должен быть таким же что и у sum’.
Посмотрим на скорость sum’:
Prelude Strict> sum’ [1 .. 1e7]
5.0000005e13
(0.50 secs, 881855740 bytes)
В 100 раз быстрее. Теперь представьте, что у нас 10 таких функций как mean они разбросаны по всему
коду и делают своё чёрное ленивое дело. Причина такого поведения кроется в том, что мы опять завернули
значение в другой тип, на этот раз в пару. Когда вычислитель дойдёт до seq, он остановится на выражении
(thunk, thunk) вместо двух чисел. Он вновь будет накапливать отложенные вычисления, а не значения.
Перепишем mean, теперь мы будем вычислять значения пары по отдельности и попросим вычислитель
привести к СЗНФ каждое из них перед вычислением итогового значения:
mean’ :: [Double] -> Double
mean’ = division . iter (0, 0)
where iter res
[]
= res
iter (sum, leng)
(a:as)
=
let s = sum
+ a
l = leng + 1
in
s ‘seq‘ l ‘seq‘ iter (s, l) as
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 Пример ленивых вычислений
У вас может сложиться ошибочное представление, что ленивые вычисления созданы только для того,
чтобы с ними бороться. Пока мы рассматривали лишь недостатки, вскользь упомянув о преимуществе выра-
зительности. Ленивые вычисления могут и экономить память! Мы можем строить огромные промежуточные
данные, обрабатывать их разными способами при условии, что в конце программы нам потребуется лишь
