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

Question

В 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'?

Answer 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' по причинам, которые вы упомянули.

Answer 2

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