An example of a nested function in Scala

Photo by Landon Martin on Unsplash

In JavaScript, you can nest a function inside another function. Because JavaScript is such a haphazard hodgepodge of kludges, the topic of nested functions is so complicated that I better leave it to someone far more intelligent than I am to explain.

Thanks to Scala being a more coherently designed language that had functional characteristics from the beginning, nested functions in Scala are quite easy to understand.

Whatever the programming language, nested functions are generally used for recursion. Perhaps the factorial numbers are the most commonly used example for nested functions in Scala.

For this article, however, I’m going to give an example based on an example from Eloquent JavaScript by Marijn Haverbeke. It’s an example that’s more interesting, in my opinion.

Start from 1, then either add 5 or multiply by 3. Repeat one or the other or alternate in whatever pattern you want. Some numbers, like 13, can be reached in at least one way. Others, like 15, are unreachable.

Write a Scala function to find a solution for a given number; it doesn’t have to be the “best” solution, it simply has to be a solution, if it exists for that particular number.

I think the function should return a list of integers. For example, for 13, the result should probably be 1, 3, 8, 13 (start with 1, multiply by 3, then add 5 twice).

If more than one solution is possible, the function should return the first solution it finds, even if it’s not the best solution. But if no solution is possible, the result should be an empty list.

This is a good problem for recursion to solve. In broad strokes, the recursion goes something like this: start with 1, make branches for 6 and 3. If either of those is the target number, we’re done.

If they’re both greater than the target number, we’re also done. Otherwise, make branches for 11, 18, 8 and 9. Determine if we need to go on to the next level of branches or not.

As usual, I start with the tests:

  @Test def testFind153SolFor3(): Unit = {
    val expected = List(1, 3)
    val actual = IntegerCalculator.find153Sol(3)
    assertEquals(expected, actual)
  }
  @Test def testFind153SolForUnreachable(): Unit = {
    val expected = List()
    val actual = IntegerCalculator.find153Sol(15)
    assertEquals(expected, actual)
  }
  @Test def testFind153SolFor8(): Unit = {
    val expected = List(1, 3, 8)
    val actual = IntegerCalculator.find153Sol(8)
    assertEquals(expected, actual)
  }

To pass the first test, just have find153Sol() return List(1, 3). For the second test, have find153Sol() check if the parameter is a multiple of 5.

It is the third test that motivates us to actually implement the recursion. After various attempts, I came up with this:

  def find153Sol(n: Int): List[Int] = {
    def recur153(curr: Int, history: List[Int]): List[Int] = {
      if (curr == n) {
        history.drop(1) :+ n
      } else if (curr > n) {
        List()
      } else {
        val add5Branch = recur153(curr + 5, history :+ curr)
        if (add5Branch.nonEmpty) {
          add5Branch
        } else recur153(curr * 3, history :+ curr)
      }
    }
    recur153(1, List(1))
  }

I suppose we could have played the TDD game a bit longer. However, you probably want to limit the tests to numbers for which only a single solution is possible, unlike, say, 18 = (1 + 5) × 3 = 1 × 3 + 5 + 5 + 5, corresponding to the lists 1, 6, 18 and 1, 3, 8, 13, 18.

For refactoring, I think it would make more sense for the inner function to take only one parameter: the list up to that point. I leave this refactoring as an exercise for you.

Don’t put the private modifier on the inner function. Your IDE should tell you it’s not allowed there. And it’s not needed anyway. The inner function can call itself and it can be called from the outer function, but it can’t be called from anywhere else in the class, object or trait that contains it.

And that’s as it should be. If other functions in the class, object or trait needed to call it, you would move it out of nesting and mark it private.

I don’t know what the scope is for inner functions in JavaScript, though my experiments in the Firefox console suggest the scope is the same as that of the enclosing function.

And then there’s JavaScript hoisting, which certainly adds complexity to the question. It’s just not an issue in Scala: scopes work as you expect them to.

A footnote: nesting functions is also possible in Java. It can be done with inner classes or with lambdas. Either way it’s probably too complicated for any practical use.