fixed point

[Thomas L. Bevan]

Is there a simple transformation that can be applied to all
recursive functions to render them non-recursive with fix.
( i suppose there must be or we wouldn't have haskell right? )

ie 
f :: a -> a
f x = .... f ....

g :: (a -> a) -> (a -> a)
g = \f -> \a ( .... f .... )

fix g = f


where .... f ... has the same structure in both cases?

On Mon, 27 Oct 2003 11:41 am, Derek Elkins wrote:
> On Sun, 26 Oct 2003 19:24:26 -0500
>
> "Harris, Andrew" <Andrew.Harris at jhuapl.edu> wrote:
> > Hi -
> >
> > 	I am trying to do Exercise 9.9 in HSOE; and I've come up with an
> > answer that works but I'm not sure if it answers the question
> > properly.  The problem is:
> >
> > The Question:
> > -------------
> >
> > Suppose we define a function "fix" as:
> >
> > fix f = f (fix f)
> >
> > Suppose further we have a recursive function:
> >
> > remainder :: Integer -> Integer -> Integer
> > remainder a b = if a < b then a
> >                 else remainder (a - b) b
> >
> > Rewrite this function using "fix" so that it's not recursive.
> >
> > My Answer:
> > ----------
> >
> > wierdFunc x y z = if y - z > z then ((\a b c -> a b c) x (y-z) z)
> >                   else ((\a b c -> a b c) (\d e -> d) (y-z) z)
> >
> > myRemainder = fix wierdFunc
> >
> > My Question:
> > ------------
> >
> > Does the ((\a b c -> a b c) x (y-z) z) mean that I've not removed the
> > recursion?  I was assuming that I was returning a function that is to
> > be evaluated and not actually doing any recursion.  That's why I
> > thought I answered the question.  However, I have a headache now and
> > would like another opinion.
>
> Notice that, (\x -> x) a reduces to a, so (\a b c -> a b c) x (y-z) z
> reduces to x (y-z) z.  You can therefore simplify your function quite a
> bit.
> wierdFunc x y z = if y-z > z then x (y-z) z else (\d e -> d) (y-z) z
> and you can still apply that lambda abstraction (beta-reduce)
> wierdFunc x y z = if y-z > z then x (y-z) z else y-z
> None of these (except, of course, fix and remainder) are recursive.  A
> recursive function is just one that calls itself.  For wierdFunc to be
> recursive, the identifier wierdFunc would have to occur in the
> right-hand side of it's definition.
>
> This all said, you are making the problem much more difficult than it
> needs to be.  Try matching up your x,y,z's to things in remainder and I
> think the expected answer will become obvious.  Also, you may want to
> look at the type of fix and wierdFunc (you can use :type in Hugs or
> GHCi).
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-- 
If people have to choose between freedom and sandwiches, they
will take sandwiches.
		-- Lord Boyd-orr

Eats first, morals after.
		-- Bertolt Brecht, "The Threepenny Opera"