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 _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe