Учебник по Haskell

Вы могли понаблюдать за значением в первых трёх состояниях на примере выше. Но что такое ⊥? Вспом-

ним определение для функции извлечения головы списка 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 тоже. Также компилировать модули можно из интерпретатора. Для этого