2

我在工作表中运行以下 Scala 代码：

package src.com.sudipta.week2.coursera
import scala.math.abs
import scala.annotation.tailrec

object FixedPoint {
  println("Welcome to the Scala worksheet")       //> Welcome to the Scala worksheet

  val tolerance = 0.0001                          //> tolerance  : Double = 1.0E-4
  def isCloseEnough(x: Double, y: Double): Boolean = {
    abs((x - y) / x) / x < tolerance
  }                                               //> isCloseEnough: (x: Double, y: Double)Boolean
  def fixedPoint(f: Double => Double)(firstGuess: Double): Double = {
    @tailrec
    def iterate(guess: Double): Double = {
      val next = f(guess)
      if (isCloseEnough(guess, next)) next
      else iterate(next)
    }
    iterate(firstGuess)
  }                                               //> fixedPoint: (f: Double => Double)(firstGuess: Double)Double

  def myFixedPoint = fixedPoint(x => 1 + x / 2)(1)//> myFixedPoint: => Double
  myFixedPoint                                    //> res0: Double = 1.999755859375

  def squareRoot(x: Double) = fixedPoint(y => (y + x / y) / 2)(1)
                                                  //> squareRoot: (x: Double)Double
  squareRoot(2)                                   //> res1: Double = 1.4142135623746899

  def calculateAverate(f: Double => Double)(x: Double) = (x + f(x)) / 2
                                                  //> calculateAverate: (f: Double => Double)(x: Double)Double
  def myNewSquareRoot(x: Double): Double = fixedPoint(calculateAverate(y => x / y))(1)
                                                  //> myNewSquareRoot: (x: Double)Double
  myNewSquareRoot(2)                              //> res2: Double = 1.4142135623746899
}

让我感到困惑的是：

  • 下面显示了我的 fixedPoint 函数的 Scala 工作表

fixedPoint: (f: Double => Double)(firstGuess: Double)Double

这是什么？这是函数类型/函数定义还是我错过了这个术语？基本上我怎么能用英语解释这个功能？

  • 下面显示了我的 calculateAverate 函数的 Scala 工作表

calculateAverate: (f: Double => Double)(x: Double)Double

但在我看来，我的函数的返回类型是 Double，但我期待 Double => Double。原因是我打算将它与期望 Double => Double 的 fixedPoint 一起使用，如下所示：

def myNewSquareRoot(x: Double): Double = fixedPoint(calculateAverate(y => x / y))(1)

请帮助我更清楚地理解高阶函数/柯里化。提前致谢。

4

2 回答 2

4 
fixedPoint: (f: Double => Double)(firstGuess: Double)Double

这里的任务是找到函数的不动点，该任务的应用将是我们众所周知的牛顿法平方根

牛顿法的平方根：

Calculates the square root of parameter x

def sqrt(x: Double): Double = ...

实现这一点的经典方法是使用牛顿法进行逐次逼近。

计算 sqrt(x)：

  1. 从初始估计 y 开始（让我们选择 y = 1）。
  2. 通过取 y 和 x/y 的平均值来反复改进估计。

例子： x=2

  Estimation               Quotient                    Mean
    1                       2/1=2                       1.5
   1.5                      2/1.5=1.333                1.4167
  1.4167                    2/1.4167=1.4118            1.4142
  1.4142 so on

首先，定义一个计算一个迭代步骤的函数

def sqrtIter(guess: Double, x: Double): Double =
if (isGoodEnough(guess, x)) guess
else sqrtIter(improve(guess, x), x)

其次，定义一个函数改进来改进估计和一个测试来检查终止：

def improve(guess: Double, x: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double, x: Double) =
abs(guess * guess - x) < 0.001

三、定义 sqrt 函数：

def sqrt(x: Double) = srqtIter(1.0, x)

使用您的定点函数，我们还计算数字的平方根

先看看什么是定点：

Anumber x称为函数 f 的不动点，如果f(x) = x

对于某些函数 f，我们可以通过从初始估计开始，然后以重复的方式应用 f 来定位固定点。

x, f(x), f(f(x))

这导致了以下用于查找固定点的函数：

val tolerance = 0.0001
def isCloseEnough(x: Double, y: Double) =
abs((x - y) / x) / x < tolerance
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
}

在这个公式中，fixedPoint是一个返回另一个函数的函数，即专用函数iterate

这里fixedPoint

def fixedPoint(f: Double => Double)(firstGuess: Double)

该函数fixedPoint应用于该函数f: Double => Double。然后将结果函数应用于第二个参数

(firstGuess: Double)

这种表示法是可能的，因为函数应用程序关联到左侧。也就是说，如果 args1 和 args2 是参数列表，则f(args1)(args2)等价于(f(args1))args2

在您的程序中，第一个参数是输入类型为 Double 且返回类型为 Double 的函数，然后将此函数应用于猜测

平方根函数的重新表述。

让我们从 sqrt 的规范开始：

sqrt(x) = the y such that y*y = x
        = the y such that y = x / y

因此，sqrt(x) 是函数 的不动点y => x / y。这表明

sqrt(x)

可以通过定点迭代计算：

def sqrt(x: double) = fixedPoint(y => x / y)(1.0)

这是一个很长的答案，但我认为它会帮助您理解这个概念

于 2013-11-06T09:16:50.620 回答
2

功能

def fixedPoint (f: Double => Double)(firstGuess: Double):Double

是一个接受两个参数的函数定义：

  1. 一个函数“f”，它接受一个类型的参数，该参数Double返回 aDouble和
  2. 一个Double名为“firstGuess”的值

并返回一个Double. 将单个参数分离到它们自己的括号组中允许该函数用于柯里化：

def mySqrtCalc(x:Double)(firstGuess:Double):Double = {...}

val mySqrtFunc = mySqrtCalc(2.0) _

val v = mySqrtFunc(1) // parameter firstGuess is set to 1

除了柯里化的能力，这相当于未柯里化的版本

def fixedPoint (f: Double => Double,firstGuess: Double):Double

您可能看起来更熟悉。

的结果calculateAverate是 Double 因为您将传递的函数 f 应用于 x 与 x 的结果相加，这给了您 aDouble因为 f 是一个 function Double => Double。

您calculateAverate在方法体中以柯里化的方式使用方法，myNewSquareRoot方法是只给出两个参数中的第一个参数并省略第二个参数，第二个参数取自外部fixedPoint方法。省略 of 的第二个参数会calculateAverate为您提供方法Double=>Double所需的fixedPoint方法。

您可能会插入一些println(s"<methodname> value=$value")以观察执行流程并了解方法调用顺序。

于 2013-11-06T12:50:26.460 回答