Что вызывает «переполнение стека ошибок C» в haskell обычно

Question

Каковы обычные причины «переполнения стека ошибок C» в реализации Hugs Haskell.

Answer 1

Это может возникнуть, если вы привыкли к функциональным языкам, в которых обычно используется факторизация хвостовой рекурсии. Скажем, у вас есть функция:

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 использует стопку:

И это, где может произойти переполнение. Если вы оценили сумму [1,10^6], этот стек будет составлять миллион записей.

Но обратите внимание на патологию здесь. Вы переписываете список только для создания огромного выражения fscking («thunk»), а затем используйте стек для его оценки. Мы предпочли бы оценить его, как мы рекурсии, сделав хвостовую рекурсию строгое:

sum = go 0 
    where 
    go accum [] = accum 
    go accum (x:xs) = accum `seq` go (accum+x) xs 

Это говорит оценить Accum, прежде чем пытаться оценить рекурсивный вызов, таким образом мы получаем (это может занять некоторое терпение, чтобы понять) :

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

Но, если я правильно понимаю, переполнение стека всегда происходит от попытки оценить гигантский удар. Поэтому ищите места, где они могут быть созданы, и принудительная оценка произойдет раньше.

Answer 2

Беглый рекурсия является наиболее вероятным кандидатом ... Вам нужно дать больше информации, хотя для более точного ответа.

Answer 3

Вот код, который может привести к беглым рекурсии:

main = 
    let x = x :: Int 
    in print x 

Что здесь происходит, что, когда x оценивается в print x она начинается, а затем выясняется, что для завершения своей оценки он должен оценить x.

Answer 4

Наиболее вероятной причиной может быть неконтролируемая рекурсия. Каждый рекурсивный вызов потребляет немного больше пространства стека для параметров ввода/вывода.