= 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