(&& ) = 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