[Haskell-cafe] Re: MonadFix

[Joost Behrends]

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.