Объединение списков:
(++) :: [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