dx
=
y
dt
dy
=
?x
dt
x(0)
=
0
y(0)
=
1
Проверим в интерпретаторе:
*Stream> dist 1000 (sin time) sinx
1.5027460329809257e-4
*Stream> dist 1000 (cos time) cosx
1.9088156807382827e-4
Так с помощью ленивых образцов нам удалось попасть в правую часть уравнения для функции int, не рас-
крывая до конца аргументы в левой части. С помощью этого мы могли ссылаться в сопоставлении с образцом
на значение, которое ещё не было вычислено.
11.5 Краткое содержание
Ленивые вычисления повышают модульность программ. Мы можем в одной части программы создать все
возможные решения, а в другой выбрать лучшие по какому-либо признаку. Также мы посмотрели на инте-
ресную технику написания рекурсивных функций, которая называется мемоизацией. Мемоизация означает,
что мы не вычисляем повторно значения некоторой функции, а сохраняем их и используем в дальнейших
вычислениях. Мы узнали новую синтаксическую конструкцию. Оказывается мы можем не только бороться с
ленью, но и поощрять её. Лень поощряется ленивыми образцами. Они отменяют приведение к слабой заголо-
вочной нормальной форме при декомпозиции аргументов. Они пишутся как обычные образцы, но со знаком
тильда:
lazyHead ~(x:xs) = x
Мы говорим вычислителю: поверь мне, это значение может иметь только такой вид, потом посмотришь
так ли это, когда значения тебе понадобятся. Поэтому ленивые образцы проходят сопоставление с образцом
в любом случае.
Сопоставление с образцом в let и where выражениях является ленивым. Функцию lazyHead мы могли бы
написать и так:
lazyHead a = x
where (x:xs) = a
lazyHead a =
let (x:xs) = a
in
x
11.6 Упражнения
Мы побывали на выставке ленивых программ. Присмотритесь ещё раз к решениям задач этой главы и
подумайте какую роль сыграли ленивые вычисления в каждом из случаев, какие мотивы обыгрываются в
этих примерах. Также подумайте каким было бы решение, если бы в Haskell использовалась стратегия вы-
числения по значению. Критически настроенные читатели могут с помощью профилирования проверить
эффективность программ из этой главы.
Краткое содержание | 191
Глава 12
Структурная рекурсия
Структурная рекурсия определяет способ построения и преобразования значений по виду типа (по со-
ставу его конструкторов). Функции, которые преобразуют значения мы будем называть свёрткой (fold), а
функции которые строят значения – развёрткой (unfold). Эта рекурсия встречается очень часто, мы уже поль-
зовались ею и не раз, но в этой главе мы остановимся на ней поподробнее.
12.1 Свёртка
Свёртку значения можно представить как процесс, который заменяет в дереве значения все конструкторы
на подходящие по типу функции.
Логические значения
Вспомним определение логических значений:
data Bool = True | False
У нас есть два конструктора-константы. Любое значение типа Bool может состоять либо из одного кон-
структора True, либо из одного конструктора False. Функция свёртки в данном случае принимает две кон-
станты одинакового типа a и возвращает функцию, которая превращает значение типа Bool в значение
типа a, заменяя конструкторы на переданные значения:
foldBool :: a -> a -> Bool -> a
foldBool true false = b -> case b of
True
-> true
False
-> false
Мы написали эту функцию в композиционном стиле для того, чтобы подчеркнуть, что функция преобра-
зует значение типа Bool. Определим несколько знакомых функций через функцию свёртки, начнём с отри-
цания:
not :: Bool -> Bool
not = foldNat False True
Мы поменяли конструкторы местами, если на вход поступит True, то мы вернём False и наоборот. Теперь
посмотрим на “и” и “или”:
(||), (&& ) :: Bool -> Bool -> Bool
(||) = foldNat
(const True)
id
(&& ) = foldNat
id
(const False)
Определение функций “и” и “или” через свёртки подчёркивает, что они являются взаимно обратными.
Смотрите, эти функции принимают значение типа Bool и возвращают функцию Bool -> Bool. Фактически
функция свёртки для Bool является if-выражением, только в этот раз мы пишем условие в конце.
192 | Глава 12: Структурная рекурсия
Натуральные числа
У нас был тип для натуральных чисел Пеано:
data Nat = Zero | Succ Nat
Помните мы когда-то записывали определения типов в стиле классов:
data Nat where
Zero :: Nat
Succ :: Nat -> Nat
Если мы заменим конструктор Zero на значение типа a, то конструктор Succ нам придётся заменять на
функцию типа a -> a, иначе мы не пройдём проверку типов. Представим, что Nat это класс:
data Nat a where
zero :: a
succ :: a -> a
Из этого определения следует функция свёртки:
foldNat :: a -> (a -> a) -> (Nat -> a)
foldNat zero succ = n -> case n of
Zero
-> zero
Succ m
-> succ (foldNat zero succ m)
Обратите внимание на рекурсивный вызов функции foldNat мы обходим всё дерево значения, заменяя
каждый конструктор. Определим знакомые функции через свёртку:
isZero :: Nat -> Bool
isZero = foldNat True (const False)
Посмотрим как вычисляется эта функция:
isZero Zero
=>
True
— заменили конструктор Zero
isZero (Succ (Succ (Succ Zero)))
=>
const False (const False (const False True))
— заменили и Zero и Succ
=>
False
Что интересно за счёт ленивых вычислений на самом деле во втором выражении произойдёт лишь одна
замена. Мы не обходим всё дерево, нам это и не нужно, а смотрим лишь на первый конструктор, если там
Succ, то произойдёт замена на постоянную функцию, которая игнорирует свой второй аргумент и рекурсив-
ного вызова функции свёртки не произойдёт, совсем как в исходном определении!
even, odd :: Nat -> Bool
even
= foldNat True
not
odd
= foldNat False not
Эти функции определяют чётность числа, сдесь мы пользуемся тем свойством, что not (not a) == a.
Определим сложение и умножение:
add, mul :: Nat -> Nat -> Nat
add a
= foldNat a
Succ
mul a
= foldNat Zero
(add a)
Свёртка | 193
Maybe
Вспомним определение типа для результата частично определённых функций:
data Maybe a = Nothing | Just a
Перепишем словно это класс:
data Maybe a b where
Nothing :: b
Just
:: a -> b
Этот класс принимает два параметра, поскольку исходный тип Maybe принимает один. Теперь несложно
догадаться как будет выглядеть функция свёртки, мы просто получим стандартную функцию maybe. Дадим
определение экземпляра функтора и монады через свёртку:
instance Functor Maybe where
fmap f = maybe Nothing (Just . f)
instance Monad Maybe where
return
= Just
ma >>= mf
= maybe Nothing mf ma
Списки
Функция свёртки для списков это функция foldr. Выведем её из определения типа:
data [a] = a : [a] | []
Представим, что это класс:
class [a] b where
cons
:: a -> b -> b
nil
:: b
Теперь получить определение для foldr совсем просто:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil = x -> case x of
a:as
-> a ‘cons‘ foldr cons nil as
[]
-> nil
Мы обходим дерево значения, заменяя конструкторы методами нашего воображаемого класса. Опреде-
лим несколько стандартных функций для списков через свёртку.
Первый элемент списка:
head :: [a] -> a
head = foldr const (error ”empty list”)
Объединение списков:
(++) :: [a] -> [a] -> [a]
a ++ b = foldr (:) b a
В этой функции мы реконструируем заново первый список но в самом конце заменяем пустой список в
хвосте a на второй аргумент, так и получается объединение списков. Обратите внимание на эту особенность,
