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

Question

Y - Combinator

I tried to learn about Y - Combinators (an explanation for this would be great too) and came across an example from the wiki . A detailed explanation on this would be highly appreciated in either Haskell or Python. Pleaaase!

The code

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

Problem

A function called fix returns 9 when fix is applied to (\x -> 9) , and I don't know why; when I follow the stack, I render f(f ... (fix f) ...) .

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

Answer 1

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

If you're interested, you can see how to implement Y combinator in Haskell here on SO. This is a bit tricky with static types - a recursive type is required to work.

As for your second question, the code works thanks to laziness. If you apply (\ x -> 9) to something, this thing will never be appreciated. Try the following:

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

This includes a recursive call in the fix definition. See what happens if you replace the external f (\ x -> 9) with the fix definition:

 (\ x -> 9) (fix f) 

Following the same logic as the version with error , the recursive call is never evaluated, and you just get 9 .