Project Euler 23: Insight in this Package Program

Question

Hi haskell guys. I am currently working on the 23rd issue of Project Euler . Where I am in atm is that my code seems plausible to me - not in the sense of a "good algorithm", but in the sense of "should work", but the stack memory overflows.

I know that my algorithm is not perfect (in particular, I could, of course, avoid calculating such a large intermediate result at each stage of the recursion in my worker function).

Although, while learning Haskell, I would like to understand why this code is not so dull to avoid such errors the next time.

Any insight into why this program is incorrect will be appreciated.

 import qualified Data.List as Set ((\\)) main = print $ sum $ worker abundants [1..28123] -- Limited list of abundant numbers abundants :: [Int] abundants = filter (\x -> (sum (divisors x)) - x > x) [1..28123] -- Given a positive number, returns its divisors unordered. divisors :: Int -> [Int] divisors x | x > 0 = [1..squareRoot x] >>= (\y -> if mod xy == 0 then let d = div xy in if y == d then [y] else [y, d] else []) | otherwise = [] worker :: [Int] -> [Int] -> [Int] worker (a:[]) prev = prev Set.\\ [a + a] worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as))) -- http://www.haskell.org/haskellwiki/Generic_number_type#squareRoot (^!) :: Num a => a -> Int -> a (^!) xn = x^n squareRoot :: Int -> Int squareRoot 0 = 0 squareRoot 1 = 1 squareRoot n = let twopows = iterate (^!2) 2 (lowerRoot, lowerN) = last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows newtonStep x = div (x + div nx) 2 iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot) isRoot r = r^!2 <= n && n < (r+1)^!2 in head $ dropWhile (not . isRoot) iters 

Edit: exact error Stack space overflow: current size 8388608 bytes. . Increasing the stack memory limit via +RTS -K... does not solve the problem.

Edit2: about sqrt thing, I just copied it from the link in the comments. To avoid the need to run Integer in doubles and run into rounding problems, etc.

Answer 1

In the future, it is polite to try to minimize a little on your own. For example, with a small number of games, I was able to find that the following program also has an overflow stack (with an 8 megabyte stack):

 main = print (worker [1..1000] [1..1000]) 

... which really swallows only that function is spinning you. Let's look at the worker :

 worker (a:[]) prev = prev Set.\\ [a + a] worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as))) 

Even at the first reading, this function was marked in red in my mind, because it is tail-recursive. Haskell's tail recursion is generally not as great an idea as it is in other languages; (where you produce at least one constructor before recursing or recurs a number of times before creating the constructor) is generally better for lazy evaluation. And in fact, what happens here is that every recursive call to worker creates a deeper and deeper nested thunk in the prev argument. When the time comes to finally return prev , we need to go very deep into the long chain of calls to Set.\\ to work out what we finally had.

This problem is a bit confused due to the fact that the obvious strictest annotation does not help. Give a massage to the worker until it works. The first observation is that the first sentence is completely subordinate to the second. This is a style; it should not affect behavior (except for empty lists).

 worker [] prev = prev worker (a:as) prev = worker as (prev Set.\\ map (a+) (a:as)) 

Now an obvious annotation of strict severity:

 worker [] prev = prev worker (a:as) prev = prev `seq` worker as (prev Set.\\ map (a+) (a:as)) 

I was surprised to find that this is still a stack overflow! The point is that seq in lists evaluates far enough to find out if the list matches either [] or _:_ . The stack overflow is not performed below:

 import Control.DeepSeq worker [] prev = prev worker (a:as) prev = prev `deepseq` worker as (prev Set.\\ map (a+) (a:as)) 

I have not included the final version back to the source code, but at least working with a minimized main above. By the way, you might like the following implementation idea, which also overflows the stacks:

 import Control.Monad worker as bs = bs Set.\\ liftM2 (+) as as 

but which can be fixed using Data.Set instead of Data.List , and no strictness annotations:

 import Control.Monad import Data.Set as Set worker as bs = toList (fromList bs Set.\\ fromList (liftM2 (+) as as)) 

Answer 2

As Daniel Wagner correctly said , the problem is that

 worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as))) 

builds poorly invested TNCs. You can avoid this and get slightly better performance than using deepseq , using the fact that both arguments in worker are sorted in this application. Thus, you can get incremental output by noting that at any stage everything in prev less than 2*a cannot be the sum of two bountiful numbers, therefore

 worker (a:as) prev = small ++ worker as (large Set.\\ map (+ a) (a:as)) where (small,large) = span (< a+a) prev 

doing better. However, this is still bad because (\\) cannot use the sorting of these two lists. If you replace it with

 minus xxs@ (x:xs) yys@ (y:ys) = case compare xy of LT -> x : minus xs yys EQ -> minus xs ys GT -> minus xxs ys minus xs _ = xs -- originally forgot the case for one empty list 

(or use the data-ordlist package version), calculating the difference of values ​​is O (length) instead of O (length ^ 2).

Answer 3

Ok, I uploaded it and gave it a chance. Daniel Wagner's advice is pretty good, probably better than mine. The problem is really related to the working function, but I was going to suggest using Data.MemoCombinators instead of memoize your function.

Also, your divisors algorithm looks dumb. There is a much better way to do this. This is kind of mathy and will require a lot of TeX, so here is a link to the math.stackexchange page on how to do this. The one I talked about was the accepted answer, although someone else gives a recursive solution, which, I think, will work faster. (This does not require simple factorization.)

https://math.stackexchange.com/questions/22721/is-there-a-formula-to-calculate-the-sum-of-all-proper-divisors-of-a-number