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

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


lazy-evaluation fold combinators haskell
person titaniumdecoy    schedule 21.06.2010    source источник

Ответы (4)


arrow_upward
245
arrow_downward

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

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

foldl is:

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

foldr is:

  • Правоассоциативный: 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' is:

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

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

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

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

person C. A. McCann    schedule 21.06.2010
comment
Я пришел сюда, потому что мне любопытно, почему foldr лучше, чем foldl в Haskell, в то время как обратное верно в Erlang (который я узнал до Haskell ). Поскольку Erlang не ленив, а функции не каррированы, foldl в Erlang ведет себя так же, как foldl' выше. Это отличный ответ! Отличная работа и спасибо! - person Siu Ching Pong -Asuka Kenji-; 02.03.2014
comment
В основном это отличное объяснение, но я считаю, что описание foldl как обратное и foldr как прямое проблематичное. Частично это связано с тем, что flip применяется к (:) на иллюстрации того, почему складка происходит в обратном направлении. Естественная реакция, конечно, обратная: вы flipподключили конкатенацию списков! Также странно видеть, что это вызвано в обратном порядке, поскольку foldl применяет f к первому элементу списка первым (самым внутренним) в полной оценке. Это foldr, который выполняется в обратном направлении, применяя f к последнему элементу первым. - person Dave Abrahams; 02.11.2014
comment
@DaveAbrahams: Между foldl и foldr и игнорированием строгости и оптимизации, в первую очередь, означает самое внешнее, а не самое внутреннее. Вот почему foldr может обрабатывать бесконечные списки, а foldl нет - правая свертка сначала применяет f к первому элементу списка и (неоцененному) результату сворачивания хвоста, в то время как левая свертка должна пройти весь список, чтобы оценить самый внешний применение f. - person C. A. McCann; 10.11.2014
comment
Мне просто интересно, есть ли какой-нибудь пример, в котором будет предпочтительнее foldl, чем foldl ', как вы думаете, есть ли такой? - person kazuoua; 30.12.2015
comment
@kazuoua, где лень необходима, например last xs = foldl (\a z-> z) undefined xs. - person Will Ness; 13.08.2016
comment
Отличный ответ, но я думаю, что более ясно представить левую ассоциативную функцию foldl как f (foldl f [] [x1, x2,... xn-1]) xn и левую ассоциативную функцию foldr как f x1 (foldr f [] [x2, x3, ... xn]). В этом представлении ясно, что foldr может работать с бесконечным списком. - person Dagang; 11.01.2017
comment
Спасибо за это объяснение - мне было трудно понять, почему foldr работал лучше с бесконечными списками (если foldr вычисляет справа, как это работает с бесконечными списками, у которых нет определенной правой части?), Но этот ответ хорошо это объясняет :) - person nyctef; 13.01.2017
comment
@ SiuChingPong-AsukaKenji: мне было интересно, является ли лень единственной причиной такого поведения Haskell, и вы точно ответили на это. - person dhu; 23.02.2018
comment
Понятия start и end или first и last были бы лучшей терминологией для текущих left и right или даже top и bottom, поскольку эти понятия относятся к концу списка новых элементов append. - person George; 14.03.2021

arrow_upward
28
arrow_downward 

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 всегда находится «снаружи» или «слева», поэтому оно раскрывается первым. До бесконечности.

person Artelius    schedule 21.06.2010

arrow_upward
10
arrow_downward

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

person Romain    schedule 21.06.2010

arrow_upward
0
arrow_downward

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

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

person leppie    schedule 21.06.2010
comment
В Haskell все по-другому из-за лени. - person Lifu Huang; 14.08.2017