станты одинакового типа 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 на второй аргумент, так и получается объединение списков. Обратите внимание на эту особенность,
скорость выполнения операции (++) зависит от длины первого списка. Поэтому между двумя выражениями
((a ++ b) ++ c) ++ d
a ++ (b ++ (c ++ d))
Нет разницы в итоговом результате, но есть огромная разница по скорости вычисления! Второй гораздо
быстрее. Убедитесь в этом! Реализуем объединение списка списков в один список:
concat :: [[a]] -> [a]
concat = foldr (++) []
194 | Глава 12: Структурная рекурсия
Через свёртку можно реализовать и функцию преобразования списков:
map :: (a -> b) -> [a] -> [b]
map f = foldr ((:) . f) []
Если смысл выражения ((:) . f) не совсем понятен, давайте распишем его типы:
f
(:)
a
——->
b
——->
([b] -> [b])
Напишем функцию фильтрации:
filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr (a as -> foldBool (a:as) as (p a)) []
Тут у нас целых две функции свёртки. Если значение предиката p истинно, то мы вернём все элементы