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:
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Однако это не способ, которым ведет себя функция. Как эта несправедливость?
4 ответа
То, как свертки различаются, кажется частым источником путаницы, поэтому вот более общий обзор:
Рассмотрим свертывание списка из n значений [x1, x2, x3, x4 ... xn] с помощью некоторой функции f и начального числа z .
foldl :
- Левая ассоциативная :
f (... (f (f (f (f (fz 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 - Хвостовая рекурсия : выполняет итерацию по списку, после чего выдает значение
- Strict :Каждое приложение-функция оценивается по пути
- Назад :
foldl '(flip (:)) []переворачивает список.
Поскольку foldl ' является строгим , для вычисления результата Haskell будет вычислить f на каждом шаге, вместо того, чтобы позволять левому аргументу накапливать огромное, неоцененное выражение. Это дает нам обычную эффективную хвостовую рекурсию, которую мы хотим! Другими словами:
foldl 'может эффективно сворачивать большие списки.foldl 'будет зависать в бесконечном цикле (не вызывая переполнения стека) в бесконечном списке.
В вики Haskell есть страница, обсуждающая это .
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 всегда находится «снаружи» или «слева», поэтому сначала расширяется. До бесконечности.
Я не знаю Haskell, но в Scheme fold-right всегда будет сначала «действовать» на последнем элементе списка. Таким образом, это не будет работать для циклического списка (который аналогичен бесконечному).
Я не уверен, что fold-right можно записать хвостовой рекурсией, но для любого циклического списка вы должны получить переполнение стека. fold-left OTOH обычно реализуется с хвостовой рекурсией и просто застревает в бесконечном цикле, если его не завершить раньше.
Вы можете увидеть в документации Haskell здесь , что foldl является хвостовой рекурсией и никогда не завершится, если передан бесконечный список, поскольку он вызывает себя для следующего параметра перед возвратом значение ...