Idiom Upper Triangle for Scala Lists

Question

From my experience in imperative programming, I'm used to doing

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

to explore all the unique pairs in the millionth array of elements. doSomething is some kind of operation that gives trivial results on diagonal and symmetric or antisymmetric diagonal results --- that is why I want to work only on the upper triangle. (There is a small option where the case i == j interesting, which is easy to fix.)

I feel strangely stuck trying to do this in Scala. I have a large List and I want to do something for all pair combinations, but

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

includes all redundant or trivial cases (twice as much work) and

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

it would be very wrong, because lists are not random access (factor N ^ 2 works too much). I could convert my Lists to Arrays , but it seems like he doesn't understand the point. Lists are linked lists, so the j + 1 element from my imperative example is just the step from i that I am currently viewing. I'm sure I can write an effective upper triangular loop over linked lists in C / Python / whatever.

I believe that now I can simply learn the factor of two, but this is such a common situation in which you are faced with the fact that it seems that this should be a good solution.

Also, does this “upper triangular loop” have a common name? I could not find a good search bar.

Edit: Here is 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 }) }) 

as he is still visiting the unwanted nodes.

Answer 1

You can look at the Vector data type, which allows you to quickly find an indexed search.

In addition, there is a built-in combination 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 as follows:

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

Answer 3

About this part of the question:

Also, does this “upper triangular loop” have a common name? I could not find a good search bar.

The common name "triangle of the upper triangle" is a triangular matrix. (as described on wikipedia )

... a triangular matrix is ​​a special kind of square matrix. A square matrix is ​​called lower triangular if all elements above the main diagonal are equal to zero. Similarly, a square matrix is ​​called upper triangular if all entries below the main diagonal are equal to zero.