вычисляется как можно позже и как можно меньше. Такие вычисления называются вычислениями по необ-
ходимости.
Также мы узнали о вычислениях по значению и вычислениях по имени.
• В вычислениях по значению редукция проводится от листьев дерева выражения к корню
• В вычислениях по имени редукция проводится от корня дерева выражения к листьям.
152 | Глава 9: Редукция выражений
Вычисление по необходимости является улучшением вычисления по имени. Мы не дублируем выражения
во время применения. Мы сохраняем значения в памяти и подставляем в функцию ссылки на значения. После
вычисления значения происходит его обновление в памяти. Так если в одном месте выражение уже было
вычислено и мы обратимся к нему по ссылке из другого места, то мы не будем перевычислять его, а просто
считаем готовое значение.
Мы познакомились с терминологией процесса вычислений. Выражение может находится в нормальной
форме. Это значит что оно вычислено. Может находится в слабой заголовочной нормальной форме. Это значит,
что мы знаем хотя бы один конструктор в корне выражения. Также возможно выражение ещё не вычислялось,
тогда оно является отложенным (thunk).
Суть ленивых вычислений заключается в том, что они происходят синхронно. Если у нас есть композиция
двух функций:
g ( f x)
Внутренняя функция f не начнёт вычисления до тех пор пока значения не понадобятся внешней функции
g. О последствиях этого мы остановимся подробнее в отдельной главе. Значения могут потребоваться только
при сопоставлении с образцом. Когда мы хотим узнать какое из уравнений нам выбрать.
Иногда ленивые вычисления не эффективны по расходу памяти. Это происходит когда выражение состоит
из большого числа подвыражений, которые будут вычислены в любом случае. В Haskell у нас есть способы
борьбы с ленью. Это функция seq, энергичные образцы и энергичные типы данных.
Функция seq:
seq :: a -> b -> b
Сначала приводит к слабой заголовочной форме свой первый аргумент, а затем возвращает второй.
Взрывные образцы выполняют те же функции, но они используются в декомпозиции аргументов или в объ-
явлении типа.
9.6 Упражнения
• Потренируйтесь в понимании того как происходят ленивые вычисления. Вычислите на бумаге следу-
ющие выражения (если это возможно):
– sum $ take 3 $ filter (odd . fst) $ zip [1 .. ] [1, undefined, 2, undefined, 3, undefined,
undefined]
– take 2 $ foldr (+) 0 $ map Succ $ repeat Zero
– take 2 $ foldl (+) 0 $ map Succ $ repeat Zero
• Функция seq приводит первый аргумент к СЗНФ, убедитесь в этом на таком эксперименте. Определите
тип:
data TheDouble = TheDouble { runTheDouble :: Double }
Он запаковывает действительные числа в конструктор. Определите для этого типа экземпляр класса
Num и посмотрите как быстро будет работать функция sum’ на таких числах. Как изменится скорость
если мы заменим в определении типа data на newtype? как изменится скорость, если мы вернём data,
но сделаем тип TheDouble энергичным? Поэкспериментируйте.
• Посмотрите на приведение к СЗНФ в энергичных типах данных. Определите два типа:
data Strict a = Strict ! a
data Lazy
a = Lazy
a
И повычисляйте в интерпретаторе различные значения с undefined, const, ($! ) и seq: