Function application has higher precedence than exponentiation
On Fri, Nov 27, 2015 at 9:04 PM, Romain Gehrig
Hi,
I implemented a function to count how many steps it takes for a number to be reduced to 1 using the Collatz Conjecture (also known as the 3n + 1 problem) and I was very surprised to see it working instantaneously for integers as big as 10^100000.
The said function:
collatzSteps :: Integer -> Integer collatzSteps n = steps 1 n where steps acc 1 = acc steps acc n' | even n' = steps (acc+1) (n' `div` 2) steps acc n' = steps (acc+1) (n' * 3 + 1)
You can try in GHCi (apparently with an upper limit of 10^199669):
GHCi> collatzSteps 10^199668 [big num...] GHCi> length $ show $ collatzSteps 10^199668 168740 GHCi> collatzSteps 10^199669 -- Oops [1] 36128 bus error ghci
Notice the number 168740: it is the number of *digits* for the number of steps. It implies that the `acc` is ~= *10^168740* when the function ends. Without optimisation at some point, it would mean there were as much (acc+1) calls ! My understanding completely stops there; I can't comprehend why a function that shouldn't return anything even long after the end of the universe just finished before my eyes.
Can someone shed some light on how this peculiar function was optimised by GHC?
Many thanks, (still dazed) Romain
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe