Allen Wang Allen Wang - 2 months ago 9
Scala Question

double for loop in scala with incrementing inner index

This is probably a basic question, but I'm trying to create a simple function to find the two closest pairs in a list. Since this operation involves comparing TWO elements in the list, I am not sure using a for loop works if it really is just sugar for map and flatmap. So far, I have the structure of the expression as this:

val points: List[(Double, Double)] = List((2.0,3.1),(3.5,2.3),(1.2,0.2),(6.4,2.4))
var minDistance = Double.PositiveInfinity
var closestPoints = ((Double.NaN, Double.NaN), (Double.NaN, Double.NaN))

for {
point1 <- points
point2 <- points if (point1 != point2)
if (distance(point1, point2) < minDistance): {
minDistance = distance(point1, point2)
closestPoints = (point1, point2)
}
} yield (I guess I don't want a yield here?)


Note that the
if (point1 != point2)
is not really what I want here, since I really want to compare distinct points in the list, even if they have the same value. Would this only be possible using something like

for {
index1 <- 0 until points.length
index2 <- 0 until index1
...


This still seems unsatisfactory because of the yield? I guess there is some foldleft implementation that works, but I also don't know how to iterate on smaller and smaller subsets in the inner loop. I find foldLeft to be confusing to reason about compared to a simple double loop.

Answer

You can achieve this using combinations and foldLeft:

points.combinations(2).foldLeft((Double.PositiveInfinity,
                               ((Double.NaN, Double.NaN), (Double.NaN, Double.NaN))))
                               ((acc, points) => {
  val List(firstPoint, secondPoint) = points
  val dist = distance(firstPoint, secondPoint)
  if (dist < acc._1) (dist, (firstPoint, secondPoint)) else acc
})
Comments