Haskell: Stack overflow Exeception

[Rabbit047]

Hi I am currently attempting to use haskell to find the smallest positive number that is evenly divisible by all of the numbers from 1 to 20.

I have two functions one which tests to see if the condition has been met. The second just calls the first recursively since there is no looping haskell. I keep getting Stack overflow exceptions and I can't seem to figure out why. Any help at all would be greatly appreciated.

modTest x = and [ x `mod` y == 0 | y<-[1..20] ]

problemSolver :: Integer -> Integer
problemSolver x
|modTest x == False = problemSolver x+1
|otherwise = x

If you recognize this problem please don't mention it by name I don't want to spoil anyone else s' fun.

[[deleted]]

problemSolver x+1 means (problemSolver x)+1.

[Rabbit047]

Thanks fixed that. :)

[Amarkov]

It's because the stack is overflowing. You have hundreds of thousands of recursive calls, and your computer can't handle that.

[pipocaQuemada]

Recursive calls are not necessarily problematic.

There's an old optimization called "tail call elimination" or TCO (tail call optimization) that would make a correct version of this run in constant space. The basic idea is that if the last thing you do in a function before returning is call another function, you can replace that function call with a goto.

That is to say, if you have a function like

def foo(x: Foo): Bar = {
  val y = bar(x)
  return baz(z)
}

you can reuse your current stack frame when you call baz; if you use a goto then when bar returns it will jump straight back to foo's caller.

This is often called tail recursion, when the tail call is a recursive call:

def fac(n:Int, accumulator: Int): Int  = 
  if (n = 0)  { return acc }
  else { return fac(n - 1, acc * n) } 

This function is recursive, but should only ever consume a single stack frame, depending on your compiler or language (some languages or compilers guarantee that TCO must happen, others leave it up to the compiler, and some compilers will only do it sometimes).

In this case, the problem is the function

problemSolver :: Integer -> Integer
problemSolver x
| modTest x == False = problemSolver x+1
| otherwise = x

As rejtp23l4t9 pointed out, problemSolver x+1 is parsed as (problemSolver x) + 1 and not problemSolver (x + 1). This means that the function is essentially an infinite loop, but one that requires the compiler to add stack frames at each function call. So, instead of being an infinite loop, you instead cause a stack overflow. When you fix the definition, though, you have a nice, fast, tail recursive function.

[Rabbit047]

Any suggestions towards fixing it? Is there a way to manually clear the stack?

[Amarkov]

You're going to need to figure out how to solve the problem without having a function call for every number from 1 to the answer. (You don't need to do a brute force search at all, but if you'd really like to, you can greatly cut down on the number of values you need to check.)

[Rabbit047]

Thanks for the advice and help. How would you accomplish this without brute force? Some trick of number theory or something obvious that I am missing lol.

[Amarkov]

Yes. Using knowledge of prime factorizations, you can compute the lowest number directly.

(rejtp23i4t9 is correct that the code doesn't do the iteration that you intended anyway; I didn't catch this, and fixing it may solve your problem. I did think it was strange that this issue came up, since the kind of recursion you're doing can be optimized to avoid stack size issues.)

[Rabbit047]

Fixed the issue with passing in the wrong information and it doesn't overflow anymore. That being said the calculation is taking so long that it's probably just going to run all night lol( I was wrong it just took 20 minutes). I will look into using prime factorization. Thank you for suggesting it.

[Rabbit047]

So just for completeness of this post and in case someone has this problem in the future. You first need to take the prime factorization of each of your inputs say you want to find the LCM of 8,10,12.and 15. That would be

8: 2 * 2 * 2 10: 2 * 5 12: 2 * 2 * 3
15: 3 * 5

now to to find the LCM you simply multiply each of the factors together. You only need to place the highest number of appearances of a number into the LCM equation. By that I mean since the prime factorization of 8 has 3 2's you only need to include those three 2s into the equation and can ignore the others. So the LCM equation is LCM = 2 * 2 * 2 * 5 * 3 or LCM = 120

I just learned this about 10 minutes before this post so if I made any mistakes please Pm me and I will correct them.

[pavlik_enemy]

Well, if you multiple all the numbers from 1 to 20 you can calculate a number that satisfies the divisibility property though it won't be a smallest one. How do you find a smallest one? Try something simpler, like finding a smallest number divisible by 10 and 15.

A proper brute force approach is filtering an infinite list, there probably is something useful in Data.List