解释Scala中Y组合子的这种实现？
|
这是
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在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.StackOverflowError
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
解决方法
首先,请注意,这不是Y组合子,因为该函数的lambda版本使用自由变量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)).我们调用fact(5)实际上是Y(comp)(5),Y(comp)求值为comp(Y(comp)).这是关键点：我们在这里停止,因为comp需要一个函数,并且在需要之前它不会对它进行评估.因此,运行时将comp(Y(comp))视为comp(???),因为Y(comp)部分是一个函数,只有在需要(if)时才会计算. 你知道Scala中的call-by-value和call-by-name参数吗？如果将参数声明为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) 这意味着我们将整个事物包装成一个函数.这样做我们没有失去任何东西,只是获得了. 我们获得了什么？嗯,这与上一个问题的答案中的伎俩相同;这样我们实现的func(Y(func))将仅在需要时进行评估,因为它包含在函数中.这样我们就可以避免无限循环.将(单参数)函数f扩展为函数x => f(x)称为eta-expansion(你可以阅读更多关于它的here). 这是另一个简单的eta-expansion示例：假设我们有一个方法getSquare(),它返回一个简单的square()函数(即一个计算数字平方的函数).我们可以返回一个取x并返回square(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 希望这可以帮助. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |