-> \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
Кажется мы ошиблись в аргументах, ведь foldr принимает три аргумента. Дело в том, что в функции
foldr мы сворачиваем списки в функции, последний аргумент предназначен как раз для результирующей
функции. Отметим, что из определения можно исключить два последних аргумента с помощью функции
flip.
Свёртка | 195
Вычислительные особенности foldl и foldr
Если посмотреть на выражение, которое получается в результате вычисления foldr и foldl можно понять
почему они так называются.
В левой свёртке foldl скобки группируются влево, поэтому на конце l (left):
foldl f s [a1, a2, a3, a4] =
(((s ‘f‘ a1) ‘f‘ a2) ‘f‘ a3) ‘f‘ a4
В правой свёртке foldr скобки группируются вправо, поэтому на конце r (right):
foldr f s [a1, a2, a3, a4]
a1 ‘f‘ (a2 ‘f‘ (a3 ‘f‘ (a4 ‘f‘ s)))
Кажется, что если функция f ассоциативна
(a ‘f‘ b) ‘f‘ c
= a ‘f‘ (b ‘f‘ c)
то нет разницы какую свёртку применять. Разницы нет по смыслу, но может быть существенная разница
в скорости вычисления. Рассмотрим функцию concat, ниже два определения:
concat
= foldl (++) []
concat
= foldr (++) []
Какое выбрать? Результат и в том и в другом случае одинаковый (функция ++ ассоциативна). Стоит вы-