I'm relatively new to Haskell and rather inexperienced with programming in general. A function is causing a stack overflow on certain inputs and I'm not sure why.
Function in question:
digitSum :: Integer -> Integer -> Integer
digitSum _ 1 = 1
digitSum base x = (x `mod` base) + digitSum base (x `div`base)
On some inputs (e.g. 10 15, 11 121, 16 19, 3 1234) it works while on others (10 456 for example) it breaks Could someone explain this to me, so that I can avoid it in the future?
Stack overflow in a functional language often means: unbounded recursion. And, indeed, it is what happens here, for a lot of inputs: take for instance digitSum 2 0. It doesn't match the first pattern match, so it goes for the second case, with base=2 and x=0. x `mod` base = 1 and x `div` base = 0. It then makes a recursive call to digitSum 2 0. Then forever.
This is because your base case is wrong: it should be digitSum _ 0 = 0 instead, because if you keep integer dividing x by base, if base is not 1, you'll always end up with 0.
BlackBeans has the right answer, but as an addendum, it's possible to see a stack overflow not only on unbounded recursion, but also on simply too much recursion. Fortunately this is easy to address by writing your functions in a tail-recursive manner. If you do this, your Haskell compiler can run the function in constant stack space.
A common way to accomplish this is by adding an accumulator parameter, and this is often hidden from the user of the function with a local function.
digitSum :: Integer -> Integer -> Integer
digitSum = digitSum' 0
where
digitSum' acc _ 0 = acc
digitSum' acc base x = digitSum (acc + x `mod` base) base (x `div` base)
If you write your functions in a tail-recursive style and have unbounded recursion, do not expect to see a stack overflow, but do expect to see the program simply hang as the recursion is not terminating.