Justin Bailey:
I am trying to determine why my stack overflows in my medium sized program [...snip...]
prefixesAtLeast :: Int -> [S.ByteString] -> Int prefixesAtLeast !0 !ss | null ss = 0 | all S.null ss = 0 | otherwise = -1 prefixesAtLeast !n !ss = prefixesAtLeast' n ss where prefixesAtLeast' !n ss | n < 0 = -1 | null ss = n | otherwise = let (!s : (!rest)) = ss in prefixesAtLeast' (n - (S.length s)) rest
Stack overflows often occur when you evaluate a "thunk" (unevaluated computation) which you have previously allowed to become deeply nested. The usual example is something like: print $ foldl (+) 0 [1..1000000] => print $ foldl (+) (0+1) [2..1000000] => print $ foldl (+) ((0+1)+2) [3..1000000] => print $ foldl (+) (((0+1)+2)+3) [4..1000000] => ... => print (...(((0+1)+2)+3)+...+1000000) => stack overflow The key point of the example is that foldl itself doesn't need any of the intermediate values of the accumulator, so these just build up into a deeply-nested unevaluated thunk. When print finally demands an integer, the run-time pushes a stack frame for each level of parentheses it enters as it tries to evaluate the thunk. Too many parentheses leads to a stack overflow. Of course, the solution to the example is to use foldl', whose implementation uses strictness annotations to force evaluation of the accumulator at each iteration. In your function, all the thunks you create will be evaluated in the next recursive call, so it's unlikely that prefixesAtLeast is *in itself* causing a stack overflow. However, it's possible that your use of this function is forcing evaluation of a deeply-nested thunk you've created somewhere else (as print does in the foldl example). So if your initial indications are that the stack overflow is occurring somewhere during the evaluation of prefixesAtLeast, you might want to try following the food-chain back through its suppliers (parameters) until you find something like the foldl example. By they way, your sprinkling of strictness annotations (a sure sign of stack-overflow desperation!) should not be necessary. Everything you have annotated should be forced anyway, either immediately or within one recursive call. In particular, !0 is entirely unnecessary, since matching against 0 does just as good a job of forcing the parameter value as the strictness annotation.