fixed point

Derek Elkins ddarius at hotpop.com
Sun Oct 26 19:41:32 EST 2003


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).



More information about the Haskell-Cafe mailing list