Учебник по Haskell

Обратите внимание на рекурсивный вызов функции 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 истинно, то мы вернём все элементы

списка, а если ложно отбросим первый элемент. Через foldr можно даже определить функцию с хвостовой

рекурсией foldl. Но это не так просто. Всё же попробуем. Для этого вспомним определение:

foldl :: (a -> b -> a) -> a -> [b] -> a

foldl f s []

= s

foldl f s (a:as)

= foldl f (f s a) as

Нам нужно привести это определение к виду foldr, нам нужно выделить два метода воображаемого

класса списка cons и nil:

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr cons nil = \x -> case x of

a:as

-> a ‘cons‘ foldr cons nil as

[]

-> nil

Перенесём два последних аргумента определения foldl в правую часть, воспользуемся лямбда-

функциями и case-выражением:

foldl :: (a -> b -> a) -> [b] -> a -> a

foldl f = \x -> case x of

[]

-> \s -> s

a:as

->

\s -> foldl f as (f s a)

Мы поменяли местами порядок следования аргументов (второго и третьего). Выделим тождественную

функцию в первом уравнении case-выражения и функцию композиции во втором.

foldl :: (a -> b -> a) -> [b] -> a -> a

foldl f = \x -> case x of

[]

-> id

a:as

-> foldl f as . (flip f a)

Теперь выделим функции cons и nil:

foldl :: (a -> b -> a) -> [b] -> a -> a

foldl f = \x -> case x of

[]

-> nil

a:as

-> a ‘cons‘ foldl f as

where nil

= id

cons

= \a b -> b . flip f a

= \a

-> ( . flip f a)

Теперь запишем через foldr:

foldl :: (a -> b -> a) -> a -> [b] -> a

foldl f s xs = foldr (\a -> ( . flip f a)) id xs s