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

• A+
Category：Languages

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