[Haskell-cafe] MonadFix

[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 

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) ==> ...?