6

I have been studying scala for the past week or so and the ideologies associated with it and functional programming in general. As expected, the leap from imperative to functional programming is not as easy as I had hoped. For example, I converted a programming exercise that I did in Java into Scala. What I found was that it was near impossible for me to switch from mutable variables into the Scala style of immutable vals.

For the TL;DR people, my main question is, how does one decrease the var usage in a functional program? For the sake of a use case, I'll provide some sample code:

import scala.io._
object Bowling {
  def main(args: Array[String]): Unit = {
    val input = Source.fromFile("bowling.in").getLines
    for(testCase <- input) {
      val numberOfRows = augmentString(testCase).toInt
      var index = 0
      var a = 1
      var sum = 0
      while(index < numberOfRows) {
        sum += a
        a += 4
        index += 1
      }
      println(sum)
    }
  }
}

EDIT: I'm accepting Karl's answer because of its conciseness though I do really appreciate Ptharien's code example and Doval's explanation of functional concepts as a whole.

3 Answers 3

4

The general approach is instead of mutating a variable in a loop, put the values into collections and run a series of operations on those collections. Note that most of the time, functional algorithms don't need index variables. Look for mathematical relationships that allow you to factor those out. For example:

val sums = for(testCase <- input) yield {
  val numberOfRows = testCase.toInt
  val a = 1 until numberOfRows * 4 by 4
  a.sum
}
sums foreach println

Just because it's a series of operations on a collection doesn't mean you have to cram all the operations together one after another. Don't forget to break up lines, name intermediate results, and use named functions instead of lambdas where appropriate. The compiler essentially optimizes out numberOfRows and a, but putting them in there adds a lot of readability for humans.

Don't avoid for comprehensions just because of their superficial resemblance to mutated for loops. They are often the key to better readability.

Note I moved the println to outside the for comprehension. Isolating side effects like that can often make it easier to see a pure functional solution for the rest of the problem.

Also, as an aside, you don't need the augmentString. It is implicitly added for you.

1
  • 1
    Thanks for the augmentString tip. I only changed it because my IDE showed a warning. Commented May 10, 2014 at 19:16
7

There's a couple of insights that will ease your transition from imperative programming to functional programming:

  1. Mutation of some value x can be replaced with creating a modified copy of x. There are persistent versions of most data structures that can do this efficiently by copying only the parts of the structure that changed and sharing the rest.

  2. Loops can be replaced with recursive functions. On languages with tail call optimization, tail recursion won't blow the stack because the compiler can rewrite it as a loop under the hood.

  3. A function that depends on a free variable (i.e. a variable that's not a formal parameter of the function) can be converted into a function that takes the current value of that variable as an argument.

We can combine all 3 rules to rewrite imperative loops functionally. Desugar for loops into while loops, convert the loop body into a recursive function, convert iteration variables into function arguments. So this:

public void printFirst(int n) {
    for (int i = 0; i < 10; i++) {
        println(i);
    }
}

can be converted into this:

def recursionHelper(i : int, max : int) {
    if (i == max) {
        return;
    } else {
        print(i);
        // Instead of mutating i, create a new value
        recursionHelper(i + 1, max);
    }
}

def printFirst(n : int) {
    recursionHelper(0, n);
}

Such translations can be done pretty mechanically. The resulting code probably won't be idiomatic, since the imperative version of the code likely didn't make much use of high-order functions (functions that take other functions as arguments) and lambda expressions (a concise syntax for creating anonymous functions), but it's a good first step towards learning how to think functionally.

4

An immediate conversion of your sample code to "var-less", but still not all that functional, style would be the following:

import scala.io._
object Bowling {
  def main(args: Array[String]): Unit = {
    val input = Source.fromFile("bowling.in").getLines
    for(testCase <- input) {
      val numberOfRows = augmentString(testCase).toInt
      val (_, sum) = 1 to numberOfRows foldr ((1, 0)) { (_, v) => v match {
        case (a, sum) => (a + 4, sum + a)
      } }
      println(sum)
    }
  }
}

Making a more actually functional version would be a much farther-reaching transformation, and would probably depend on exactly what the point of the program is. I'll put this answer out there as is, and work on an edit that hopefully demonstrates this more complete refactoring.


EDIT: Here is how I would write this program more generally functionally (while still remaining within the confines of Scala's standard library):

import scala.io._
object Bowling extends App {
  Source.fromFile("bowling.in").getLines map { _.toInt } map { testCase =>
    1 to testCase foldr ((1, 0)) { (_, v) => v match {
      case (a, sum) => (a + 4, sum + a)
    } }
  } map { _._2 } foreach { println _ }
}

Don't worry about understanding how to do this all at once; it takes practice, and a week or two is nowhere near enough time to understand a completely different programming paradigm than you're used to. Expect to take several months before you feel like you actually understand the basics of functional programming, although you can certainly write Scala in the "Java minus semicolons" style in the interim. :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.