How to use Y- Combinator; why does this infinite recursion return 9?

Question

Y - Combinator

I've been trying to learn about Y - Combinators (an explanation on that would be lovely as well) and came across an example from this wiki. An in depth explanation on the subject would be much appreciated in either Haskell or Python. Pleaaase!

Code

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

Problem

The function calledfix returns 9 when fix is applied to (\x -> 9) and I have no clue why; when I follow the stack I visualize f(f ... (fix f) ...).

>> fix (\x -> 9)
>> 9

Ancipital

Answer 1

First of all: the fix function you have is a fixed-point combinator implemented with direct recursion. The Y combinator is a particular fixed-point combinator that does not need syntactic recursion so it accomplished the same thing as fix but in a different way.

If you're curious, you can look at how to implement the Y combinator in Haskell here on SO. It's a bit tricky with static types—it needs a recursive type to work.

As for your second question, the code works thanks to laziness. If you apply (\ x -> 9) to anything, that thing will never get evaluated. Try this:

λ> (\ x -> 9) (error "fail")
9

This includes the recursive call in the definition of fix. Look at what happens when you replace the outer-most f with (\ x -> 9) in the definition of fix:

(\ x -> 9) (fix f)

Following exactly the same logic as the version with error, the recursive call never gets evaluated and you just get a 9 out.

Landri