Почему невозможно переопределить (реализовать) foldr в терминах foldl

Question

У нас есть это foldl can be implemented in terms of foldr. Это подробно объясняется в A tutorial on the universality and expressiveness of fold. В статье говорится, что:

В отличие от этого, не представляется возможным пересмотреть fold с точки зрения foldl, в связи с тем, что foldl является строго в хвосте списка своих аргументов, но fold не является.

Однако я не вижу, как это является доказательством о невозможности определения foldr с точки зрения foldl (заметим, что в оригинальной статье fold является синонимом foldr). Я очень озадачен, пытаясь понять, как здесь играет роль строгость. Может ли кто-нибудь расширить это объяснение?

Answer 1

В дальнейшем я буду ссылаться на fold как foldr (так как это называется в стандартных библиотеках Haskell).

---

другой взгляд на определение foldl,

foldl :: (β -> α -> β) -> β -> [α] -> β 
foldl f v [] = v 
foldl f v (x:xs) = foldl f (f v x) xs 

отмечают, что базовый случай требует список аргументов, чтобы быть [] - во всех остальных случаях список оцениваемых в WNHF и мы рекурсию немедленно используя хвост списка. Это устанавливает тот факт, что foldl является строгим в своем (последнем) аргументе списка.

Теперь мы можем написать версию foldr с помощью foldl, но он будет работать только в списках конечной длины. См. this page для мотивации.

foldr' :: (α -> β -> β) -> β -> [α] -> β 
foldr' f v xs = foldl (\g u x -> g (f u x)) id xs v 

Чтобы увидеть проблему, давайте попробуем написать версию head, тотальный используя правую свертку.

import Control.Applicative ((<|>)) 

safeHead :: [α] -> Maybe α 
safeHead = foldr (\x y -> Just x <|> y) Nothing 

Если заменить foldr с нашим foldl основанного foldr', мы уже не в состоянии найти голова бесконечного списка safeHead [1..]. Даже если safeHead нужно только посмотреть на первый элемент списка, базовый foldl попытается пересечь весь бесконечный список.

---

Такая функция фактически уже существует в Prelude, он называется listToMaybe

Answer 2

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f acc [] = acc 
foldr f acc (x : xs) = f x (foldr f acc xs) 

Обратите внимание, что если список не пуст, то рекурсивный вызов foldr является внутри аргумент передан f. Haskell лениво оценивается, поэтому рекурсивный вызов foldr необязательно фактически вычисляется.Если f может возвращать результат без рассмотрения второго аргумента (но может изучить первый аргумент x, чтобы решить хочет ли он посмотреть на ее второй аргумент), то foldr вызов может «остановить рано», без рассматривая весь список.

foldl :: (b -> a -> b) -> b -> [a] -> b 
foldl f acc [] = acc 
foldl f acc (x : xs) = foldl (f acc x) xs 

Здесь (когда список не пуст) foldl немедленно рекурсивно, с вызовом f внутри аккумулятора аргумента он проходит рекурсивный вызов. f не получает возможности решить, следует ли проверять рекурсивный вызов или нет; foldl находится в полном контроле того, как долго будет продолжаться рекурсия, и он продолжает это делать, пока не найдет конец списка.

Так, в частности, с помощью foldr вы можете обработать бесконечный список; до тех пор, пока функция, которую вы передаете, в конце концов не ссылается на второй аргумент (acc). Например, в GHCi:

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..5] 
"1, 2, 3, 4, 5, STOP" 

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..] 
"1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..." 

С foldr, функция лямбда может использовать этот if заявление изучить элемент списка x и решить, следует ли использовать результаты складывания остальной части списка (которые на которые ссылаются acc, но пока еще не были рассчитаны).

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

Prelude> take 10 $ foldr (\x acc -> x + 100 : acc) [] [1..] 
[101,102,103,104,105,106,107,108,109,110] 

Здесь я только с помощью foldr делать ту же работу, как map, добавляя 100 к каждому элементу бесконечного списка, который производит бесконечный список, в свою очередь, но потом take 10 только грейферы первые 10 из них. Это работает, потому что бесконечные «результаты свертывания результата списка» просто сохраняются во втором поле конструктора списка :.

Эта способность обрабатывать бесконечный список (действительно ли вы возвращаете конечный или бесконечный результат) не может быть смоделирована foldl, потому что функция, которую вы передаете в foldl, не может решить, «сколько» рекурсии использовать; foldl сам повторяет все пути до конца списка, прежде чем он возвращает что-либо другое, кроме другого вызова foldl. Если список бесконечен, он просто никогда не возвращает ничего, кроме другого вызова foldl, независимо от того, какую функцию вы передаете foldl или какую оболочку вы используете, чтобы попытаться сделать это, выполнив задание foldr.

Это не просто обработка бесконечных списков (если это кажется эзотерическим); если все ваши списки конечны, то вы можете использовать foldl, чтобы получить тот же результат, что и foldr, но вы по-прежнему заблокированы для изучения всего списка, что может быть очень неэффективным, если вы на самом деле нуждались в небольшом префиксе.