прибавлять значения первой ячейки. У ленивой стратегии другое мнение на этот счёт. Если вы вернётесь к
примеру выше, то заметите, что sum копит отложенные выражения до самого последнего момента. Поскольку
память ограничена, такой момент не наступает. Как нам быть? В Haskell по умолчанию все вычисления про-
водятся по необходимости, но предусмотрены и средства для имитации вычисления по значению. Давайте
посмотрим на них.
9.3 Аннотации строгости
Языки с ленивой стратегией вычислений называют не строгими (non-strict), а языки с энергичной стра-
тегией вычислений соответственно~– строгими.
Принуждение к СЗНФ с помощью seq
Мы говорили о том, что при вычислении по имени значения вычисляются только при сопоставлении с
образцом или в case-выражениях. Есть специальная функция seq, которая форсирует приведение к СЗНФ:
seq :: a -> b -> b
Она принимает два аргумента, при выполнении функции первый аргумент приводится к СЗНФ и затем
возвращается второй. Вернёмся к примеру с sum. Привести к СЗНФ число – означает вычислить его полностью.
Определим функцию sum’, которая перед рекурсивным вызовом вычисляет промежуточный результат:
sum’ :: Num a => [a] -> a
sum’ = iter 0
where iter res []
= res
iter res (a:as)
= let res’ = res + a
in
res’ ‘seq‘ iter res’ as
Аннотации строгости | 147
Сохраним результат в отдельном модуле Strict. hs и попробуем теперь вычислить значение, придётся
подождать:
Strict> sum’ [1 .. 1e9]
И мы ждём, и ждём, и ждём. Но переполнения памяти не происходит. Это хорошо. Но давайте прервём
вычисления. Нажмём ctrl+c. Функция sum’ вычисляется, но вычисляется очень медленно. Мы можем су-
щественно ускорить её, если скомпилируем модуль Strict. Для компиляции модуля переключимся в его
текущую директорию и вызовем компилятор ghc с флагом –make:
ghc --make Strict
Появились два файла Strict. hi и Strict. o. Теперь мы можем загрузить модуль Strict в интерпретатор
и сравнить выполнение двух функций:
Strict> sum’ [1 .. 1e6]
5.000005e11
(0.00 secs, 89133484 bytes)
Strict> sum [1 .. 1e6]
5.000005e11
(0.57 secs, 142563064 bytes)
Обратите внимание на прирост скорости. Умение понимать в каких случаях стоит ограничить лень очень
важно. И в программах на Haskell тоже. Также компилировать модули можно из интерпретатора. Для этого
воспользуемся командой :! , она выполняет системные команды в интерпретаторе ghci:
Strict> :! ghc --make Strict
[1 of 1] Compiling Strict
( Strict. hs, Strict. o )
Отметим наличие специальной функции применения, которая просит перед применением привести ар-
гумент к СЗНФ, эта функция определена в Prelude:
($! ) :: (a -> b) -> a -> b
f $! a = a ‘seq‘ f a
С этой функцией мы можем определить функцию sum так:
sum’ :: Num a => [a] -> a
sum’ = iter 0
where iter res []
= res
iter res (a:as)
= flip iter as $! res + a
Функции с хвостовой рекурсией
Определим функцию, которая не будет лениться при вычислении произведения чисел, мы назовём её
product’:
product’ :: Num a => [a] -> a
product’ = iter 1
where iter res []
= res
iter res (a:as)
= let res’ = res * a
in
res’ ‘seq‘ iter res’ as
Смотрите функция sum изменилась лишь в двух местах. Это говорит о том, что пора задуматься о том,
а нет ли такой общей функции, которая включает в себя и то и другое поведение. Такая функция есть и
называется она foldl’, вот её определение:
foldl’ :: (a -> b -> a) -> a -> [b] -> a
foldl’ op init = iter init
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. Она накапливает значения в аргументе, но без принуждения