Rewriting Java in Scala & Making Code Lovely 4 – Example: Integration

It's time for a full example that shows off what we know so far.

For the example, we're going to implement something that does basic integration. This program will approximate the value of an integral using the rectangle method - a good explanation of this can be found here.

Background

Skip this if you already know what integration and the rectangle method are.

Put simply, integration is finding the area under the graph for a particular function. The article here has more details on this.

The rectangle method is a way of approximating this. The graph for the function is divided into sections. Each section then has a rectangle put in it. The height of the rectangle is the same as the value of the graph at the middle of the section:

Thick rectangles under a graph
This isn't perfect. All the places where the rectangles are too small or too big are errors in the approximation. These errors can be reduced by dividing the graph in to more sections:
Thin rectangles under a graph

For the purposes of this posting, that's all there is to it.

The Problem

Make a class that when given a function and a range will approximate the area under the graph. The class can be given the number of rectangles to use.

Java Version

We'll start off with a Java version of this and then rewrite it to Scala.

public class RectangleMethod {
  public double integrate(double start, double end, int steps) {
    final double stepSize = (end - start) / steps;
    double value = 0; // running total for the area
    for (int i = 0; i < steps; i++) {
      // Evaluate the function at the mid-point of the current section
      // The code below could be shorter - but it has been kept purposefully simple
      final double startX = start + stepSize * i;
      final double endX = start + stepSize * (i + 1);
      final double midX = (startX + endX) / 2;
      final double y = function(midX);
      // Add on the area of the rectangle for the current section: width * height
      value += stepSize * y;
    }
    return value;
  }

private double function(double x) {
    return 20 - Math.pow(x - 4, 2);
  }
}

The Java example above contains a hard-coded function: 20 - (x - 4) * (x - 4).

That's not quite the solution to the problem. We must be able to provide a function to this method so that we can do integrations for any function. We can do this by making the integrate method take an interface and then the caller must implement this interface for any function it wants to integrate:

public class RectangleMethod {
  public double integrate(Function function, double start, double end, int steps) {
    final double stepSize = (end - start) / steps;
    double value = 0;
    for (int i = 0; i < steps; i++) {
      final double startX = start + stepSize * i;
      final double endX = start + stepSize * (i + 1);
      final double midX = (startX + endX) / 2;
      final double y = function.y(midX); // Call the function passed in
      value += stepSize * y;
    }
    return value;
  }

// New interface for arbitrary functions public interface Function { public double y(double x); } }

I've commented the parts that have changed and removed the old comments.

This now lets us pass in any function we want:

double value = new RectangleMethod().integrate(new Function() {
  public double y(double x) {
    return 20 - Math.pow(x - 4, 2);
  }
}, 0, 1, 200);

This will approximate the integral of 20 - (x - 4) * (x - 4) between 0 and 1 with 200 sections. This requires a lot of work to define a function every time you want to integrate it.

Scala - Simple Version

Now lets take our Scala knowledge so far and convert the above code. We'll start with the simple Java version:

class RectangleMethod {
  def integrate(start : Double, end : Double, steps : Int) = {
    val stepSize = (end - start) / steps // width of each step
    var value = 0.0 // running total for the area
    for (i <- 0 until steps) {
      // Evaluate the function at the mid-point of the current section
      // The code below could be shorter - but it has been kept purposefully simple
      val startX = start + stepSize * i
      val endX = start + stepSize * (i + 1)
      val midX = (startX + endX) / 2
      val y = function(midX)
      // Add on the area of the rectangle for the current section: width * height
      value = value + stepSize * y
    }
    value // Scala doesn't need the return keyword here
  }

def function(x : Double) = {
    20 - Math.pow(x - 4, 2)
  }
}

For loops

I've slipped something new in to the example above, the for loop. In Scala there are many ways to write a for loop, this is one of them. The for loop above will iterate i over the values 0 to steps and exclude steps. E.g.

for (i <- 0 until 10) print(i)
Will print 0123456789. To make it include the final value change until to "to":

for (i <- 0 to 10) print(i)
Will print 012345678910.

There are more ways to define for loops and I'll come back to them in later posts.

Scala - Better Version

Now we use our knowledge of using functions as arguments to pass a function to the integrate method:

class RectangleMethod {
  def integrate(
      function : Double => Double, // Add the function argument on
      start : Double, end : Double, steps : Int) = {
    val stepSize = (end - start) / steps
    var value = 0.0
    for (i <- 0 until steps) {
      val startX = start + stepSize * i
      val endX = start + stepSize * (i + 1)
      val midX = (startX + endX) / 2
      val y = function(midX) // No need to change this!
      value = value + stepSize * y
    }
    value
  }
}

We've added a single argument to the integrate function. The argument is a function that takes a Double as a parameter and returns a Double. To use this new method:

new RectangleMethod().integrate(
  x => 20 - Math.pow(x - 4, 2), 
  0, 1, 200)

I hope that you'll agree that using this new version is much neater than the Java example.

Scala - Tiny Version

We can make the integrate method really compact and neat.

The first step is to merge the mid-point calculation:

val startX = start + stepSize * i
val endX = start + stepSize * (i + 1)
val midX = (startX + endX) / 2
// Becomes (by substitution and simplification)...
val midX = start + stepSize * i + stepSize * 0.5)

Then simply the calculation of y

val midX = start + stepSize * i + stepSize * 0.5)
val y = function(midX)
// Becomes...
val y = function(start + stepSize * i + stepSize * 0.5))

And finally, move y into the running total calculation:

value = value + stepSize * function(start + stepSize * i + stepSize * 0.5))

This leaves us with:

class RectangleMethod {
  def integrate(
      function : Double => Double, 
      start : Double, end : Double, steps : Int) = {
    val stepSize = (end - start) / steps
    var value = 0.0
    for (i <- 0 until steps) {
      value = value + stepSize * function(start + stepSize * i + stepSize * 0.5))
    }
    value
  }
}

Whenever you see this pattern in Scala you should be thinking about whether it can be turned in to a call to foldLeft. The things to look for are:

  • A collection to fold over - in this case (0 until steps) is actually a collection (I'll cover this more in later posts)
  • A running total - in this case value is a running total

Now we use foldLeft to make this more compact:

class RectangleMethod {
  // Add the function argument on
  def integrate(
      function : Double => Double, 
      start : Double, end : Double, steps : Int) = {
    val stepSize = (end - start) / steps
    (0 until steps).foldLeft(0.0)((runningTotal, i) =>
      runningTotal + stepSize * function(start + stepSize * i + stepSize * 0.5))
  }
}

And, that's it.

There are many other ways to rewrite this, and I would love for you to come up with your own and leave it here as a comment :)

Discussion

blog comments powered by Disqus

Colin Howe

I'm Colin. I like coding, ultimate frisbee and startups. I am VP of engineering at Conversocial