Fixed point combinator in Haskell

Question

The fixed point combinator doesn't always produce the right answer given the definition:

fix f = f (fix f)

The following code does not terminate:

fix (\x->x*x) 0

Of course, fix can't always produce the right answer, but I was wondering, can this be improved?

Certainly for the above example, one can implement some fix that looks like

fix f x | f x == f (f x)  = f x
        | otherwise       = fix f (f x)

and gives the correct output.

What is the reason the above definition (or something even better, as this one only handle function with 1 parameter) is not used instead?

Stretch

The fix point combinator always returns a correct result, but it might not be the result you want, since it frequently involves bottom. – Kaifeng

If you are interested in the deeper meaning of fix, this is an illuminating read: en.wikibooks.org/wiki/Haskell/Denotational_semantics – Copenhagen

Answer 1

Fixed point combinator finds the least-defined fixed point of a function, which is ⊥ in your case (non-termination indeed is undefined value).

You can check, that in your case

(\x -> x * x) ⊥ = ⊥

i.e. ⊥ really is fixed point of \x -> x * x.

As for why is fix defined that way: the main point of fix is to allow you use anonymous recursion and for that you do not need more sophisticated definition.

Gilthead

It is important to note that Haskell's cpo over which that definition of fix makes sense is not the usual ordering relation on the (say) real numbers. Rather, it is the information-theoretic partial order where ⊥ is the undefined value that is a member of every (non-strict) data type in Haskell, and all the usual real numbers x are ⊥ ⊑ x. A so-called lifted discrete CPO. – Chaplin

I think he meant domain-theoretic, not information-theoretic. – Marijn

Answer 2

Your example does not even typecheck:

Prelude> fix (\x->x*x) 0

<interactive>:1:11:
    No instance for (Num (a0 -> t0))
      arising from a use of `*'
    Possible fix: add an instance declaration for (Num (a0 -> t0))
    In the expression: x * x
    In the first argument of `fix', namely `(\ x -> x * x)'
    In the expression: fix (\ x -> x * x) 0

And that gives the clue as to why it doesn't work as you expect. The x in your anonymous function is supposed to be a function, not a number. The reason for this is, as Vitus suggests, that a fixpoint combinator is a way to write recursion without actually writing recursion. The general idea is that a recursive definition like

f x = if x == 0 then 1 else x * f (x-1)

can be written as

f    = fix (\f' x -> if x == 0  then 1 else x * f' (x-1))

Your example

fix (\x->x*x) 0

thus corresponds to the expression

let x = x*x in x 0

which makes no sense.

Spadework

he probably wanted fix (\x->x*x) (without the 0), which does typecheck – Foliate

I doubt it. He seemed to expect it to produce output under his revised fix, which your version doesn't do (there being no Show instance for functions). My admittedly speculative take was that he expected x*x to become 0*0 in that situation, short-circuiting the process somehow. – Spadework

Answer 3

I'm not entirely qualified to talk about what the "fixpoint combinator" is, or what the "least fixed point" is, but it is possible to use a fix-esque technique to approximate certain functions.

Translating Scala by Example section 4.4 to Haskell:

sqrt' :: Double -> Double
sqrt' x = sqrtIter 1.0
  where sqrtIter guess | isGoodEnough guess = guess
                       | otherwise          = sqrtIter (improve guess)
        improve guess = (guess + x / guess) / 2
        isGoodEnough guess = abs (guess * guess - x) < 0.001

This function works by repeatedly "improving" a guess until we determine that it is "good enough". This pattern can be abstracted:

myFix :: (a -> a)       -- "improve" the guess
      -> (a -> Bool)    -- determine if a guess is "good enough"
      -> a              -- starting guess
      -> a
fixApprox improve isGoodEnough startGuess = iter startGuess
  where iter guess | isGoodEnough guess = guess
                   | otherwise          = iter (improve guess)

sqrt'' :: Double -> Double
sqrt'' x = myFix improve isGoodEnough 1.0
  where improve guess = (guess + x / guess) / 2
        isGoodEnough guess = abs (guess * guess - x) < 0.001

See also Scala by Example section 5.3. fixApprox can be used to approximate the fixed point of the improve function passed into it. It repeatedly invokes improve on the input until the output isGoodEnough.

In fact, you can use myFix not only for approximations, but for exact answers as well.

primeAfter :: Int -> Int
primeAfter n = myFix improve isPrime (succ n)
  where improve = succ
        isPrime x = null [z | z <- [2..pred x], x `rem` z == 0]

This is a pretty dumb way to generate primes, but it illustrates the point. Hm...now I wonder...does something like myFix already exist? Stop...Hoogle time!

Hoogling (a -> a) -> (a -> Bool) -> a -> a, the very first hit is until.

until p f yields the result of applying f until p holds.

Well there you have it. As it turns out, myFix = flip until.

Asher

(Note that primeAfter isn't actually a correct example of finding a "fixed point") – Asher

+1 because, although you don't mention what fix actually does, I think this is the only answer to provide a function that resembles what the OP wants. – Ratify

Answer 4

You probably meant iterate:

*Main> take 8 $ iterate (^2) (0.0 ::Float)
[0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
*Main> take 8 $ iterate (^2) (0.001 ::Float)
[1.0e-3,1.0000001e-6,1.0000002e-12,1.0000004e-24,0.0,0.0,0.0,0.0]

*Main> take 8 $ iterate (^2) (0.999 ::Float)
[0.999,0.99800104,0.9960061,0.9920281,0.9841198,0.96849173,0.93797624,0.8797994]
*Main> take 8 $ iterate (^2) (1.0 ::Float)
[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]
*Main> take 8 $ iterate (^2) (1.001 ::Float)
[1.001,1.002001,1.0040061,1.0080284,1.0161213,1.0325024,1.0660613,1.1364866]

Here you have all the execution history explicitly available for your analysis. You can attempt to detect the fixed point with

fixed f from = snd . head 
                   . until ((< 1e-16).abs.uncurry (-).head) tail 
               $ _S zip tail history
  where history = iterate f from
        _S f g x = f x (g x)

and then

*Main> fixed (^2) (0.999 :: Float)
0.0

but trying fixed (^2) (1.001 :: Float) will loop indefinitely, so you'd need to develop separate testing for convergence, and even then detection of repellent fixed points like 1.0 will need more elaborate investigation.

Mlle

Answer 5

You can't define fix the way you've mentioned since f x may not even be comparable. For instance, consider the example below:

myFix f x | f x == f (f x)  = f x
          | otherwise       = myFix f (f x)

addG f a b =
  if a == 0 then
    b
  else
    f (a - 1) (b + 1)

add = fix addG -- Works as expected.
-- addM = myFix addG (Compile error)

Mccraw