Является ли foldl когда-либо предпочтительным для его строгой кузены, foldl '?

Haskell имеет две функции левой складки для списков: foldl и "строгая" версия, foldl'. Проблема с нестрогим foldl заключается в том, что он строит башню громкости:

    foldl (+) 0 [1..5]
--> ((((0 + 1) + 2) + 3) + 4) + 5
--> 15

Это отнимает память и может вызвать переполнение стека, если в списке слишком много элементов. foldl', с другой стороны, заставляет аккумулятор на каждом элементе.

Однако, насколько я могу судить, foldl' семантически эквивалентен foldl. Оценка foldl (+) 0 [1..5], чтобы гладить нормальную форму, требует принудительного включения аккумулятора в какой-то момент. Если бы нам не нужна форма головы, мы не будем оценивать foldl (+) 0 [1..5] для начала.

Есть ли какая-то веская причина, по которой поведение foldl было бы по сравнению с foldl'?

Ответ 1

foldl и foldl' не являются семантически эквивалентными. Тривиальный контрпример:

Prelude Data.List> foldl (\x y -> y) 0 [undefined, 1]
1
Prelude Data.List> foldl' (\x y -> y) 0 [undefined, 1]
*** Exception: Prelude.undefined

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

Ответ 2

Если foldl и foldl' не приведут к такому же результату, как в примере с хаммаром, решение должно быть принято в соответствии с желаемым результатом. Кроме того, вы должны использовать foldl, а не foldl', если сложенная функция является конструктором (применение конструктора создает значение в WHNF, нет смысла переназначать его в WHNF) и в foldl (.) id functions где Усиление WHNF тоже ничего не принесет. Помимо этих исключительных случаев, foldl' - метод выбора.