[Haskell-cafe] haskell.org

[Curtis Gagliardi]

Nobody wants to see a number theory example anyway.  I agree with Andrew
that racket's system with multiple demos is nice, but also think each demo
is much more interesting because they're problems you're more likely to run
into day to day.

On Tue, Apr 21, 2015 at 6:42 PM, Andrew Gibiansky <
andrew.gibiansky at gmail.com> wrote:

> 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
>>
>>
>
> _______________________________________________
> 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/81f14a57/attachment.html>