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
-- 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
x2 is the next
x == x2, we return
x2), if not, we calculate the fixed point of
x2, so we advanced one step in the "Quest for the fixed point".