<div dir="ltr">I think the code sample should be replaced with a number of different code samples, demonstrating different things. Then we don't have to try to fit all the syntax into one bit of code, and so we can avoid using a fake sieve entirely. See the way Racket does their code demos:<div><br></div><div><a href="http://racket-lang.org/">http://racket-lang.org/</a><br></div><div><br></div><div>I also posted this for discussion on the Github issue:</div><div><br></div><div><a href="https://github.com/haskell-infra/hl/issues/46">https://github.com/haskell-infra/hl/issues/46</a><br></div><div><br></div><div>-- Andrew</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 21, 2015 at 11:32 AM, Ertugrul Söylemez <span dir="ltr"><<a href="mailto:ertesx@gmx.de" target="_blank">ertesx@gmx.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">> Leave the example. But change the blurb to say:<br>
> This is inspired by the Sieve of Eratosthenes. For a true Sieve of<br>
> Eratosthenes, see [link to O'Neil].<br>
<br>
</span>Unfortunately trial division is in no way inspired by the SoE.  It's<br>
about the most bruteforcy way to find primes.  Basically all it does is<br>
to perform a full primality test for every single candidate.  The only<br>
advantage of the example code is that it uses laziness and sharing to<br>
keep a list of the primes found so far to make this trial division<br>
slightly less expensive.<br>
<br>
In fact it can be improved quadratically and still wouldn't be a sieve.<br>
On my current machine in 1 second the following code finds the first<br>
60000 primes while the homepage example finds only 3700 primes, both<br>
specialised to [Int]:<br>
<br>
    primes = 2 : filter isPrime [3..]<br>
        where<br>
        isPrime x =<br>
            all (\p -> mod x p /= 0) .<br>
            takeWhile (\p -> p*p <= x) $ primes<br>
<br>
The SoE on the other hand exploits the global structure of the<br>
distribution of a prime's multiples.  Without any division at all it<br>
simply deduces that after each crossing operation the smallest remaining<br>
integer *must* be prime.<br>
<br>
This is pretty much the same improvement the quadratic sieve makes to<br>
Dixon's factoring method and the number field sieve makes to the index<br>
calculus method.  It gets rid of primality tests and uses the<br>
distributions of multiples.  Thus it finds lots and lots of relations in<br>
one go rather than testing every single relation.  It would be equally<br>
wrong to call Dixon's method or index calculus sieves.<br>
<br>
How about simply changing `sieve` to `trialDiv`?  It's not that I don't<br>
like the given example, because it gives a very small use case for<br>
laziness that is difficult enough to reproduce in an eagerly evaluated<br>
language.  And with the new name for the local function it stops turning<br>
the stomach of a number theoretician.<br>
<br>
<br>
Greets,<br>
Ertugrul<br>
<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" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>