Scala - folding on values that result from object interaction

Question

In Scala I have a list of objects that represent points and contain x and y values. The list describes a path that goes through all these points sequentially. My question is how to use folding on that list in order to find the total length of the path? Or maybe there is even a better functional or Scala way to do this?

What I have came up with is this:

def distance = (0 /: wps)(Waypoint.distance(_, _)) 

but ofcourse this is totally wrong because distance returns Float, but accepts two Waypoint objects.

UPDATE:

Thanks for the proposed solutions! They are definitely interesting, but I think that this is too much functional for real-time calculations that may become heavy. So far I have came out with these lines:

val distances = for(i <- 0 until wps.size) yield wps(i).distanceTo(wps(i + 1))
val distance = (0f /: distances)(_ + _)

I feel this to be a fair imperative/functional mix that is both fast and also leaves the distances values between each waypoint for further possible references which is also a benifit in my case.

UPDATE 2: Actually, to determine, what is faster, I will have to do benchmarks of all the proposed solutions on all types of sequences.

Answer 1

This should work.

(wps, wps drop 1).zipped.map(Waypoint.distance).sum

Answer 2

Don't know if fold can be used here, but try this:

wps.sliding(2).map(segment => Waypoint.distance(segment(0), segment(1))).sum

wps.sliding(2) returns a list of all subsequent pairs. Or if you prefer pattern matching:

wps.sliding(2).collect{case start :: end :: Nil => Waypoint.distance(start, end)}.sum

BTW consider defining:

def distanceTo(to: Waypoint)

on Waypoint class directly, not on companion object as it looks more object-oriented and will allow you to write nice DSL-like code:

point1.distanceTo(point2)

or even:

point1 distanceTo point2

wps.sliding(2).collect{
  case start :: end :: Nil => start distanceTo end
}.sum

Answer 3

Your comment "too much functional for real-time calculations that may become heavy" makes this interesting. Benchmarking and profiling are critical, since you don't want to write a bunch of hard-to-maintain code for the sake of performance, only to find out that it's not a performance critical part of your application in the first place! Or, even worse, find out that your performance optimizations makes things worse for your specific workload.

The best performing implementation will depend on your specifics (How long are the paths? How many cores are on the system?) But I think blending imperative and functional approaches may give you the worst-of-both worlds. You could lose out on both readability and performance if you're not careful!

I would very slightly modify missingfaktor's answer to allow you to have performance gains from parallel collections. The fact that simply adding .par could give you a tremendous performance boost demonstrates the power of sticking with functional programming!

def distancePar(wps: collection.GenSeq[Waypoint]): Double = {
  val parwps = wps.par
  parwps.zip(parwps drop 1).map(Function.tupled(distance)).sum
}

My guess is that this would work best if you have several of cores to throw at the problem, and wps tends to be somewhat long. If you have few cores or short paths, then parallelism will probably hurt more than it helps.

The other extreme would be a fully imperative solution. Writing imperative implementations of individual, performance critical, functions is usually acceptable, so long as you avoid shared mutable state. But once you get used to FP, you'll find this sort of function more difficult to write and maintain. And it's also not easy to parallelize.

def distanceImp(wps: collection.GenSeq[Waypoint]): Double = {
  if (wps.size <= 1) {
    0.0
  } else {
    var r = 0.0
    var here = wps.head
    var remaining = wps.tail

    while (!remaining.isEmpty) {
      r += distance(here, remaining.head)
      here = remaining.head
      remaining = remaining.tail
    }
    r
  }
}

Finally, if you're looking for a middle ground between FP and imperative, you might try recursion. I haven't profiled it, but my guess is that this will be roughly equivalent to the imperative solution in terms of performance.

def distanceRec(wps: collection.GenSeq[Waypoint]): Double = {
  @annotation.tailrec
  def helper(acc: Double, here: Waypoint, remaining: collection.GenSeq[Waypoint]): Double =
    if (remaining.isEmpty)
      acc
    else
      helper(acc + distance(here, remaining.head), remaining.head, remaining.tail)

  if (wps.size <= 1)
    0.0
  else
    helper(0.0, wps.head, wps.tail)
}

Answer 4

If you are doing indexing of any kind you want to be using Vector, not List:

scala> def timed(op: => Unit) = { val start = System.nanoTime; op; (System.nanoTime - start) / 1e9 }
timed: (op: => Unit)Double

scala> val l = List.fill(100000)(1)
scala> val v = Vector.fill(100000)(1)


scala> timed { var t = 0; for (i <- 0 until l.length - 1) yield t += l(i) + l(i + 1) }
res2: Double = 16.252194583

scala> timed { var t = 0; for (i <- 0 until v.length - 1) yield t += v(i) + v(i + 1) }
res3: Double = 0.047047654

ListBuffer offers fast appends, it doesn't offer fast random access.