在Scala中将功能重复N次

Question

我想创建一个函数，该函数将返回一个函数，该函数是参数x上f的n倍的函数，即f（f（f ... f（x）...））。这是我的代码：

def repeated(f: Int => Int, n: Int) = {
   var tek: Int => Int = f

   for (i <- 0 to n) {
     tek = x => f(tek(x))
   }
   tek
}

我知道这不是在Scala中执行此操作的正确方法，我只想了解幕后发生的事情。

调用它repeated(x => x + 1, 5)(1)会导致堆栈溢出。
我在调试器中注意到的是，重复完成后将执行for循环内的行。似乎是惰性启动，也许for循环的主体是按名称传递的lambda？

Answer 1

在纯 FP 中：

def repeated[A](f: A => A, n: Int): A => A =
  (0 until n).foldLeft(identity[A] _)((ff, _) => ff.andThen(f))

（如果n=0-也有效identity）

或者，如果您不喜欢迭代 a Range（我认为它的性能不会比替代方案差多少），手动尾递归：

def repeated[A](f: A => A, n: Int): A => A = {
  @tailrec def aux(acc: A => A, n: Int): A => A = {
    if(n > 0) aux(acc.andThen(f), n - 1)
    else acc
  }

  aux(identity, n)
}

编辑：还有 Stream 版本，正如@Karl Bielefeldt 所提到的。性能应该差不多，但当然最好的选择方法是根据您的用例进行基准测试：

def repeated[A](f: A => A, n: Int): A => A =
  Stream.iterate(identity[A] _)(_.andThen(f)).apply(n)

编辑2：如果你有猫：

def repeated[A](f: A => A, n: Int): A => A =
  MonoidK[Endo].algebra[A].combineN(f, n)

Answer 2

您x => f(tek(x))正在关闭变量 tek。一旦内部for循环至少运行一次，您便tek成为自引用的，因为tek = x => f(tek(x))调用自身，这会导致无限递归和StackOverflowError。

如果要使用for-loop进行操作，则可以引入局部不可变的辅助变量来中断递归：

def repeated(f: Int => Int, n: Int) = {
   var tek: Int => Int = identity

   for (i <- 1 to n) {
     val g = tek
     tek = x => f(g(x))
   }
   tek
}

请注意，您f的代码中至少有两个应用程序过多：

1. 你不是从身份开始 n = 0
2. 您从迭代0到n，即(n + 1)次。

一个更简单的解决方案是：

def repeated[A](f: A => A, n: Int): A => A = { (a0: A) =>

  var res: A = a0
  for (i <- 1 to n) {
    res = f(res)
  }
  res
}