解释Scala中Y组合子的实现?

wgxvkvu9  于 2023-06-23  发布在  Scala
关注(0)|答案(4)|浏览(114)

这是Scala中Y-combinator的一个实现:

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在执行过程中是如何出来的?
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.StackOverflowError
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
ui7jx7zq

ui7jx7zq1#

首先,注意这不是一个Y-combinator,因为函数的lambda版本使用了自由变量Y。它是Y的正确表达式,只是不是一个组合子。
因此,让我们首先将计算阶乘的部分放入一个单独的函数中。我们可以称之为comp:

def comp(f: Int => Int) =
  (n: Int) => {
    if (n <= 0) 1
    else n * f(n - 1)
  }

factorial函数现在可以这样构造:

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)部分是一个函数,只有在需要时才会被评估。
你知道Scala中的按值调用和按名称调用参数吗?如果你声明你的参数为someFunction(x: Int),那么调用someFunction时它就会被计算。但是如果你将它声明为someFunction(x: => Int),那么x不会立即被计算,而是在它被使用的地方被计算。第二个调用是“按名称调用”,它基本上是将x定义为“不接受任何内容并返回Int的函数”。所以如果你传入5,你实际上是传入一个返回5的函数。通过这种方式,我们实现了函数参数的延迟求值,因为函数在使用时被求值。
因此,comp中的参数f是一个函数,因此它只在需要时进行求值,这是在else分支中。这就是为什么整件事都能起作用的原因- Y可以创建一个func(func(func(func(...)))的无限链,但这个链是惰性的。仅在需要时计算每个新链路。
所以当你调用fact(5)时,它会通过body运行到else分支,只有在那个点f才会被计算。之前没有由于Y作为参数f传入comp(),我们将再次深入comp()。在comp()的递归调用中,我们将计算4的阶乘。然后,我们将再次进入comp函数的else分支,从而有效地进入另一层次的递归(计算3的阶乘)。请注意,在每个函数调用中,Y都提供了一个comp作为comp的参数,但它只在else分支中进行计算。一旦我们到达计算阶乘为0的级别,if分支将被触发,我们将停止进一步向下跳水。
Q2:
这一

func(Y(func))(_:T)

是语法糖

x => func(Y(func))(x)

这意味着我们把整个东西 Package 成了一个函数。我们这样做没有损失,只有收获。
我们得到了什么?这和回答前一个问题的技巧一样通过这种方式,我们实现了func(Y(func))仅在需要时才被评估,因为它被 Package 在函数中。这样我们就可以避免无限循环。将(单参数)函数f展开为函数x => f(x)称为 eta-expansion(你可以在这里阅读更多)。
下面是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

希望这能帮上忙。

s6fujrry

s6fujrry2#

补充公认的答案
首先,注意这不是一个Y组合子,因为lambda版本的函数使用了自由变量Y。它是Y的正确表达式,只是不是一个组合子。
组合子不允许显式递归;它必须是一个没有自由变量的lambda表达式,这意味着它不能在定义中引用自己的名字。在lambda演算中,不可能引用函数体中函数的定义。递归只能通过传入函数作为参数来实现。
考虑到这一点,我从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))
  }

希望这有助于理解。

b09cbbtk

b09cbbtk3#

我不知道答案,但我会猜一猜。既然你有def Y[T](f: ...) = f(...)编译器可以尝试用简单的f代替Y(f)。这将创建f(f(f(...)))的无限序列。部分应用f创建了一个新对象,这样的替换就变得不可能了。

p3rjfoxz

p3rjfoxz4#

不幸的是,公认的答案是完全错误的。函数参数没有什么魔力;特别是,它们在默认情况下不是别名或惰性。让我们看看你的代码,为了可读性稍微重写了一下:

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(Y(F))在调用F之前只减少一次:由于匿名函数的存在,Y(F)变成了t => F(Y(F))(t),不能再进一步缩减,然后调用F,进行阶乘计算。

Q2. t => F(Y(F))(t)F(Y(F))有什么区别?

第一个使用了一个匿名函数来延迟计算(thunk)。在t => F(Y(F))(t)中,直到t的值被传递给函数时,内部的Y(F)才会被计算。在F(Y(F))中,函数调用的无限嵌套被立即构造。让我们看看这个新定义对事实(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)
// { ... }

看到问题了吗使用匿名函数可以防止构建这种无限的调用堆栈。

相关问题