← Volver a los ejercicios

Generadores anidados: cuál varía más rápido

Dos generadores en la misma expresión for combinan cada valor del primero con todos los del segundo, y el segundo se agota entero cada vez. Eso decide en qué orden salen las parejas, y por eso invertir los generadores devuelve las mismas parejas en otra secuencia. Hay un caso en que no se pueden invertir: cuando el segundo generador usa el valor del primero. Lo que devuelve cada expresión salió de correrla con la versión de Scala del curso.

1. ¿En qué orden salen las parejas?

1val pares =
2 for {
3 x <- 1 to 3
4 y <- 1 to 2
5 } yield (x, y)

Las dos preguntas son sobre los extremos del resultado: con qué pareja abre y con cuál cierra.

2. La traza, pareja por pareja

La misma expresión repartida en líneas para poder señalar cuál se está evaluando. El contador de cada línea dice cuántas veces se evaluó, y ahí se ve la diferencia entre el generador de afuera y el de adentro.

paso 0 de 0
lo que lleva el resultado–
■ línea 3: el generador de afuera le da un valor a x ■ línea 4: el generador de adentro le da un valor a y ■ línea 5: el yield arma la pareja

La columna x se repite dos veces seguidas y la columna y alterna. Eso es lo que significa que el generador de la derecha varíe más rápido.

3. Los mismos dos generadores, invertidos

1val pares = for { x <- 1 to 3; y <- 1 to 2 } yield (x, y)
2val invertidas = for { y <- 1 to 2; x <- 1 to 3 } yield (x, y)

Ninguno de los dos generadores nombra al otro, así que los dos órdenes se pueden escribir. La pregunta es qué cambia.

4. Cuando el segundo generador usa el valor del primero

1val triangulo = for { i <- 1 to 3; j <- 1 to i } yield (i, j)

Escoja cuántas parejas trae triangulo antes de mirar las opciones.

5. Tres generadores

1val ternas = for { a <- 1 to 2; b <- 1 to 2; c <- 1 to 2 } yield (a, b, c)

6. Lo que se lleva de aquí

En generadores anidados, el de la derecha es el que varía más rápido. La traza lo deja en los contadores: la línea de x se evalúa una vez por cada valor del generador de afuera, y la del yield una vez por cada pareja. Por eso for { x <- 1 to 3; y <- 1 to 2 } yield (x, y) devuelve Vector((1,1), (1,2), (2,1), (2,2), (3,1), (3,2)), agrupado por x.

Invertir dos generadores independientes no cambia qué parejas hay, solo en qué orden salen. for { y <- 1 to 2; x <- 1 to 3 } yield (x, y) devuelve Vector((1,1), (2,1), (3,1), (1,2), (2,2), (3,2)), y las dos comparaciones lo dicen: los vectores comparados con == dan false y sus toSet dan true. De ahí que el orden importe cuando el resultado es una secuencia y deje de importar en cuanto se pasa a un conjunto.

Un generador puede usar los nombres que traen los de arriba, y eso es lo que recorta el recorrido. Con j <- 1 to i el resultado es Vector((1,1), (2,1), (2,2), (3,1), (3,2), (3,3)), seis parejas con j menor o igual que i, mientras los dos generadores independientes de 1 to 3 dan nueve. Con j <- i to 3 sale el otro triángulo, Vector((1,1), (1,2), (1,3), (2,2), (2,3), (3,3)).

Ahí el orden deja de ser una preferencia. Los generadores se evalúan de arriba abajo, así que el que define i tiene que estar antes del que lo usa. Invertirlos no da otro resultado: da un programa que no compila.

1val v = for { j <- 1 to i; i <- 1 to 3 } yield (i, j)
./Invertido.scala:3:29
not found: value i
    val v = for { j <- 1 to i; i <- 1 to 3 } yield (i, j)
                            ^

Con tres generadores la regla es la misma y se ve mejor: el de la derecha cambia en cada terna, el del medio cuando el de la derecha se agota y el de la izquierda cuando se agotan los otros dos. for { a <- 1 to 2; b <- 1 to 2; c <- 1 to 2 } yield (a, b, c) devuelve ocho ternas, Vector((1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)), que es el producto de los tres recorridos y no su suma.