Объясните эту реализацию Y комбинатора в Scala?
Это реализация Y-комбинатора в Scala:
scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
Y: [T](func: (T => T) => (T => T))T => T
scala> def fact = Y {
| f: (Int => Int) =>
| n: Int =>
| if(n <= 0) 1
| else n * f(n - 1)}
fact: Int => Int
scala> println(fact(5))
120
Q1: как результат 120 выходи шаг за шагом? Поскольку Y(func) определяется как func(Y(func)), Y должно становиться все больше и больше, Где Y потерялся и как 120 выйти в процессе peform?
Q2: в чем разница между
def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
а также
def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))
Они одинакового типа в scala REPL, но второй не может распечатать результат 120?
scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))
Y: [T](func: (T => T) => (T => T))T => T
scala> def fact = Y {
| f: (Int => Int) =>
| n: Int =>
| if(n <= 0) 1
| else n * f(n - 1)}
fact: Int => Int
scala> println(fact(5))
java.lang.StackruError
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
4 ответа
Прежде всего, обратите внимание, что это не Y-комбинатор, так как лямбда-версия функции использует свободную переменную Y. Это правильное выражение для Y, но только не комбинатор.
Итак, давайте сначала поместим часть, которая вычисляет факториал, в отдельную функцию. Мы можем назвать это comp:
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 принимает функцию и не оценивает ее, пока не понадобится. Таким образом, среда выполнения видит comp (Y(comp)) как comp(???), потому что часть Y(comp) является функцией и будет оцениваться только тогда, когда (если) потребуется.
Знаете ли вы о параметрах call-by-value и call-by-name в 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-расширением (подробнее об этом можно прочитать здесь).
Вот еще один простой пример расширения eta: допустим, у нас есть метод getSquare() который возвращает простое square() функция (то есть функция, которая вычисляет квадрат числа). Вместо прямого возврата square(x), мы можем вернуть функцию, которая принимает x и возвращает square(x):
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
Надеюсь это поможет.
Дополняя принятый ответ,
Прежде всего, обратите внимание, что это не Y-комбинатор, так как лямбда-версия функции использует свободную переменную Y. Это правильное выражение для Y, но не комбинатор.
Комбинатор не может быть явно рекурсивным; это должно быть лямбда-выражение без свободных переменных, что означает, что оно не может ссылаться на собственное имя в своем определении. В лямбда-исчислении невозможно сослаться на определение функции в теле функции. Рекурсия может быть достигнута только путем передачи функции в качестве параметра.
Учитывая это, я скопировал следующую реализацию из кода Rosetta, который использует некоторые уловки типов для реализации комбинатора Y без явной рекурсии. Смотрите здесь
def Y[A, B](f: (A => B) => (A => B)): A => B = {
case class W(wf: W => A => B) {
def get: A => B =
wf(this)
}
val g: W => A => B = w => a => f(w.get)(a)
g(W(g))
}
Надеюсь, это поможет с пониманием.
Я не знаю ответа, но постараюсь угадать. Так как у вас есть def Y[T](f: ...) = f(...) компилятор может попытаться подставить Y(f) с просто f, Это создаст бесконечную последовательность f(f(f(...))), Частично применяется f Вы создаете новый объект, и такая замена становится невозможной.
К сожалению, принятый ответ совершенно неверен. В параметрах функций нет ничего волшебного; в частности, по умолчанию они не являются поименными или ленивыми. Давайте посмотрим на ваш код, слегка переписанный для удобства чтения:
def Y[T](F: (T => T) => (T => T)): (T => T) =
t => F(Y(F))(t)
def F(f: Int => Int)(n: Int) =
if (n <= 0) then 1 else n * f(n - 1)
val fact = Y(F)
Q1: Как пошагово получается результат 120?
Давайте запустим его вручную! Далее каждая строка является результатом этапа сокращения, а каждый комментарий описывает сокращение, использованное для этого шага.
fact(5)
// { Apply `fact` }
Y(F)(5)
// { Apply `Y` }
(t => F(Y(F))(t))(5)
// { Apply the anonymous function }
F(Y(F))(5) // Here we learned that `F(Y(F))(5)` is the same as `fact(5)`
// { Reduce the first argument of F: Apply `Y` }
F(t => F(Y(F))(t))(5)
// { Apply `F` }
if (5 <= 0) then 1 else 5 * (t => F(Y(F))(t))(4)
// { Simplify the if }
5 * (t => F(Y(F))(t))(4)
// { Reduce the arguments of `*`: Apply the anonymous function }
5 * F(Y(F))(4)
// { Notice the repeated pattern }
5 * fact(4)
// { ... }
Здесь важно понимать, что вызывается только один раз, прежде чем вызывается: из-за анонимной функции становится, которую невозможно сократить дальше, а затемFвызывается, и происходит этап вычисления факториала.
В2. В чем разница между и ?
Первый использует анонимную функцию, которая задерживает вычисления («thunk»). Вt => F(Y(F))(t), внутреннийY(F)не оценивается до тех пор, пока не будет получено значение дляtпередается в функцию. ВF(Y(F)), немедленно создается бесконечное вложение вызовов функций. Давайте посмотрим, что произойдет с fact(5) с этим новым определением:
fact(5)
// { Apply `fact` }
Y(F)(5)
// { Apply `Y` }
F(Y(F))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(Y(F)))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(F(Y(F))))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(F(F(Y(F)))))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(F(F(F(Y(F))))))(5)
// { ... }
Видите проблему? Использование анонимной функции предотвращает создание этого бесконечного стека вызовов.