Re: fixed point

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" 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@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"