3

让我举例说明我的问题。这是在 Scala 中用尾递归编写的标准求幂算法：

def power(x: Double, y: Int): Double = {
  def sqr(z: Double): Double = z * z
  def loop(xx: Double, yy: Int): Double = 
    if (yy == 0) xx
    else if (yy % 2 == 0) sqr(loop(xx, yy / 2))
    else loop(xx * x, yy - 1)

  loop(1.0, y)
}

这里sqr方法用于产生loop' 结果的平方。这看起来不是一个好主意——为这样一个简单的操作定义一个特殊的函数。但是，我们不能只写loop(..) * loop(..)，因为它会使计算加倍。

我们也可以用函数val和不sqr函数来编写它：

def power(x: Double, y: Int): Double = {
  def loop(xx: Double, yy: Int): Double = 
    if (yy == 0) xx
    else if (yy % 2 == 0) { val s = loop(xx, yy / 2); s * s }
    else loop(xx * x, yy - 1)

  loop(1.0, y)
}

我不能说它看起来比变体更好sqr，因为它使用state variable. 第一种情况更实用，第二种方式对 Scala 更友好。

无论如何，我的问题是如何处理需要对函数结果进行后处理的情况？也许 Scala 有其他方法可以实现这一目标？

4

4 回答 4

6

你使用的法律是

x^(2n) = x^n * x^n

但这与

x^n * x^n = (x*x)^n

因此，为避免递归后平方，y 为偶数的情况下的值应该如下面的代码清单所示。

这样，就可以进行尾部调用。这是完整的代码（不知道 Scala，我希望我能通过类比得到正确的语法）：

def power(x: Double, y: Int): Double = {
    def loop(xx: Double, acc: Double, yy: Int): Double = 
      if (yy == 0) acc
      else if (yy % 2 == 0) loop(xx*xx, acc, yy / 2)
      else loop(xx, acc * xx, yy - 1)

    loop(x, 1.0, y)
}

这是一个类似 Haskell 的语言：

power2 x n = loop x 1 n 
    where 
        loop x a 0 = a 
        loop x a n = if odd n then loop x    (a*x) (n-1) 
                              else loop (x*x) a    (n `quot` 2)
于 2013-07-04T12:19:43.483 回答
5

您可以使用“前向管道”。我从这里得到了这个想法：在单线中缓存一个中间变量。

所以

val s = loop(xx, yy / 2); s * s

可以重写为

loop(xx, yy / 2) |> (s => s * s)

使用这样的隐式转换

implicit class PipedObject[A](value: A) {
  def |>[B](f: A => B): B = f(value)
}

正如 Petr 指出的那样：使用隐式值类

object PipedObjectContainer {
  implicit class PipedObject[A](val value: A) extends AnyVal {
    def |>[B](f: A => B): B = f(value)
  }
}

像这样使用

import PipedObjectContainer._
loop(xx, yy / 2) |> (s => s * s)

更好，因为它不需要临时实例（需要 Scala >= 2.10）。

于 2013-07-04T12:12:13.853 回答
2

在我的评论中，我指出您的实现不能优化尾调用，因为在 where 的情况下yy % 2 == 0，有一个不在尾位置的递归调用。因此，对于大输入，这可能会溢出堆栈。

一个通用的解决方案是蹦床你的函数，用可以映射到“后处理”的数据替换递归调用，例如sqr. 然后由解释器计算结果，解释器逐步处理返回值，将它们存储在堆上而不是堆栈上。

Scalaz 库提供了数据类型和解释器的实现。

import scalaz.Free.Trampoline, scalaz.Trampoline._

def sqr(z: Double): Double = z * z

def power(x: Double, y: Int): Double = {
  def loop(xx: Double, yy: Int): Trampoline[Double] =
    if (yy == 0)
      done(xx)
    else if (yy % 2 == 0)
      suspend(loop(xx, yy / 2)) map sqr
    else
      suspend(loop(xx * x, yy - 1))

  loop(1.0, y).run
}

但是，这样做会对性能造成相当大的影响。在这种特殊情况下，我会使用 Igno 的解决方案来完全避免调用sqr。但是，当您无法对算法进行此类优化时，上述技术可能会很有用。

于 2013-07-04T11:49:22.387 回答
0

在这种特殊情况下

  • 不需要实用功能
  • 不需要钝的管道/隐式

  • 最后只需要一个独立的递归调用 - 总是给出尾递归

    def power(x: Double, y: Int): Double = 
  if (y == 0) x
  else {
    val evenPower = y % 2 == 0
    power(if (evenPower) x * x else x, if (evenPower) y / 2 else y - 1)
  }
于 2013-11-21T23:56:55.197 回答