undefined | Better HN

0 pointsjoeyh14y ago0 comments

quickcheck is running makeChange with an arbitrary Int. maxBound :: Int here is 2147483647. When given a number that large, makeChange recurses a lot, subtracting one two-dollar coin at a time, so you blow the stack. This is where you need to consult a haskell guru to find a way to make your code tail-recursive -- or find a smarter algorithm (using mod c for example so it only needs to recurse 6 times total).

Amusingly, if you simply change the type to Integer -> [Integer], it all works ok. I suspect that since Integers have unbounded size, quickcheck only tests with reasonably small ones.

0 comments

3 comments · 2 top-level

pja14y ago· 1 in thread

It's even worse than that if he's on a 64-bit machine!

It runs just fine on my box with i = 2^32: 10s to completion or thereabouts.

However, the way this is written, the code has to construct the entire list in memory before it can print any of it out so for larger lists it is pretty much guaranteed to blow the stack and / or memory depending on the computational representation.

If it was using a snoclist or something then it could stream the output and perform the calculation in constance space, as it stands it has to hold on to the whole list of integers before outputting any of them.

I'm surprised that the OCaML version 'just worked' frankly: either a) the OP didn't use QuickCheck with their OCaML code or b) the OCaML QuickCheck doesn't bother testing across the whole Int space.

pja14y ago

Also, a quick test reveals that quickCheck on an Int will by default test 100 Ints across the entire range up to Int::maxbound. If your Ints are 64 bit this really isn't going to work very well on this code, regardless of what language you write it in unless you can stream the output. Any code that holds on to the list is going to fall over, since the size of the list is going to exceed physical memory for larger test values.

gnuvince14y ago

The code is already tail recursive, which is why it's doubly puzzling. Also, like you said, using an Integer instead fixes the problem. But I find that fixing these issues distracts me away from the main problem and that doesn't happen in OCaml.

j / k navigate · click thread line to collapse