|—-+
=> Succ (Succ (Succ (Succ (Succ M))))
|
— далее остаётся только подставить уже
|
— вычисленные значения M
|
— и вернуть значение.
|
Итак подставляется не значение а ссылка на него, вычисленная часть значения используется сразу в
нескольких местах. Эта стратегия редукции называется вычислением по необходимости (call by need) или
ленивой стратегией вычислений (lazy evaluation).
Теперь немного терминологии. Значение может находится в четырёх состояниях:
• Нормальная форма (normal form, далее НФ), когда оно полностью вычислено (нет синонимов);
• Слабая заголовочная НФ (weak head NF, далее СЗНФ), когда известен хотя бы один верхний конструк-
тор;
• Отложенное вычисление (thunk), когда известен лишь рецепт вычисления;
• Дно (bottom, часто рисуют как ?), когда известно, что значение не определено.
Вы могли понаблюдать за значением в первых трёх состояниях на примере выше. Но что такое ?? Вспом-
ним определение для функции извлечения головы списка head:
head :: [a] -> a
head (a:_)
= a
head []
= error ”error: empty list”
Второе уравнение возвращает ?. У нас есть две функции, которые возвращают это “значение”:
undefined
:: a
error
:: String -> a
146 | Глава 9: Редукция выражений
Первая – это ? в чистом виде, а вторая не только возвращает неопределённое значение, но и приводит
к выводу на экран сообщения об ошибке. Обратите внимание на тип этих функций, результат может быть
значением любого типа. Это наблюдение приводит нас к ещё одной тонкости. Когда мы определяем тип:
data Bool
= False | True
data Maybe a
= Nothing | Just a
На самом деле мы пишем:
data Bool
= undefined | False | True
data Maybe a
= undefined | Nothing | Just a
Компилятор автоматически прибавляет ещё одно значение к любому определённому пользователем ти-
пу. Такие типы называют поднятыми (lifted type). А значения таких типов принято называть запакованными
(boxed). Не запакованное (unboxed) значение – это простое примитивное значение. Например целое или дей-
ствительное число в том виде, в котором оно хранится на компьютере. В Haskell даже числа “запакованы”.
Поскольку нам необходимо, чтобы undefined могло возвращать в том числе и значение типа Int:
data Int = undefined
| I# Int#
Тип Int# – это низкоуровневое представление ограниченного целого числа. Принято писать не запа-
кованные типы с решёткой на конце. I# – это конструктор. Нам приходится запаковывать значения ещё и
потому, что значение может принимать несколько состояний (в зависимости от того, насколько оно вычис-
лено), всё это ведёт к тому, что у нас хранится не просто значение, а значение с какой-то дополнительной
информацией, которая зависит от конкретной реализации языка Haskell.
Мы решили проблему дублирования вычислений, но наше решение усугубило проблему расхода памяти.
Ведь теперь мы храним не просто значения, но ещё и дополнительную информацию, которая отвечает за
проведение вычислений. Эта проблема может проявляться в очень простых задачах. Например попробуем
вычислить сумму чисел от одного до миллиарда:
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
[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. Она накапливает значения в аргументе, но без принуждения
