Прежде всего, отметим, что это не является Y-комбинатор, так как версия лямбда-функции использует свободную переменную Y. Это правильное выражение для Y, но для того, чтобы быть комбинатор он нуждается в некоторой подтяжке лица. Here’s некоторые предлагаемые для этого чтения.
Теперь, для ясности, возьмем ту часть, которая вычисляет факториал в отдельную функцию. Мы можем назвать это комп:
def comp(f: Int => Int) =
(n: Int) => {
if (n <= 0) 1
else n * f(n - 1)
}
Факториал функция теперь может быть построена следующим образом:
def fact = Y(comp)
Q1:
Y определяется как FUNC (Y (FUNC)). Мы вызываем факт (5), который на самом деле Y (comp) (5), а Y (comp) вычисляется до comp (Y (comp)). Это ключевой момент: мы остановиться здесь потому что комп принимает функцию и не оценивает его, пока не потребуется. Таким образом, среда выполнения считает comp (Y (comp)) как comp (???), потому что часть Y (comp) является функцией и будет оцениваться только тогда, когда (если) необходимо.
Знаете ли вы о параметрах вызова по значению и по вызову в Scala? Если вы объявите свой параметр как someFunction(x: Int)
, он будет оценен сразу после вызова функции someFunction. Но если вы объявите его как someFunction(x: => Int)
, тогда x не будет оцениваться сразу, но в том месте, где он используется. Второй вызов - это «вызов по имени», и он в основном определяет вашу x как «функцию, которая ничего не принимает и возвращает Int». Поэтому, если вы проходите в 5, вы фактически передаете функцию, которая возвращает 5. Таким образом мы достигаем ленивой оценки параметров функции, поскольку функции оцениваются в той точке, в которой они используются.
Таким образом, параметр f в comp является функцией, поэтому он оценивается только при необходимости, который находится в ветке else. Вот почему все это работает - Y может создать бесконечную цепочку func (func (func (func (...)))), но цепочка ленива. Каждая новая ссылка вычисляется только при необходимости.
Итак, когда вы вызываете факт (5), он будет проходить через тело в ветку else и только в этой точке f будет оценен. Не раньше, чем. Поскольку ваш Y передан в comp() как параметр f, мы снова погрузимся в comp(). В рекурсивном вызове comp() мы будем вычислять факториал из 4. Затем мы снова перейдем в другую ветвь функции comp, тем самым эффективно погрузившись в другой уровень рекурсии (вычисляя факторный из 3). Обратите внимание, что в каждой функции вызов Y предоставил comp в качестве аргумента для comp, но он оценивается только в ветке else. Как только мы дойдем до уровня, который вычисляет факториал 0, ветка if будет запущена, и мы прекратим погружение дальше вниз.
Q2:
Это
func(Y(func))(_:T)
является синтаксисом для этого
x => func(Y(func))(x)
, который означает, что мы обернули все это в функцию. Мы ничего не потеряли, сделав это, только выиграли.
Что мы получили? Ну, это тот же трюк, что и в ответе на предыдущий вопрос; таким образом мы достигаем, что func(Y(func))
будет оцениваться только при необходимости, поскольку он завернут в функцию. Таким образом, мы избежим бесконечного цикла. Разложение (однопараметрическая) функция f на функцию x => f (x) называется eta-expansion (вы можете узнать больше об этом here).
Вот еще один простой пример eta-расширения: допустим, у нас есть метод getSquare()
, который возвращает простую функцию square()
(то есть функцию, которая вычисляет квадрат числа). Вместо возвращение квадрата (х) непосредственно, мы можем вернуть функцию, которая принимает й и возвращает квадрат (х):
def square(x: Int) = x * x
val getSquare: Int => Int = square
val getSquare2: Int => Int = (x: Int) => square(x)
println(square(5)) // 25
println(getSquare(5)) // 25
println(getSquare2(5)) // 25
Надеется, что это помогает.