Calculating distance with Scala’s foldLeft

I wanted a way to calculate the total distance of a GPS track. A track is basically just a list of lat,long pairs – represented in Scala by the following:

Seq[(Double, Double)]

One way to do this would be to iterate over the sequence, calculating the distance between points (using the haversine formula) and updating the sum in a variable but since this is Scala we can do it in a more functional way.

According to the Scaladoc, foldLeft “Applies a binary operator to a start value and all elements of this list, going left to right.” The signature looks like this for List[A] (a List of type A):

def foldLeft[B](z: B)(f: (B, A) ⇒ B): B

The first parameter z is of type B, so it can be different from the list type. The second parameter is a function that takes a B and an A (one of the list items) and produces a B.

The neat bit is this function iterates over the list and passes in each item to function f as the value of A. For the first item, z is passed in to f as the value of B. For each subsequent item the result of the previous call to f is used.

The usual example you will find is to sum a list of integers or something similar, like this:

list.foldLeft(0)((b, a) => b+a)

This will return the sum of all the items items in a list.

My use-case was slightly different. My list consisted of tuples and I needed to apply a function to each pair of tuples in the list and accumulate the sum of those results. This meant I needed to keep track of both the current element and the previous one during the folding.

It was Matt Malone’s page of lots and lots of foldLeft examples that put me on the right track, specifically his example for Average which showed how to use a tuple as an accumulator. Here’s how I did it:

As I said, points is just a sequence of lat,long pairs, eg:

val points = List((51.168437004089355, -0.648922920227051), (51.16805076599121, -0.64918041229248), (51.16757869720459, -0.64995288848877))

We first split the list into head and tail and use head and 0.0 as initial values. The folding function then produces a Tuple2[(Double, Double), Double]. The first item of the resultant tuple is the current list element and the second item is the sum of the current total and the result of the haversineDistance function (which itself takes as input the previous element and the current element).

points match {
  case head :: tail => tail.foldLeft(head, 0.0)((accum, elem) => (elem, accum._2 + haversineDistance(accum._1, elem)))._2
  case Nil => 0.0
}

The pattern matching is used to handle the case of an empty list.

Phew! This one line took me a while to figure out but it packs a lot of work into just a single line of code and shows how powerful Scala can be. Experimenting with the REPL was invaluable here.

For completeness, here’s the haversine function which calculates the distance between two points on the Earth (3958.761 is the mean radius of the Earth in miles):

def haversineDistance(pointA: (Double, Double), pointB: (Double, Double)): Double = {
  val deltaLat = math.toRadians(pointB._1 - pointA._1)
  val deltaLong = math.toRadians(pointB._2 - pointA._2)
  val a = math.pow(math.sin(deltaLat / 2), 2) + math.cos(math.toRadians(pointA._1)) * math.cos(math.toRadians(pointB._1)) * math.pow(math.sin(deltaLong / 2), 2)
  val greatCircleDistance = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
  3958.761 * greatCircleDistance
}