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.

Answer 2

Given a function f, what's the value of fix f? It's some point x where x = f x. Replacing English verbiage above with Haskell, we get

fix f = x where x = f x

Try fix (1:) or fix (const 42).

That's it. Now any value x returned by fix f equals f x, by definition. That's if fix f returns a value — for many inputs it doesn't (try fix (+ 1)). It doesn't return a value even for functions that ostensibly do have a fixed point (e.g. f x = 2^(x-1)). But that's another story...

Answer 3

Technically it could be implemented as

fix f x = let x' = f x in if x == x' then x else fix f x'

You try and see that

fix (\x -> (x + 5) `div` 2) 12345

returns 5 and

print $ fix (\x -> (x + 3 / x) / 2) 12345

returns 1.7320508075688772

Answer 4

How can I write it use Haskell?

Let's start from the very end, from the application. So we wish to write recursive anonymous functions, e.g. factorial, thus we need fixed point combinator. Desired result:

fac' :: Integer -> Integer
fac' = fix fac

Where fix is the fixed-point combinator and fac is our factorial combinator (not so anonymous, but this is only for convenience).

Now let's define fac.

fac :: (Integer -> Integer) -> Integer -> Integer
fac _ 1 = 1               -- Fixed point case
fac f x = x * f (x - 1)

Where the first argument, f, is a reference to fac itself. Now we may start reasoning about fix. Let's start from signature. In our example fix takes fac and returns some Integer -> Integer combinator. So our signature is following (considering fix can handle arbitrary typed functions):

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

Let's define it. We have to return some x combinator of type a -> a feeding some combinator of type a -> a to the f. Well, the most obvious solution there is:

fix f = x where x = f x

And this is an actual definition. But its signature is pretty complex... Note that it is possible to substitute a -> a by y. Then we get

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

This is close to the standard library definition. Why does it work? Consider the first case of our fac definition. We don't use first argument there, so laziness prevents from infinite loop at the fixed point.