Foldr & foldl Объяснение Haskell

Ответ 1

Достаточно канонический источник по этому вопросу - Foldr Foldl Foldl ' в Haskell Wiki. Таким образом, в зависимости от того, насколько строго вы можете комбинировать элементы списка и каков результат вашей складки, вы можете выбрать либо foldr, либо foldl'. Это редко правильный выбор для выбора foldl.

Как правило, это хороший пример того, как вы должны учитывать ленивость и строгость своих функций, чтобы эффективно вычислять в Haskell. В строгих языках определение хвоста-рекурсии и TCO - это название игры, но такие определения могут быть слишком "непроизводительными" (недостаточно ленивыми) для Haskell, что приводит к производству бесполезных thunks и меньше возможностей для оптимизации.

Когда выбрать foldr

Если операция, которая потребляет результат вашей складки, может работать лениво, и ваша функция объединения не является строгой в ее правильном аргументе, тогда foldr обычно является правильным выбором. Ключевым примером этого является nonfold. Сначала мы видим, что (:) является нестрогим справа

head (1 : undefined)
1

Тогда здесь nonfold, записанный с использованием foldr

nonfoldr :: [a] -> [a]
nonfoldr = foldr (:) []

Так как (:) создает списки лениво, выражение, подобное head . nonfoldr, может быть очень эффективным, требуя всего лишь одного шага сложения и заставляя только заголовок списка ввода.

head (nonfoldr [1,2,3])
head (foldr (:) [] [1,2,3])
head (1 : foldr (:) [] [2,3])
1

Замыкание

Очень распространенное место, где побеждает лень, - это короткие вычисления. Например, lookup :: Eq a => a -> [a] -> Bool может быть более продуктивным, возвращая момент, когда он видит совпадение.

lookupr :: Eq a => a -> [a] -> Bool
lookupr x = foldr (\y inRest -> if x == y then True else inRest) False

Короткое замыкание происходит, потому что мы отбрасываем isRest в первой ветки if. То же самое, что реализовано в foldl', не может этого сделать.

lookupl :: Eq a => a -> [a] -> Bool
lookupl x = foldl' (\wasHere y -> if wasHere then wasHere else x == y) False

lookupr 1 [1,2,3,4]
foldr fn False [1,2,3,4]
if 1 == 1 then True else (foldr fn False [2,3,4])
True

lookupl 1 [1,2,3,4]
foldl' fn False [1,2,3,4]
foldl' fn True [2,3,4]
foldl' fn True [3,4]
foldl' fn True [4]
foldl' fn True []
True

Когда выбрать foldl'

Если операция потребления или комбинирование требует, чтобы весь список обрабатывался до его продолжения, тогда foldl' обычно является правильным выбором. Часто лучшая проверка для этой ситуации заключается в том, чтобы спросить себя, является ли ваша функция комбинирования строгой - если она строго указана в первом аргументе, тогда весь ваш список должен быть принудительно принудительно. Ключевым примером этого является sum

sum :: Num a => [a] -> a
sum = foldl' (+) 0

так как (1 + 2) не может быть разумно потреблен до фактического выполнения добавления (Haskell недостаточно умен, чтобы знать, что 1 + 2 >= 1 без предварительной оценки 1 + 2), тогда мы не получаем никакой пользы от использования foldr, Вместо этого мы будем использовать свойство строкового объединения foldl', чтобы убедиться, что мы оцениваем вещи так же охотно, насколько это необходимо

sum [1,2,3]
foldl' (+) 0 [1,2,3]
foldl' (+) 1 [2,3]
foldl' (+) 3 [3]
foldl' (+) 6 []
6

Заметим, что если мы выберем foldl здесь, мы не получим вполне правильный результат. Если foldl имеет ту же ассоциативность, что и foldl', это не приводит к тому, что операция объединения с seq аналогична foldl'.

sumWrong :: Num a => [a] -> a
sumWrong = foldl (+) 0

sumWrong [1,2,3]
foldl (+) 0 [1,2,3]
foldl (+) (0 + 1) [2,3]
foldl (+) ((0 + 1) + 2) [3]
foldl (+) (((0 + 1) + 2) + 3) []
(((0 + 1) + 2) + 3)
((1       + 2) + 3)
(3             + 3)
6

Что происходит, когда мы выбираем неправильно?

Мы получаем лишние бесполезные трюки (космическая утечка), если мы выбираем foldr или foldl в foldl' сладком месте, и мы получаем дополнительную, бесполезную оценку (временную утечку), если мы выберем foldl', когда foldr было бы лучшим выбором.

nonfoldl :: [a] -> [a]
nonfoldl = foldl (:) []

head (nonfoldl [1,2,3])
head (foldl (:) []  [1,2,3])
head (foldl (:) [1]   [2,3])
head (foldl (:) [1,2]   [3])  -- nonfoldr finished here, O(1)
head (foldl (:) [1,2,3]  [])
head [1,2,3]
1                             -- this is O(n)

sumR :: Num a => [a] -> a
sumR = foldr (+) 0

sumR [1,2,3]
foldr (+) 0 [1,2,3]
1 + foldr (+) 0 [2, 3]      -- thunks begin
1 + (2 + foldr (+) 0 [3])
1 + (2 + (3 + foldr (+) 0)) -- O(n) thunks hanging about
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6                           -- forced O(n) thunks

Ответ 2

В языках со строгой/нетерпеливой оценкой складывание слева может выполняться в постоянном пространстве, а сворачивание справа требует линейного пространства (по числу элементов списка). Из-за этого многие люди, которые впервые обращаются к Haskell, приходят с этим предубеждением.

Но это эмпирическое правило не работает в Haskell, из-за ленивой оценки. В Haskell возможно записывать постоянные пространственные функции с помощью foldr. Вот один пример:

find :: (a -> Bool) -> [a] -> Maybe a
find p = foldr (\x next -> if p x then Just x else next) Nothing

Попробуйте оценить вручную find even [1, 3, 4]:

-- The definition of foldr, for reference:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

find even (1:3:4:[])
    = foldr (\x next -> if even x then Just x else next) (1:3:4:[])
    = if even 1 then Just 1 else foldr (\x next -> if even x then Just x else next) (3:4:[])
    = foldr (\x next -> if even x then Just x else next) (3:4:[])
    = if even 3 then Just 3 else foldr (\x next -> if even x then Just x else next) (4:[])
    = foldr (\x next -> if even x then Just x else next) (4:[])
    = if even 4 then Just 4 else foldr (\x next -> if even x then Just x else next) []
    = Just 4

Размер выражений на промежуточных шагах имеет постоянную верхнюю границу - это на самом деле означает, что эта оценка может быть выполнена в постоянном пространстве.

Еще одна причина, по которой foldr в Haskell может работать в постоянном пространстве, состоит из оптимизации слияния списков в GHC. GHC во многих случаях может оптимизировать foldr в цикле постоянного пространства над производителем постоянного пространства. Обычно это невозможно сделать для левой складки.

Тем не менее, левые складки в Haskell могут быть записаны для использования хвостовой рекурсии, что может привести к повышению производительности. Дело в том, что для того, чтобы это на самом деле преуспеть, нужно быть очень осторожным в отношении лениво-наивных попыток написания хвостового рекурсивного алгоритма, обычно приводящего к выполнению линейного пространства из-за накопления неоцененных выражений.

Уроки урожая:

• Когда вы начинаете работу в Haskell, попробуйте как можно больше использовать библиотечные функции от Prelude и Data.List, потому что они были тщательно написаны для использования функций производительности, таких как слияние списков.
• Если вам нужно сбросить список, сначала попробуйте foldr.
• Никогда не используйте foldl, используйте foldl' (версию, которая позволяет избежать неоцененных выражений).
• Если вы хотите использовать хвостовую рекурсию в Haskell, сначала вам нужно понять, как работает оценка, иначе вы можете ухудшить ситуацию.

Ответ 3

(Прочитайте комментарии к этому сообщению. Некоторые интересные моменты были сделаны, и то, что я написал здесь, не совсем верно!)

Это зависит. foldl обычно быстрее, так как он является рекурсивным, что означает (вроде), что все вычисления выполняются на месте, и нет вызова-стека. Для справки:

foldl f a [] = a
foldl f a (x:xs) = foldl f (f a x) xs

Для запуска foldr нам нужен стек вызовов, так как есть "ожидающий" вычисление для f.

foldr f a [] = a
foldr f a (x:xs) = f x (foldr f a xs)

С другой стороны, foldr может замыкаться, если f не является строгим в своем первом аргументе. Это в некотором роде. Например, если мы определим новый продукт

prod 0 x = 0
prod x 0 = 0
prod x y = x*y

Тогда

foldr prod 1 [0...n]

принимает постоянное время в n, но

foldl prod 1 [0...n]

принимает линейное время. (Это не сработает с использованием (*), так как он не проверяет, является ли какой-либо аргумент равным 0. Поэтому мы создаем нестрогую версию. Благодаря Ingo и Daniel Lyons за то, что они указали это в комментариях)