<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div>Wow, nice catch!<br></div><div><br>On Nov 27, 2015, at 9:21 PM, Justin Holmgren <<a href="mailto:holmgren@mit.edu">holmgren@mit.edu</a>> wrote:<br><br></div><blockquote type="cite"><div><div dir="ltr">Function application has higher precedence than exponentiation</div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Nov 27, 2015 at 9:04 PM, Romain Gehrig <span dir="ltr"><<a href="mailto:romain.gehrig@gmail.com" target="_blank">romain.gehrig@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi,<div><br></div><div>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.</div><div><br></div><div>The said function:</div><div><pre style="color:rgb(0,0,0)">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)</pre></div><div><br></div><div>You can try in GHCi (apparently with an upper limit of 10^199669):</div><div><pre style="color:rgb(0,0,0)">GHCi> collatzSteps 10^199668
[big num...]
GHCi> length $ show $ collatzSteps 10^199668
168740
GHCi> collatzSteps 10^199669 -- Oops
[1] 36128 bus error ghci</pre></div><div><br></div><div>Notice the number 168740: it is the number of <b>digits</b> for the number of steps. It implies that the `acc` is ~= <b>10^168740</b> 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.</div><div><br></div><div>Can someone shed some light on how this peculiar function was optimised by GHC?</div><div><br></div><div>Many thanks,</div><div>(still dazed) Romain</div></div>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>
</div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>Haskell-Cafe mailing list</span><br><span><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a></span><br><span><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a></span><br></div></blockquote></body></html>