returns 另一个函数的 scala 递归函数

Question

我正在查看 scala 中的柯里化技术示例，但不明白当一个函数是递归时，一个函数如何 return 另一个函数。

例如我理解这段代码

def addOne(x: Int): Int = x => x + 1
def repeater(myFunc: Int => Int, n: Int, x:Int): Int = 
    if(n<=0) x
    else repeater(myFunc, n-1, myFunc(x))

上面一个对我来说没问题，如果我说 repeater(addOne, 10, 1) returns 11。直到 n 等于 0，我将 n 减 1，递归堆栈开始工作到底部向上。

但是这个让我很困惑

def repeater(myFunc: Int => Int, n:Int): Int => Int = {
   if(n<=0) (x:Int) => x
   else (x: Int) => repeater(myFunc, n-1)(myFunc(x))
}

这里我不明白的一点，例如，如果我运行 repeater(addOne, 2) 它会看 else 部分和 else 部分说到 return 一个函数，所以程序 return 首先是一个函数，或者用 n-1 (1-1) 和 return 另一个函数再执行一次中继器？这 else 部分 return 有多少个函数，调用堆栈是什么样的？

Answer 1

让我们逐步展开递归。

repeater(addOne, 2) returns 新的匿名函数

(x:Int) => repeater(addOne, 1).apply(addOne(x))

其中repeater(addOne, 1)returns新建匿名函数

(x:Int) => repeater(addOne, 0).apply(addOne(x))

其中 repeater(addOne, 0) returns 新建匿名函数

(x:Int) => x

因此 repeater(addOne, 1) returns 一个看起来像

的匿名函数

(y:Int) => {
    ((x: Int) => {
        x
    }).apply(addOne(y))
}

和 repeater(addOne, 2) returns 一个匿名函数，看起来像

(z:Int) => {
    ((y: Int) => {
        ((x: Int) => {
            x
        }).apply(addOne(y))
    }).apply(addOne(z))
}

Answer 2

为了使其更易于理解，我将简化您函数的某些部分并对其进行脱糖处理。

让我们首先删除 myFunc 参数并将其替换为 addOne 函数，直接降低复杂性，同时关注主要问题：

def repeater(n:Int): Int => Int = {
   if(n<=0) (x:Int) => x
   else (x: Int) => repeater(n-1)(addOne(x))
}

现在让我们对函数文字实例化代码进行脱糖

def repeater(n:Int): Int => Int = {
  if(n<=0) new Function1[Int,Int]{ //#1
    override def apply(x: Int): Int = x
  }
  else new Function1[Int,Int]{ //#2
    override def apply(x: Int): Int = repeater(n-1)(addOne(x))
  }
}

所以现在您可以看到，当您调用 reporter(2) 时，它会生成新函数 #2 而无需对其求值。所以结果你会得到这样的东西：

val repeaterFirstIteration: Int => Int = {
  new Function1[Int,Int]{
    override def apply(x: Int): Int = repeater(2-1)(addOne(x))
  }
}

或者让我们加糖回来

val repeaterFirstIteration: Int => Int = {
  x => repeater(2-1)(addOne(x))
}

所以现在你有 val 包含你可以像这样调用的函数文字 repeaterFirstIteration(...)

Answer 3

首先，让我们澄清一下，如果您运行 repeater(addOne, 3)，您只会取回一个函数。您需要运行repeater(addOne, 3)(SomeOtherInteger) 来获取整数值和计算结果。递归在这里所做的就是构造一个函数。 repeater(addOne, 3) returns 是一个接受整数的函数，returns 是一个整数。以repeater(addOne, 3)为例，如果我们把递归的结果全写出来，就是这样

{ x => {x => { x => { x => x }(myFunc(x)) }(myFunc(x)) }(myFunc(x))) }

它可能看起来有点混乱，但让我们分解一下。

让我们关注最里面的部分 - { x => x }(myFunc(x))。这可以分为两部分，一个函数和一个函数的输入。该函数是 { x => x } 并且该函数的输入是 (myFunc(x)) 。在这种情况下，函数所做的只是 return 返回给用户的输入。因此，如果我们写 { x => x }(1)，我们将得到 1。所以我们可以用 myFunc(x) 替换整个 { x => x }(myFunc(x))。我们剩下的是

  { x => { x => { x => myFunc(x) }(myFunc(x)) }(myFunc(x)) }

让我们看看 { x => myFunc(x)}(myFunc(x)) 项。这里的函数部分是{ x => myFunc(x) }，这个函数部分的输入由(myFunc(x))给出。函数部分接受一个整数 x 并将 myFunc 应用于该整数。它本质上与直接将 myFunc 应用于该整数相同。在这种情况下，我们应用它的整数是输入 myFunc(x)，因此我们可以将 { x => myFunc(x) }(myFunc(x)) 重写为 myFunc(myFunc(x))。现在我们有

   { x => { x => myFunc(myFunc(x)) }(myFunc(x)) }

我们可以应用上一步中使用的相同逻辑来分解 { x => myFunc(myFunc(x)) }(myFunc(x)) 项。我们会得到 myFunc(myFunc(myFunc(x)))。如果你继续这个逻辑，你会看到 repeater 将继续合成 myFunc。对于每个n，它会增加一层myFunc。如果 n = 3

，结果将如下所示

   { x  => myFunc(myFunc(myFunc((x))) }

因此对于repeater(addOne, 3)，我们会得到

{ x => addOne(addOne(addOne(x))) }

而repeater(addOne, 5)是

{ x => addOne(addOne(addOne(addOne(addOne(x))))) }

所有 repeater 所做的只是构造此函数，然后 return 将其提供给用户。您可以使用 repeater 的 return 函数并放入一个名为 f

的 val

 val f = { x => addOne(addOne(addOne(x))) } //ie repeater(addOne, 3)

f 接受一个整数输入，然后 return 将该整数加 3。然后我们可以使用这个

得到我们想要的实际结果

 val someIntegerPlus3: Int = f(someInteger)

returns 另一个函数的 scala 递归函数

scala recursive function that returns another function

recursion

scala

currying

higher-order-functions