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.

David Holbrook · Accepted Answer · 2014-05-07 16:37:56Z

6

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)

edited May 7, 2014 at 16:37

answered Sep 9, 2013 at 21:31

David Holbrook

1,61714 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Jim Pivarski Over a year ago

Thank you! combinations is what I was looking for. I took a look at the Scala docs and the description is so brief that I'm not embarrassed I didn't find it before.

dividebyzero Over a year ago

This is pretty cool, but it only works because we are working with (1 to 3). What if I want the combinations from a list with repeated values? Should I use that to index? I wanted to iterate like this using generators...

David Holbrook Over a year ago

Vector(1,2,2,3).combinations(2).mkString(" ") will give you the expected results with duplicates.

Will Fitzgerald Over a year ago

If the expected results for Vector(1,1,1,1).combinations(2).toList is List(Vector(1, 1)), then ok. But not if you're expecting 6 items in that list.

Lev Khomich · Accepted Answer · 2013-09-09 21:31:31Z

5

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 =>
  }

answered Sep 9, 2013 at 21:31

Lev Khomich

2,24714 silver badges18 bronze badges

1 Comment

Jim Pivarski Over a year ago

Thanks! While this is really clever, I'd rather use a built-in functor. It may be how combinations is implemented internally.

Reinis · Accepted Answer · 2014-08-19 16:30:41Z

-1

About this part of the question:

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

The common name for "upper-triangular loop" is triangular matrix. (as described in wikipedia)

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

edited Aug 19, 2014 at 16:30

answered Jul 31, 2014 at 8:04

Reinis

659 bronze badges

Collectives™ on Stack Overflow

Upper-triangular loop idiom for Scala Lists

3 Answers 3

4 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related