sum [1 .. 1e9]
< interactive>: out of memory (requested 2097152 bytes)
Интуитивно кажется, что для решения этой задачи нам нужно лишь две ячейки памяти. В одной мы бу-
дем постоянно прибавлять к значению единицу, пока не дойдём до миллиарда, так мы последовательно
будем получать элементы списка, а в другой мы будем хранить значение суммы. Мы начнём с нуля и будем
прибавлять значения первой ячейки. У ленивой стратегии другое мнение на этот счёт. Если вы вернётесь к
примеру выше, то заметите, что 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