foldl против поведения foldr с бесконечными списками

124

В коде функции myAny в этом вопросе используется foldr. Он прекращает обработку бесконечного списка, когда предикат удовлетворен.

Переписал с помощью foldl:

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

(Обратите внимание, что аргументы пошаговой функции правильно поменяны местами.)

Однако он больше не останавливает обработку бесконечных списков.

Я попытался отследить выполнение функции, как в ответе Apocalisp :

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

Однако функция ведет себя иначе. Как это не так?

titaniumdecoy
источник

Ответы:

231

Чем foldотличаются, кажется, частый источник путаницы, поэтому вот более общий обзор:

Рассмотрите возможность свертывания списка из n значений [x1, x2, x3, x4 ... xn ]с помощью некоторой функции fи начального числа z.

foldl является:

  • Левая ассоциативная :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
  • Хвостовой рекурсивный : он выполняет итерацию по списку, а затем производит значение.
  • Ленивый : ничего не оценивается, пока не потребуется результат.
  • Назад : foldl (flip (:)) []переворачивает список.

foldr является:

  • Правый ассоциативный :f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
  • Рекурсивно в аргумент : каждая итерация применяется fк следующему значению и результату свертывания остальной части списка.
  • Ленивый : ничего не оценивается, пока не потребуется результат.
  • Вперед : foldr (:) []возвращает список без изменений.

Здесь есть немного тонкий момент, который иногда сбивает людей с толку: потому что foldlэто наоборот, каждое приложение fдобавляется к результату вне его; и поскольку он ленив , ничего не оценивается, пока не потребуется результат. Это означает, что для вычисления любой части результата Haskell сначала выполняет итерацию по всему списку, создавая выражение вложенных приложений-функций, а затем оценивает самую внешнюю функцию, оценивая ее аргументы по мере необходимости. Если fвсегда использовать свой первый аргумент, это означает, что Haskell должен пройти весь путь до самого внутреннего термина, а затем работать в обратном направлении, вычисляя каждое приложение f.

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

Фактически, даже если foldlэто технически хвостовая рекурсия, потому что все выражение результата создается до того, как что-либо оценивать, foldlможет вызвать переполнение стека!

С другой стороны, подумайте foldr. Это тоже лениво, но поскольку оно запускается вперед , каждое приложение fдобавляется внутрь результата. Итак, чтобы вычислить результат, Haskell создает приложение с одной функцией, вторым аргументом которого является остаток свернутого списка. Если fвторой аргумент является ленивым - например, конструктор данных - результат будет постепенно ленивым , и каждый шаг свертки будет вычисляться только тогда, когда вычисляется некоторая часть результата, которая в нем нуждается.

Итак, мы можем понять, почему foldrиногда работает с бесконечными списками, foldlа не срабатывает : первый может лениво преобразовать бесконечный список в другую ленивую бесконечную структуру данных, тогда как второй должен проверять весь список, чтобы сгенерировать любую часть результата. С другой стороны, foldrс функцией, которой требуются оба аргумента немедленно, например (+), работает (или, скорее, не работает) во многом так же foldl, как построение огромного выражения перед его вычислением.

Итак, следует отметить два важных момента:

  • foldr может преобразовать одну ленивую рекурсивную структуру данных в другую.
  • В противном случае ленивые свертки будут вылетать из-за переполнения стека в больших или бесконечных списках.

Возможно, вы заметили, что это звучит так, будто я foldrмогу делать все foldl, что может, и даже больше. Это верно! Фактически, foldl почти бесполезна!

Но что, если мы хотим получить неленивый результат, свернув большой (но не бесконечный) список? Для этого нам нужна строгая свертка , которую стандартные библиотеки продуманно предоставляют :

foldl' является:

  • Левая ассоциативная :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
  • Хвостовой рекурсивный : он выполняет итерацию по списку, а затем производит значение.
  • Строгий : каждое приложение-функция оценивается в процессе.
  • Назад : foldl' (flip (:)) []переворачивает список.

Поскольку foldl'это строго , для вычисления результата Haskell будет оценивать результат f на каждом шаге, вместо того, чтобы позволять левому аргументу накапливать огромное неоцененное выражение. Это дает нам обычную эффективную хвостовую рекурсию, которую мы хотим! Другими словами:

  • foldl' может эффективно складывать большие списки.
  • foldl' будет зависать в бесконечном цикле (не вызывая переполнения стека) в бесконечном списке.

В вики Haskell есть страница, на которой это обсуждается .

CA McCann
источник
6
Я пришел сюда, потому что мне любопытно, почему foldrэто лучше, чем foldlв Haskell , в то время как в Erlang (что я изучил до Haskell ) все наоборот . Так как Эрланг не ленивый и функция не кэррите , так что foldlв Эрланге ведет себя как foldl'выше. Это отличный ответ! Отличная работа и спасибо!
Сиу Чинг Понг - Асука Кенджи -
7
В основном это отличное объяснение, но я считаю, что описание foldlкак «назад» и foldr«вперед» проблематично. Отчасти это связано с тем, что flipон применяется (:)на иллюстрации того, почему складывание происходит в обратном направлении. Естественная реакция: «Конечно, все наоборот: вы делаете flipконкатенацию списков!» Также странно видеть, что это называется «обратным», поскольку foldlприменяется fк первому (самому внутреннему) элементу списка при полной оценке. Это то, foldrчто «бежит в обратном направлении», fсначала применяя последний элемент.
Дэйв Абрахамс
1
@DaveAbrahams: Между просто foldlи foldrигнорированием строгости и оптимизаций, во-первых, означает «самый внешний», а не «самый внутренний». Вот почему foldrможет обрабатывать бесконечные списки, а foldlне может - правая свертка сначала применяется fк первому элементу списка и (неоцененному) результату сворачивания хвоста, в то время как левая свертка должна проходить через весь список для оценки самого внешнего приложения f.
CA McCann
1
Мне просто интересно, есть ли какой-нибудь пример, в котором будет предпочтительнее foldl, чем foldl ', как вы думаете, есть ли такой?
kazuoua
1
@kazuoua, где лень необходима, например last xs = foldl (\a z-> z) undefined xs.
Уилл Несс,
28
myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

и т.п.

Интуитивно foldlон всегда находится «снаружи» или «слева», поэтому сначала расширяется. До бесконечности.

Artelius
источник
10

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

Ромен
источник
0

Я не знаю Haskell, но в Scheme fold-rightвсегда сначала «действует» на последний элемент списка. Таким образом, это не будет работать для циклического списка (который аналогичен бесконечному).

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

leppie
источник
3
В Haskell все по-другому из-за лени.
Лифу Хуанг,