Чем 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 есть страница, на которой это обсуждается .
foldr
это лучше, чемfoldl
в Haskell , в то время как в Erlang (что я изучил до Haskell ) все наоборот . Так как Эрланг не ленивый и функция не кэррите , так чтоfoldl
в Эрланге ведет себя какfoldl'
выше. Это отличный ответ! Отличная работа и спасибо!foldl
как «назад» иfoldr
«вперед» проблематично. Отчасти это связано с тем, чтоflip
он применяется(:)
на иллюстрации того, почему складывание происходит в обратном направлении. Естественная реакция: «Конечно, все наоборот: вы делаетеflip
конкатенацию списков!» Также странно видеть, что это называется «обратным», посколькуfoldl
применяетсяf
к первому (самому внутреннему) элементу списка при полной оценке. Это то,foldr
что «бежит в обратном направлении»,f
сначала применяя последний элемент.foldl
иfoldr
игнорированием строгости и оптимизаций, во-первых, означает «самый внешний», а не «самый внутренний». Вот почемуfoldr
может обрабатывать бесконечные списки, аfoldl
не может - правая свертка сначала применяетсяf
к первому элементу списка и (неоцененному) результату сворачивания хвоста, в то время как левая свертка должна проходить через весь список для оценки самого внешнего приложенияf
.last xs = foldl (\a z-> z) undefined xs
.и т.п.
Интуитивно
foldl
он всегда находится «снаружи» или «слева», поэтому сначала расширяется. До бесконечности.источник
Вы можете увидеть в документации Haskell здесь, что foldl является хвостовой рекурсией и никогда не завершится, если передан бесконечный список, поскольку он вызывает себя для следующего параметра перед возвратом значения ...
источник
Я не знаю Haskell, но в Scheme
fold-right
всегда сначала «действует» на последний элемент списка. Таким образом, это не будет работать для циклического списка (который аналогичен бесконечному).Я не уверен,
fold-right
можно ли написать хвостовую рекурсию, но для любого циклического списка вы должны получить переполнение стека.fold-left
OTOH обычно реализуется с хвостовой рекурсией и просто застревает в бесконечном цикле, если его не завершить раньше.источник