scala - 在 Scala 中重复一个函数 N 次

Question

我想创建一个函数，该函数将返回一个函数，该函数是 f 对参数 x 的 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 )

或者，如果您不喜欢迭代 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)