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 

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

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

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

foldl :

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

foldr :

  • Правый ассоциативный : f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
  • Рекурсивный аргумент : каждая итерация применяет f к следующему значению и к результату складывания остальной части списка.
  • Lazy : ничто не оценивается до тех пор, пока результат не понадобится
  • Форварды : foldr (:) [] возвращает список без изменений.

Здесь есть немного тонкая точка, которая иногда foldl людей: поскольку 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 (fz x1) x2) x3) x4) ...) xn
  • Хвост рекурсивный : он выполняет итерацию по списку, производя значение впоследствии
  • Строго : каждое приложение функции оценивается по пути
  • Назад : 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 всегда находится «снаружи» или «слева», поэтому он сначала расширяется. Ad infinitum.

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

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

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

Interesting Posts

Командная строка с несколькими вкладками в Windows?

Невозможно прочитать последнюю небуферизованную строку

Как использовать std :: find / std :: find_if с вектором объектов пользовательского classа?

DIRCA_CHECKFX Возвращаемое значение 3 – Проект развертывания VS 2013

Передача аргумента unicode командной строки в код Java

Regex найти целые слова

Любые рекомендации для CSS-маркера?

Есть ли firefox-подобный плагин-контейнер для хром?

Невозможно использовать Intellij с созданной исходной папкой

Как отключить дескриптор перетаскивания на рабочем столе?

Почему начало раздела в секторе 2048 вместо 63

Прочитать файлы реестра в каталоге «config» Windows из резервной копии?

Почему имена обновления data.table (DT) по ссылке, даже если я назначаю другую переменную?

Как отключить сенсорную панель нетбука при подключении мыши USB

Не удалось подключиться к FTP-сайтам даже при отключенном брандмауэре Windows

Давайте будем гением компьютера.