[Haskell-cafe] haskell.org

[Andrew Gibiansky]

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:

http://racket-lang.org/

I also posted this for discussion on the Github issue:

https://github.com/haskell-infra/hl/issues/46

-- Andrew

On Tue, Apr 21, 2015 at 11:32 AM, Ertugrul Söylemez <ertesx at gmx.de> wrote:

> > Leave the example. But change the blurb to say:
> > This is inspired by the Sieve of Eratosthenes. For a true Sieve of
> > Eratosthenes, see [link to O'Neil].
>
> Unfortunately trial division is in no way inspired by the SoE.  It's
> about the most bruteforcy way to find primes.  Basically all it does is
> to perform a full primality test for every single candidate.  The only
> advantage of the example code is that it uses laziness and sharing to
> keep a list of the primes found so far to make this trial division
> slightly less expensive.
>
> In fact it can be improved quadratically and still wouldn't be a sieve.
> On my current machine in 1 second the following code finds the first
> 60000 primes while the homepage example finds only 3700 primes, both
> specialised to [Int]:
>
>     primes = 2 : filter isPrime [3..]
>         where
>         isPrime x =
>             all (\p -> mod x p /= 0) .
>             takeWhile (\p -> p*p <= x) $ primes
>
> The SoE on the other hand exploits the global structure of the
> distribution of a prime's multiples.  Without any division at all it
> simply deduces that after each crossing operation the smallest remaining
> integer *must* be prime.
>
> This is pretty much the same improvement the quadratic sieve makes to
> Dixon's factoring method and the number field sieve makes to the index
> calculus method.  It gets rid of primality tests and uses the
> distributions of multiples.  Thus it finds lots and lots of relations in
> one go rather than testing every single relation.  It would be equally
> wrong to call Dixon's method or index calculus sieves.
>
> How about simply changing `sieve` to `trialDiv`?  It's not that I don't
> like the given example, because it gives a very small use case for
> laziness that is difficult enough to reproduce in an eagerly evaluated
> language.  And with the new name for the local function it stops turning
> the stomach of a number theoretician.
>
>
> Greets,
> Ertugrul
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150421/728e14f4/attachment.html>