<br><br><div><span class="gmail_quote">On 2/10/07, <b class="gmail_sendername"><a href="mailto:apfelmus@quantentunnel.de">apfelmus@quantentunnel.de</a></b> <<a href="mailto:apfelmus@quantentunnel.de">apfelmus@quantentunnel.de
</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Creighton Hogg wrote:<br>> Hello Haskell-ers,<br>> So a friend and I were thinking about making code faster in Haskell, and I
<br>> was wondering if there was a way to improve the following method of<br>> generating the list of all prime numbers. It takes about 13 seconds to<br>> run, meanwhile my friend's C version took 0.1.<br>> I'd love to learn a bit more about how to optimize Haskell code.
<br><br>Of course, the best optimization is a better algorithm. In case this is<br>what you're after, have a look at<br><br> Colin Runciman, Lazy Wheel Sieves and Spirals of Primes<br> <a href="http://citeseer.ist.psu.edu/runciman97lazy.html">
http://citeseer.ist.psu.edu/runciman97lazy.html</a></blockquote><div><br><snip helpfullness> <br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
The glitches may have been unintentional, but the flaw intentionally<br>degrades performance: you should not use a strict all' but the lazy<br><br> all prop = foldr (\y z -> prop y && z) True<br><br>from the Prelude. The point is that the lazy version stops inspecting
<br>the elements of the remaining list whenever (prop y) turns False for the<br>first time. This is because && is lazy:<br><br> False && x = False<br><br>for whatever x we supply. For example, take the list
<br><br> [True, False, True, True] ++ replicate 100 True<br><br>Here, all returns False after inspecting the first two elements while<br>all' inspects every one of the 104 list elements just to return False<br>afterwards. As every second number is even, your all' is busy wasting
<br>time like crazy.</blockquote><div><br>Okay, this is sinking in a good bit better, thank you. I think I've had a conceptual block about what laziness really means.<br><br><br><br><br></div><br></div>