Repeat a function N times in Scala

Question

I want to create a function that would return a function which is n-times composed function of f over parameter x, i.e. f(f(f ... f(x) ...)). Here is my code:

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

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

I know this is not right way to do this in Scala, I just want to find out what's happening behind the scenes.

Calling it like repeated(x => x + 1, 5)(1) would result in stack overflow.
What I have notice in debugger is that line inside for loop is executed after repeated is finished. It seems like lazy initiation, maybe body of for loop is a lambda passed by name?

Answer 1

In pure FP:

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

(also works if n=0 - becomes identity)

Or, if you don't like iterating over a Range (which I think wouldn't be much less performant than alternatives), manual tail recursion:

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)
}

EDIT: there's also the Stream version, as @Karl Bielefeldt mentioned. Should be about about as performant, but of course the best way to choose is to benchmark with your usecase:

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

EDIT 2: if you have Cats:

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

Answer 2

Your x => f(tek(x)) is closing over the variable tek. Once the inner for-loop runs at least once, your tek becomes self-referential, because tek = x => f(tek(x)) calls itself, which causes unbounded recursion and StackOverflowError.

If you wanted to do it with a for-loop, you could introduce a local immutable helper variable to break the recursion:

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
}

Note that you had at least two applications of f too much in your code:

1. You didn't start with identity for n = 0
2. You iterated from 0 to n, that is, (n + 1) times.

A much simpler solution would have been:

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
}