Search code examples
haskellfixpoint-combinators

a fixed point for fix :: Eq 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

Solution

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