Upper-triangular loop idiom for Scala Lists

Question

From my background in imperative programming, I'm accustomed to doing

for (i = 0;  i < 1000000;  i++) {
    for (j = i + 1;  j < 1000000;  j++) {
        doSomething(array[i], array[j])
    }
}

to examine all unique pairs in a million element array. doSomething is some operation that yields trivial results on diagonal and symmetric or antisymmetric results off diagonal--- that's why I only want to work on the upper triangle. (There's a minor variant of this where the i == j case is interesting; that's easy to fix.)

I find myself oddly stuck trying to do this in Scala. I have a large List and want to do something to all the pairwise combinations, but

list.flatMap(x => list.map(y => doSomething(x, y))

includes all the redundant or trivial cases (a factor of two too much work) and

(0 until 1000000).flatMap({i =>
  (0 until 1000000).map({j =>
    doSomething(list(i), list(j))
  })
})

would be very wrong because Lists are not random access (a factor of N^2 too much work). I could convert my Lists to Arrays, but that feels like it misses the point. Lists are linked lists, so the j + 1 element from my imperative example is only a step away from the i I'm currently examining. I'm sure I could write an efficient upper-triangular loop over linked lists in C/Python/whatever.

I suppose I can just swallow the factor of two for now, but this is such a common situation to run into that it feels like there ought to be a nice solution to it.

Also, does this "upper-triangular loop" have a common name? I couldn't find a good search string for it.

Edit: Here's an example of a bad solution:

list.zipWithIndex.flatMap({case (x, i) =>
  list.zipWithIndex.map({case (y, j) =>
    if (j > i)
      doSomething(x, y)
    else
      Nil
  })
})

because it still visits the unwanted nodes.

Answer 1

You may want to look at the Vector data type, it allows for quick indexed based look up.

Also, there is a built in combinations method that will give you what it looks like you are looking for.

scala> (1 to 3).combinations(2).mkString(" ")
res1: String = Vector(1, 2) Vector(1, 3) Vector(2, 3)

Answer 2

You can use pattern matching and tail recursion in the following way:

@tailrec def walk[T](list: Seq[T]): Unit =
  list match {
    case head :: tail =>
      tail.foreach(doSomething(head, _))
      walk(tail)
    case Nil =>
  }