Desde mi experiencia en programación imperativa, estoy acostumbrado a hacer

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

para examinar todos los pares únicos en una matriz de millones de elementos.doSomething es una operación que produce resultados triviales en diagonal y simétrica o antisimétrica fuera de la diagonal, por eso solo quiero trabajar en el triángulo superior. (Hay una variante menor de esto donde eli == j el caso es interesante; eso es fácil de arreglar)

Me encuentro extrañamente atascado tratando de hacer esto en Scala. Tengo un granList y quiero hacer algo a todas las combinaciones por pares, pero

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

incluye todos los casos redundantes o triviales (un factor de dos demasiado trabajo) y

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

sería muy incorrecto porque las listas no son de acceso aleatorio (un factor de N ^ 2 demasiado trabajo). Podría convertir miLists aArrays, pero eso se siente como si faltara el punto.Lists son listas enlazadas, por lo que laj + 1 El elemento de mi ejemplo imperativo está a solo un paso de lai Actualmente estoy examinando. Estoy seguro de que podría escribir un bucle triangular superior eficiente sobre las listas vinculadas en C / Python / lo que sea.

Supongo que puedo tragar el factor de dos por ahora, pero esta es una situación tan común que parece que debería haber una buena solución.

Además, ¿este "bucle triangular superior" tiene un nombre común? No pude encontrar una buena cadena de búsqueda para ello.

Editar: Aquí hay un ejemplo de una mala solución:

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

Porque todavía visita los nodos no deseados.