[Haskell-cafe] MonadFix
Joost Behrends
joost at h-labahn.de
Tue Dec 18 11:26:51 EST 2007
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
divstep :: DivIter -> DivIter
divstep x | divisor x > bound x = x
| ximod > 0 = x { divisor = (divisor x) +2 }
| otherwise = x {dividend=xidiv,
bound=intsqrt(xidiv),
result = result x ++ [divisor x] }
where
(xidiv, ximod) = divMod (dividend x) (divisor x)
(dividend x is already odd, when this is called).
The problem to solve for really large Integers is how to call divstep iterated
without not accumulating billions of stack frames. Here is one possibility:
divisions = do
y <- get
if divisor y <= bound y then do
put ( divstep y )
divisions
else
return y
(this for a version of divstep without the first guard) called from
res = execState divisions (DivIter { dividend = o1,
divisor = 3,
bound = intsqrt(o1),
result = o2 })
( where o1 "the odd part" of the number to decompose, o2 a list of its
"contained" twos). This computes the primefactors of 2^120+1 in 17 minutes after
all. But i cannot help feeling that this is an abuse of the State monad. The
MonadFix has a function fix (a -> a) -> a and i added the first guard in
divstep above for making this a fixpoint problem.
For me the signature looks, as if using fix doesn't afford to create explicitely
a variable of a MonadFix instance and a simple twoliner for divisions could do
the job. What i do not understand at all from the documentation of fix is:
"fix f is the least fixed point of the function f, i.e. the least defined x
such that f x = x."
What does "least" mean here ? There is nothing said about x being a variable of
an instance of Ord. And why fix has not the type a -> (a -> a) -> a, means: How
can i provide a starting point of the iteration x ==> f x ==> f (f x) ==> ...?
More information about the Haskell-Cafe
mailing list