Fixed point combinator in Haskell

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.

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.

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.