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

Question

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

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

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

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

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

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

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

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

Рассмотрим складную список 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 Wiki имеет Страница обсуждает это, также.

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

Answer 3

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

Answer 4

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

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