[Haskell-cafe] Re: MonadFix

[Joost Behrends]

apfelmus <apfelmus <at> quantentunnel.de> writes:

> Huh?  p < intsqrt n  is evaluated just as often as  p*p > n , with 
> changing  n  . Why would that be less expensive? Btw, the code above 
> test for  r==0  first, which means that the following  p*p > n  is 
> tested exactly once for every prime candidate  p .

No. One point in the introduction of DivIter is, that intsqrt dividend is stored
there and only recomputed, when a new factor is found.

And concerning my cycled lists of summands as [2,4] or [2,4,2,4,2,4,2,6,2,6]:

There simply is no function easily yielding primes for your list primes'. 
If we use the sieve of Eratosthenes, we must have the whole list 
of found primes up to a certain point in memory for proceeding 
beyond that certain point. We cannot gain anything by lazy evaluation. 
Not with the sieve of Eratosthenes - and there is no other reliable mechanism.

What is more - if we have a list of primes, possibly up to 1,000,000 - what
shall we do for efficiently yielding divisors beyond 1,000,000 ? We would have
to fall back to x -> x+2.

Thus an easily computable function stepping through all primes can only be
a function, which yields primes plus some more odd numbers. This is, what i
tried. Alternating addition of 2 and 4 to the current divisor can be continued 
beyond any bound. And i am not forced to use any of the longer list of
summands - indeed, which of these lists to choose should be adapted to the
size of the number to decompose.

Concerning the State monad:

Yes, i was wrong here completely. Ryan Ingram gave detailed instructions why.
And Albert Y.C. Lai pointed out, that normal recursion for division works
tail recursive too. It didn't on my computer - perhaps i misconfigured
ghci (where i tried it). Let us close discussion of this point.

Cheers, Joost