Учебник по Haskell

Эти функции описывают точку, которая бегает по окружности. Вот математическое определение:

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)