这是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)
4条答案
按热度按时间ui7jx7zq1#
首先,注意这不是一个Y-combinator,因为函数的lambda版本使用了自由变量Y。它是Y的正确表达式,只是不是一个组合子。
因此,让我们首先将计算阶乘的部分放入一个单独的函数中。我们可以称之为comp:
factorial函数现在可以这样构造:
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:
这一
是语法糖
这意味着我们把整个东西 Package 成了一个函数。我们这样做没有损失,只有收获。
我们得到了什么?这和回答前一个问题的技巧一样通过这种方式,我们实现了
func(Y(func))
仅在需要时才被评估,因为它被 Package 在函数中。这样我们就可以避免无限循环。将(单参数)函数f展开为函数x => f(x)称为 eta-expansion(你可以在这里阅读更多)。下面是eta扩展的另一个简单例子:假设我们有一个方法
getSquare()
,它返回一个简单的square()
函数(即计算数字平方的函数)。我们可以不直接返回square(x),而是返回一个接受x并返回square(x)的函数:希望这能帮上忙。
s6fujrry2#
补充公认的答案
首先,注意这不是一个Y组合子,因为lambda版本的函数使用了自由变量Y。它是Y的正确表达式,只是不是一个组合子。
组合子不允许显式递归;它必须是一个没有自由变量的lambda表达式,这意味着它不能在定义中引用自己的名字。在lambda演算中,不可能引用函数体中函数的定义。递归只能通过传入函数作为参数来实现。
考虑到这一点,我从rosetta代码中复制了以下实现,该代码使用了一些类型技巧来实现Y组合子,而没有显式递归。看这里
希望这有助于理解。
b09cbbtk3#
我不知道答案,但我会猜一猜。既然你有
def Y[T](f: ...) = f(...)
编译器可以尝试用简单的f
代替Y(f)
。这将创建f(f(f(...)))
的无限序列。部分应用f
创建了一个新对象,这样的替换就变得不可能了。p3rjfoxz4#
不幸的是,公认的答案是完全错误的。函数参数没有什么魔力;特别是,它们在默认情况下不是别名或惰性。让我们看看你的代码,为了可读性稍微重写了一下:
Q1:120的结果是怎么一步一步出来的?
让我们用手来运行它!在下文中,每一行是还原步骤的结果,并且每个注解描述用于该步骤的还原。
这里要理解的关键是,
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)的影响:看到问题了吗使用匿名函数可以防止构建这种无限的调用堆栈。