# fixed point

Paul Hudak paul.hudak at yale.edu
Mon Oct 27 09:24:20 EST 2003

```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

```