Ответ 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