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 и niclass="underline"
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 и niclass="underline"
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
Кажется мы ошиблись в аргументах, ведь foldr принимает три аргумента. Дело в том, что в функции