Upper-triangular loop idiom for Scala Lists

Upper-triangular loop idiom for Scala Lists

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.