поведение FoldL против Foldr с бесконечными списками

Question

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

Я переписал его, используя foldl:

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

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

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

Я попытался отследить выполнение функции, как в Ответ 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

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

Answer 1

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

Рассмотрите возможность сворачивания списка из n значений [x1, x2, x3, x4 ... xn ] с некоторой функцией f и seed 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 добавляется к вне результата; и поскольку он lazy , ничего не оценивается, пока не потребуется результат. Это означает, что для вычисления любой части результата Haskell сначала выполняет итерацию по всему списку 1065 *, создающему выражение для приложений с вложенными функциями, а затем оценивает функцию externalmost , оценивая ее аргументы по мере необходимости. Если f всегда использует свой первый аргумент, это означает, что Haskell должен пройти весь путь до самого внутреннего термина, а затем работать в обратном направлении, вычисляя каждое приложение f.

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

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

С другой стороны, рассмотрим foldr. Это также лениво, но поскольку он запускает forward , каждое приложение f добавляется к внутри результата. Таким образом, чтобы вычислить результат, Haskell создает приложение функции single , вторым аргументом которого является оставшаяся часть сложенного списка. Если 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 есть страница, на которой обсуждается также .

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

Answer 3

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

Answer 4

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

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