Scala 高阶函数有点困惑

Question

我在 Worksheet 中运行以下 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。原因是我将把它与 fixedPoint 一起使用，它需要 Double => Double 如下所示:

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

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

Answer 1

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

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

牛顿法平方根:

计算参数 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)

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

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)

使用您的 Fixedpoint 函数，我们还可以计算数字的平方根

先看看什么是不动点:

如果 f(x) = x

，数 x 称为函数 f 的不动点

对于某些函数 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

此处固定点

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)

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