Поведение сложения против складывания с бесконечными списками

Код для функции 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

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

Источник

4 ответа

Решение

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

Рассмотрим сворачивание списка из 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 также есть страница, где это обсуждается.

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

Источник

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

Источник

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

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

Источник
Другие вопросы по тегам