Haskell Foldl и переполнение стека?

Question

Я прочитал сообщение о претензиях foldl может произойти переполнение стека легко. И пример кода отправки был:

maximum [1..1000000]

Код не переполнен на моей машине. Однако это может варьироваться в зависимости от окружающей среды. Я увеличил число так:

maximum [1..1000000000]

это вызвало замену жесткого диска, поэтому я должен прекратить оценку. Пример кода не важен. Действительно ли происходит переполнение стека? Или просто старая история?

Answer 1

Некоторые точки

• Рекурсивная функция занимает место в стеке при каждом вызове, поэтому глубоко вложенные вызовы вызовут переполнения
• Хвосто-рекурсивная функция может быть оптимизирована для итераций и поэтомупереполнение
• foldr равно не хвост-рекурсивно
• Ленивая оценка может помешать оптимизации хвост-рекурсивных функций
• foldl - это хвост-рекурсивный и ленивый, поэтому он может переполнить
• foldl' является хвост-рекурсивным и строгим, поэтому он безопасен

Answer 2

Data.List.maximum реализован с использованием ленивых foldl1. Существует правило использования strictMaximum (реализовано с использованием строгого foldl1'), если список содержит Int или Integer.

Итак, следующая программа, скомпилированная с оптимизацией, не вызывает переполнение стека:

main = print $ максимум [1..1000000000]