Levi's Blog

I’ve been messing around with Scala a lot recently and I think the language hits such a sweet spot. Scala is a multi-paradigm language which means if you want to use an exclusively procedural/imperative/functional style or a mix of the three then you can. As Martin Odersky (the creator of the language) mentions in his fantastic book Programming in Scala, Scala doesn’t force you to do anything, but it definitely encourages you to use a functional style where it makes sense. So, in this respect Scala is very welcoming to beginners; you can use it initially just to write more concise Java, but you are also lead to discover the beauty of functional programming.

Functional programming takes some getting used to when you’re coming from an imperative language like Java. You have to learn to think functionally. The essence of functional programming is the application of functions to some input which produces a well-defined output. Functional programming, therefore, in contrast to imperative programming, shuns changing state and mutating data. As such, whereas in imperative languages it is common to use iteration/loops to continuously update the value of some variable to solve a given problem, in functional programming there is only f(x) – the function applied to x always yields a particular, well-defined value. As a consequence, in functional programming, many problems can be solved using recursive approaches. Scala supports tail recursion which makes recursive solutions practicable (in Java, the lack of tail call optimization frequently results in a stack overflows).

I just wanted to share a small bit of code that I thought showcases a lot of the neat things about Scala (and other functional languages as well).

The problem is a simple one: for any number, calculate the sum of its digits. For example, the sum of the digits of 123 is 6, the sum of the digits of 375 = 15. It’s easy to see that this problem lends itself to a recursive solution, since the sum of the digits of the number 123 can be defined as the sum of 3 + the sum of the digits of 12. Here’s a solution in scala:

def sumOfDigits(n: Int) = {
  @annotation.tailrec
  def sumOfDigitsAcc(n: Int, acc: Int): Int = {
    n match {
      case 0 => n + acc
      case _ => sumOfDigitsAcc(n / 10, acc + (n % 10))
    }
  }
  sumOfDigitsAcc(n, 0)
}

view rawgistfile1.scalaThis Gist brought to you by GitHub.
The basis for the solution is the fact that when dealing with ints, n/10 will always drop the last digit of a number and n%10 will always yield the rightmost digit. So, for example 45/10 will give you 4 and 45%10 yields 5. In our solution, once we arrive at a single digit number, we can simply add that number to our accumulated value. The accumulated value is also needed in order to allow the scala compiler to optimize the tail call here. Why? Because a solution is only tail recursive if the final statement in the function is a call to the functional itself. Without the ability to pass the stored up sum into our nested function, we wouldn’t be able to do this and we wouldn’t have tail call optimization. The beauty of being able to have nested functions is that since we know our accumulator must start at 0, we can avoid leaking the fact that we use an accumulator into our public API. Instead, we simply require an Int to be passed and we then define the solution as our nested function. Another awesome thing is that Scala has an annotation @tailrec which will raise a compiler error if the function cannot be optimized into a loop.

There are a lot of points here, but I thought this small example was actually pretty informative. It demonstrates the use of recursion, the ability to have nested functions, the bonus @tailrec annotation and how nicely this all comes together in the language.

I’m pretty new to Scala and functional programming so if I’m wrong about something, I’d love feedback.

EDIT –

As Nicolas B. kindly pointed out in the comments, I had a mistake in the above code. for case 0, I was returned n + acc when there’s no need to add n since I’m going from n to 0. Nicolas also pointed out that I can clean things up a bit more by using default arguments. Scala lets you specify default values for function parameters. The argument for such a parameter can optionally be omitted from a function call, in which case the corresponding argument will be filled in with the default. For us, this means we don’t need to supply the initial value of our accumulator when we call sumOfDigitsAcc. Combining Nicolas’s two points results in the following:

def sumOfDigits(n: Int) = {
  @annotation.tailrec
  def sumOfDigitsAcc(n: Int, acc: Int = 0): Int = {
    n match {
      case 0 => acc
      case _ => sumOfDigitsAcc(n / 10, acc + (n % 10))
    }
  }
  sumOfDigitsAcc(n)
}