на подходящие по типу функции.
Логические значения
Вспомним определение логических значений:
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