where iter res []
= res
iter res (a:as)
= let res’ = res ‘op‘ a
in
res’ ‘seq‘ iter res’ as
Мы вынесли в аргументы функции бинарную операцию и начальное значение. Всё остальное осталось
прежним. Эта функция живёт в модуле Data.List. Теперь мы можем определить функции sum’ и prod’:
148 | Глава 9: Редукция выражений
sum’
= foldl’ (+) 0
product’
= foldl’ (*) 1
Также в Prelude определена функция foldl. Она накапливает значения в аргументе, но без принуждения
вычислять промежуточные результаты:
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 а затем через за-