[Haskell-cafe] Re: MonadFix
Joost Behrends
joost at h-labahn.de
Tue Dec 18 17:32:34 EST 2007
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
>
> Am Dienstag, 18. Dezember 2007 17:26 schrieb Joost Behrends:
> > Hi,
> >
> > since about three weeks i am learning Haskell now. One of my first
> > excercises is to decompose an Integer into its primefactors. I already
> > posted discussion on the solution to the problem 35 in "99 excercises".
> >
> > My simple algorithm uses a datatype DivIter of 4 named fields together with
> > the core iteration
>
> But a simple recursion that returns the list of primefactors lazily would also
> solve the stack frame problem, wouldn't it?
> sort of
> factor 0 = error "0 has no factorisation"
> factor 1 = []
> factor n
> | n < 0 = (-1):factor (-n)
> | even n = 2:factor (n `div` 2)
> | otherwise = oddFactors 3 n
>
> oddFactors k n
> | k*k > n = [n]
> | r == 0 = k:oddFactors k q
> | otherwise = oddFactors (k+2) n
> where
> (q,r) = n `divMod` k
>
> you can then start consuming the prime factors as they come, before the
> factorisation is complete.
> >
Hi and thanks for your answers,
@Daniel: no, this doesn't solve the stack problem. These are the primefactors of
2^120+1: [97,257,673,394783681,4278255361,46908728641].
oddFactors k n | otherwise = oddFactors (k+2) n
could eventually push 394783681-673 function calls onto the stack before finding
the factor 394783681. And indeed a recursive version of divisions trying to
compute this ran more than two hours on my machine, before i stopped it (this is
the time a python script needs for the computation). And there were peaks of
memory use > 300 MB ! While the version with the State monad seems to
work tail recursive - it has an absolutely constant memory use, slightly
different per run, i watched 2044k and 2056k. And it takes around 17 minutes on
my machine getting the result.
Thus it's vital here, how the recursion is done. Because of that i separated
divisions and divstep - for experimenting with divisions. If a factor is done,
it should leave as little traces as possible on the machine.
Both of your instructions for fix are well readable - thanks again. I'll spend
some time studying them, but it seems, fix doesn't fix the problem.
More information about the Haskell-Cafe
mailing list