First of all, note that this is not a Y-combinator, since the lambda version of the function uses the free variable Y. This is the correct expression for Y, but in order for it to be a combinator, it must undergo a facelift. Heres some suggested reading for this.
Now, for clarity, let's take the part that computes the factorial into a separate function. We can call it comp:
def comp(f: Int => Int) = (n: Int) => { if (n <= 0) 1 else n * f(n - 1) }
Now the factorial function can be constructed as follows:
def fact = Y(comp)
Q1:
Y is defined as func (Y (func)). We invoke fact (5), which is actually Y (comp) (5), and Y (comp) is computed before comp (Y (comp)). This is a key point: we will stop here because comp accepts the function, not evaluates it until needed . Thus, the runtime considers comp (Y (comp)) as comp (???), because the part of Y (comp) is a function and will be evaluated only when (if) necessary.
Do you know the default options and name by name in Scala? If you declare your parameter as someFunction(x: Int) , it will be evaluated as soon as someFunction is called. But if you declare it as someFunction(x: => Int) , then x will not be evaluated immediately, but in the place where it is used. The second call is a "call by name", and it basically defines your x as a "function that takes nothing and returns an Int". Therefore, if you go through 5, you actually pass in a function that returns 5. This way we achieve a lazy evaluation of the parameters of the function, since the functions are evaluated at the point at which they are used.
Thus, the f parameter in comp is a function, so it is evaluated only when necessary, which is in the else branch. That's why it all works - Y can create an endless chain of func (func (func (func (...))), but the chain is lazy. Each new link is calculated only if necessary.
Therefore, when you call fact (5), it will go through the body to the else branch and only at this point will f be evaluated . No sooner than. Since your Y is passed to comp () as the parameter f, we dive into comp () again. In the recursive call to comp (), we will calculate the factorial from 4. Then we again go to another branch of the comp function, thereby effectively plunging into another level of recursion (calculating the factorial from 3). Note that in each function, the call to Y provided comp as an argument to comp, but it is evaluated only in the else branch. As soon as we get to the level that calculates factorial 0, the if branch will start, and we will stop diving further down.
2:
it
func(Y(func))(_:T)
is syntactic sugar for this
x => func(Y(func))(x)
which means we wrapped it all up in a function. We did not lose anything by doing this, we only won.
What did we get? Well, this is the same trick as in the answer to the previous question; Thus, we achieve that func(Y(func)) will be evaluated only if necessary from the moment it is included in the function. In this way, we avoid an infinite loop. The expansion of the (one-parameter) function f into the function x => f (x) is called an eta-extension (you can read more about this here ).
Here is another simple example of an eta extension: let's say we have a getSquare() method that returns a simple square() function (that is, a function that calculates the square of a number). Instead of directly returning the square (x), we can return a function that takes x and returns the square (x):
def square(x: Int) = x * x val getSquare: Int => Int = square val getSquare2: Int => Int = (x: Int) => square(x) println(square(5))
Hope this helps.