Search code examples
scalarecursiontail-recursion

passing function calls in scala as arguments, does function evaluate first?


I was just playing around with a implementation of foldlLeft in Scala

def foldLeft[A,B] (as: List[A], z: B) (f: (B, A) => B): B = as match {
  case Nil => z
  case Cons(x, xs) => foldLeft(xs, f(z,x)) (f)
}

In this implementation, f(z,x) is in the recursive call given as parameter for z, but I was wondering how this actually works? When the recursive call happens, does foldLeft() receive the value of the execution of f(z,b) or does it receive the function call the way it is written, and then execute when needed?

Example: if we call foldLeft() with the following values

def foldLeft[A,B] ([1,2,3], 0) (f: (x, y) => x + y): B = as match {
  case Nil => z
  case Cons(x, xs) => foldLeft([2,3], f(0,1)) (f)
}

Will the next execution of foldLeft() like this, where z is equal to the value of f()?

def foldLeft[A,B] ([2,3], 1) (f: (x, y) => x + y): B = as match {
  case Nil => z
  case Cons(x, xs) => foldLeft([2,3], f(1,2)) (f)
}

or does it work like this, where foldLeft() receives the call itself?

def foldLeft[A,B] ([2,3], f(0,1)) (f: (x, y) => x + y): B = as match {
  case Nil => z
  case Cons(x, xs) => foldLeft([3], f(f(1,0),2)) (f)
}

The question is essentially about when the values that a tail recursive function are evaluated?


Solution

  • Scala, like almost every mainstream language, is a strict language with an eager evaluation strategy and pass-by-value argument passing semantics.

    This means that all arguments to a method or function call will be fully evaluated before being passed into the method or function.

    However, what I wrote is actually not quite true: that is only the default.

    There are two ways to deviate from the default:

    1. The lazy modifier makes a value, well, lazy.
    2. by-name parameters are passed by name, not by value.

    #1 is not applicable here. #2 needs to be explicitly declared in the parameter list, which is not the case here.

    Therefore, we can conclude that, yes, f(z, x) will be fully evaluated before the recursive call to foldLeft.