Haskell - Garbage collection fails to reclaim sufficient space

Question

I'm doing a program to sum all odd numbers up to n:

oddSum' n result | n==0 = result
                 | otherwise = oddSum' (n-1) ((mod n 2)*(n)+result)

oddSum n = oddSum' n 0

I'm getting a two erros for for my inputs (I've put them below), I'm using tail recursion so why is the stack overflow happening? (note: I'm using Hugs on Ubuntu)

oddSum 20000 ERROR - Control stack overflow

oddSum 100000 ERROR - Garbage collection fails to reclaim sufficient space

Answer 1

 oddSum 3
 oddSum 2 ((2 mod 2)*2 + 3)
 oddSum 1 ((1 mod 2)*1 + ((2 mod 2)*2 + 3))

You are building a huge thunk in the result variable. Once you evaluate this, all the computations have to be done at once, and then the stack overflows, because, to perform addition, for example, you first have to evaluate the operands, and the operands of additions in the operands.

If, otoh, the thunk gets too big, you get a heap overflow.

Try using

result `seq` ((mod n 2) * n + result)

in the recursion.

Answer 2

Firstly, don't use Hugs, it's unsupported. With optimising GHC chances are something like this would be compiled to a tight efficient loop (still your code wouldn't be fine).

Nonstrict accumulators always pose the risk of building up huge thunks. One solution would be to make it strict:

{-# LANGUAGE BangPatterns   #-}

oddSum' n !acc | n==0       = acc
               | otherwise  = oddSum' (n-1) $ (n`mod`2)*n + acc

Of course, that's hardly idiomatic; explicitly writing tail-recursive functions is cumbersome and somewhat frowned upon in Haskell. Most things of this kind can nicely be done with library functions, like

oddSum n = sum [1, 3 .. n]

...which unfortunately doesn't work reliably in constant space, either. It does work with the strict version of the fold (which sum is merely a specialisation of),

import Data.List
oddSum n = foldl' (+) 0 [1, 3 .. n]