Это может произойти, если вы привыкли к функциональным языкам, на которых распространена факторизация хвостовой рекурсии. Скажем, у вас есть функция:
sum = go 0
where
go accum [] = accum
go accum (x:xs) = go (accum+x) xs
Что, кстати, совпадает с
sum = foldl (+) 0
Если мы оценим функцию, мы увидим проблему:
sum [1,2,3,4]
go 0 [1,2,3,4]
go (0+1) [2,3,4]
go ((0+1)+2) [3,4]
go (((0+1)+2)+3) [4]
go ((((0+1)+2)+3)+4) []
(((0+1)+2)+3)+4
Теперь, чтобы оценить это выражение, Haskell использует стек:
EXPR | STACK
(((0+1)+2)+3)+4 |
((0+1)+2)+3 | +4
(0+1)+2 | +3 +4
(0+1) | +2 +3 +4
1 | +2 +3 +4
3 | +3 +4
6 | +4
10 |
И это , где может произойти переполнение. Если вы оцените сумму [1..10 ^ 6], этот стек будет иметь миллион записей.
Но обратите внимание на патологию здесь. Вы просматриваете список только для создания огромного выражения fscking («thunk»), а затем используете стек для его оценки. Мы предпочли бы оценить его, как мы повторяем, сделав строгую хвостовую рекурсию:
sum = go 0
where
go accum [] = accum
go accum (x:xs) = accum `seq` go (accum+x) xs
Это говорит о том, что нужно оценить накопление, прежде чем пытаться оценить рекурсивный вызов, поэтому мы получаем (это может потребоваться некоторое терпение, чтобы понять):
sum [1,2,3,4]
go 0 [1,2,3,4]
let accum = 0 in accum `seq` go (accum+1) [2,3,4]
go (0+1) [2,3,4]
let accum = 0+1 in accum `seq` go (accum+2) [3,4]
go (1+2) [3,4]
let accum = 1+2 in accum `seq` go (accum+3) [4]
go (3+3) [4]
let accum = 3+3 in accum `seq` go (accum+4) []
go (6+4) []
6+4
10
Итак, когда мы просматриваем список, мы вычисляем сумму, поэтому нам не нужно использовать глубокий стек для оценки результата. Этот измененный шаблон хвостовой рекурсии инкапсулирован в Data.List.foldl ', поэтому:
sum = foldl' (+) 0
Хорошее эмпирическое правило: никогда не используйте : foldl , потому что он всегда создает гигантские громы. Используйте вместо этого foldl '. Если тип вывода имеет ленивую структуру (например, список или функцию), используйте foldr. Но для предотвращения переполнения стека в целом не существует «серебряной пули», вам просто нужно понять поведение вашей программы при оценке. Иногда это может быть трудно.
Но, если я правильно понимаю, переполнение стека всегда происходит из-за попытки оценить гигантский поток. Так что ищите места, где они могут быть созданы, и заставьте оценку произойти раньше.