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