fixed point

[Paul Hudak]

Thomas L. Bevan wrote:
 > Is there a simple transformation that can be applied to all
 > recursive functions to render them non-recursive with fix.

Suppose you have a LET expression with a set of (possibly mutually 
recursive) equations such as:

let f1 = e1
     f2 = e2
     ...
     fn = en
in e

The following is then equivalent to the above, assuming that g is not 
free in e or any of the ei:

let (f1,...,fn) = fix g
     g ~(f1,...,fn) = (e1,...,en)
in e

Note that all recursion introduced by the top-most LET has been removed 
(or, if you will, concentrated into the one application of fix).  This 
transformation will work even if there is no recursion, and even if some 
of the fi are not functions (for example they could be recursively 
defined lazy data structures).

For example:

main1 =
   let rem = \a b -> if a < b then a
                     else rem (a - b) b
       ones = 1 : ones
       x   = 42
   in (rem 42 9, take 3 ones, x)

is equivalent to:

main2 =
   let (rem,ones,x)    = fix g
       g ~(rem,ones,x) = (\a b -> if a < b then a
                                  else rem (a - b) b,
                          1 : ones,
                          42
                         )
   in (rem 42 7, take 3 ones, x)

and both yield the result (6,[1,1,1],42).

-Paul