Unknown - haskell-notes

что мы не вычисляем повторно значения некоторой функции, а сохраняем их и используем в дальнейших

вычислениях. Мы узнали новую синтаксическую конструкцию. Оказывается мы можем не только бороться с

ленью, но и поощрять её. Лень поощряется ленивыми образцами. Они отменяют приведение к слабой заголо-

вочной нормальной форме при декомпозиции аргументов. Они пишутся как обычные образцы, но со знаком

тильда:

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 -> caseb 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 Nata where

zero ::a

succ ::a ->a

Из этого определения следует функция свёртки:

foldNat ::a ->(a ->a) ->( Nat ->a)

foldNat zero succ =\n -> casen of