a fixed point for fix :: Eq a => (a -> a) -> a -> a

  • A+

Hello everyone I'm trying to implement the higher-order function fix, which computes an attractive fixed point of an arbitrary function f :: a -> a from an initial point x. That is, a fixed point of the form fᴷ(x) for a given f and x.

-- CONTRACT fix :: Eq a => (a -> a) -> a -> a -- DEFINITION [TODO: Implement fix] fix f x  = ? 

My current attempt is:

fix f x | f x == x = x         | otherwise = fix f x     where x = f x 

Note: Your function will not terminate if the function does not converge from the starting point. can someone help me please ? I tried but it didn't return anything


A common misconception is that when you write x = ..., you assign a value in Haskell. In Haskell one does not assign a value, one declares one.

This thus means that basically you constructed a variable x in the where clause that is not the x in the head of the function, so something like:

fix :: Eq a => (a -> a) -> a -> a fix f _ | f x == x = x         | otherwise = fix f x     where x = f x

Here you thus defined x in terms of itself: x = f x, so that means if Haskell aims to evaluate that, it will start calculating f(f(f(f(f(f(...)))))), but without any checks if the fixed point has been reached.

The solution is thus to introduce a new variable, for example x2, and thus use this like:

fix :: Eq a => (a -> a) -> a -> a fix f x | x == x2 = x         | otherwise = fix f x2     where x2 = f x

So here x2 is the next x. Given x == x2, we return x (or x2), if not, we calculate the fixed point of f and x2, so we advanced one step in the "Quest for the fixed point".


:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: