Haskell : how to get fix point of a function?

Question

A fix-point of a function f is a value x such that f(x)=x . Write a function fix that takes a function f and returns its fix-point.

For example: the pseudocode is as follows：

f(x)= 
if (x=f(x)) return x
      else return f(f(x))

How can I write it use Haskell?

Answer 1

From an application perspective, there are many kinds of fixed points. For instance, I'd like to draw the distinction between logical fixed points and analytical fixed points. Most of the answers in this thread discuss the logical fix point. It can be written quite beautifully in Haskell as follows

fix :: (a -> a) -> a
fix f = x where x = f x

Or even

fix :: (a -> a) -> a
fix f = f (fix f)

This logical fix ends up being a certain kind of natural way to discuss and introduce recursion into a language.

The analytical fix shows up often in numerical computing and has a somewhat different, but related, meaning. We'll begin with the type.

fixa :: (a -> a -> Bool) -> (a -> a) -> a -> Int -> a

This is clearly more complex than simple fix was as it represents guarded descent. Let's begin to write fixa to give names to these arguments

fixa ok iter z n

The goal is to repeatedly apply iter to the starting point z until either n, a positive integer, reaches 0 or ok current previous is True. The implementation reads almost exactly as the prose here does.

fixa ok iter z 0 = z
fixa ok iter z n = loop z n where
  loop z n = 
    let next = iter z
        in if (ok next z)
          then next
          else loop next (n-1)

The value of a function like this is that we can use it to do iterative numerical algorithms, like Newton's Method

newton :: (Double -> Double) -> (Double -> Double) -> Double -> Double
newton f f' z = fixa (\a b -> a - b < 1e-6) (\x -> x - f x / f' x) z 1000

We can also improve it somewhat dramatically by using Haskell's lazy evaluation to spit out a lazy list of results instead of just the final point. When we do this we no longer need the manual loop counter as it's up to the consumer to decide how to manage this list of improvements.

fixaList :: (a -> a -> Bool) -> (a -> a) -> a -> [a]
fixaList ok iter z = loop z where
  loop z = let next = iter z
           in if (ok next z)
             then cycle next -- we'll return next forever
             else z : loop next

fixa ok iter z n = fixaList ok iter z !! n

In fact, we don't need the ok test anymore either, that can also be left to the consumer

fixaList :: (a -> a) -> a -> [a]
fixaList iter z = loop z where loop z = z : loop (iter z)

fixa iter z n = take n (fixaList iter z)

And now fixaList starts to look a bit like fix

fix      f      = x      where x      = f x
fixaList iter z = loop z where loop z = z : loop (iter z)

And, indeed, we can think of fixaList as specializing fix and use fix to write it

fixaList iter z = fix (\loop z -> z : loop (iter z)) z
-- or, eta reduce to
fixaList iter   = fix (\loop z -> z : loop (iter z))

Which is a really long way of saying that logical fixed points are strictly more powerful than analytical ones.