[Haskell-cafe] Re: Optimization fun

[Creighton Hogg]

On 2/10/07, apfelmus at quantentunnel.de <apfelmus at quantentunnel.de> wrote:
>
> Creighton Hogg wrote:
> > Hello Haskell-ers,
> > So a friend and I were thinking about making code faster in Haskell, and
> I
> > was wondering if there was a way to improve the following method of
> > generating the list of all prime numbers.  It takes about 13 seconds to
> > run, meanwhile my friend's C version took 0.1.
> > I'd love to learn a bit more about how to optimize Haskell code.
>
> Of course, the best optimization is a better algorithm. In case this is
> what you're after, have a look at
>
>    Colin Runciman, Lazy Wheel Sieves and Spirals of Primes
>    http://citeseer.ist.psu.edu/runciman97lazy.html


<snip helpfullness>

The glitches may have been unintentional, but the flaw intentionally
> degrades performance: you should not use a strict all' but the lazy
>
>   all prop = foldr (\y z -> prop y && z) True
>
> from the Prelude. The point is that the lazy version stops inspecting
> the elements of the remaining list whenever (prop y) turns False for the
> first time. This is because && is lazy:
>
>   False && x = False
>
> for whatever x we supply. For example, take the list
>
>   [True, False, True, True] ++ replicate 100 True
>
> Here, all returns False after inspecting the first two elements while
> all' inspects every one of the 104 list elements just to return False
> afterwards. As every second number is even, your all' is busy wasting
> time like crazy.


Okay, this is sinking in a good bit better, thank you.  I think I've had a
conceptual block about what laziness really means.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070210/49e526b7/attachment.htm