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

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

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

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

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

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

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

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

Однако это не так, как работает функция. Как это неправильно?

Ответ 1

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

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

`foldl`:

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

`foldr`:

Правильный ассоциативный: f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
Рекурсивно в аргумент. Каждая итерация применяет f к следующему значению и результат складывания остальной части списка.
Lazy: ничто не оценивается до тех пор, пока результат не понадобится
Вперед: 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 wiki имеет страницу, обсуждающую этот вопрос.

Ответ 2

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 всегда находится на "снаружи" или "слева", поэтому он сначала расширяется. Ad infinitum.

Ответ 3

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

Ответ 4

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

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