[Haskell-cafe] MonadFix

[Daniel Fischer]

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

It's quite another thing,
fix is not a fixed point iteration as used in calculus, least here means 
'least defined'.
The least defined of all values is 'undefined' (aka bottom, often denoted by 
_|_).
For simple data types like Int or Bool, a value is either completely defined 
or undefined, and both True and False are more defined than bottom, but 
neither is more or less defined than the other.
For a recursive data type like lists, you have a more interesting hierarrchy 
of definedness:
_|_ is less defined than _|_:_|_ is less defined than _|_:_|_:_|_ is less 
defined than _|_:_|_:_|_:_|_ ...
And definedness of list elements is also interesting,
_|_:_|_:_|_ is less defined than 1:_|_:_|_ is less defined than 1:2:_|_ is 
less defined than 1:2:3:_|_ is less defined than ...

You cannot use fix on a strict function (a function is strict iff f _|_ = 
_|_), as by its implementation,
fix f = let x = fix f in f x
IIRC, it's calculated without knowing what x is when f is called.
fix f is basically
lim xn, when 
x0 = undefined, 
x(n+1) = f xn

And since f x is always at least as defined as x, xn is a monotonic sequence 
(monotonic with respect to definedness), so the limit exists - it's _|_ for 
strict functions, and if we follow a few steps of the easy example fix (1:), 
we see
x0 = _|_
x1 = 1:_|_
x2 = 1:1:_|_
x3 = 1:1:1:_|_,
hence fix (1:) == repeat 1.

HTH,
Daniel