fixed point

[Josef Svenningsson]

On Mon, 27 Oct 2003, Paul Hudak wrote:

> 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).
>
This is a very nice technique. As an exercise to the reader I suggest the
following program:

\being{code}
data Tree a = Branch a (Tree (a,a)) | Leaf

cross f (a,b) = (f a,f b)

main1 =
  let mapTree :: (a -> b) -> Tree a -> Tree b
      mapTree = \f tree -> case tree of
                            Branch a t -> Branch (f a) (mapTree (cross f) t)
                            Leaf -> Leaf
  in mapTree id (Branch 42 Leaf)
\end{code]

	/Josef