← Volver a los ejercicios

La criba sobre un flujo que no termina

La criba de Eratóstenes toma el primer número de la secuencia, descarta sus múltiplos y repite el procedimiento con lo que queda. Sobre una lista eso obliga a fijar un tope: hay que decidir de antemano hasta dónde cribar. Sobre un LazyList no hace falta tope, porque la cola de cada paso queda descrita y sin calcular. Las ocho preguntas van de lo que devuelve cada llamada a la traza de los cuatro primeros pasos, con la cola que deja cada filtro, y los dos resultados del final salieron de correr el código con la versión de Scala del curso.

1. Qué devuelve cada llamada

2. La traza, un paso a la vez

La fila del paso aparece cuando se predice. El paso 0 es el flujo que llega a la primera llamada, enterosDesde(2).

3. Lo que devuelve el flujo

1primos.take(10).toList
2primos(20)

4. Por qué el proceso termina

1Cada llamada a criba devuelve dos cosas de naturaleza distinta: s.head, que es un número concreto, y una cola que es la llamada siguiente sin evaluar.
2El filtro no recorre nada al escribirse. s.tail.filter(...) deja la condición encima de la cola y la aplica cuando alguien pide un elemento.
3Los filtros se apilan: el de 2, el de 3, el de 5 y el de 7 siguen todos puestos en el cuarto paso, y cada número que llega los atraviesa en orden.
4El índice pedido decide cuánto se calcula. primos.take(10).toList devuelve List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29) y primos(20) devuelve 73, cada uno tras mirar solo los números que hicieron falta.

Que la recursión no tenga caso base y el flujo de partida no se agote son dos razones para esperar un cálculo sin fin, y ninguna lo produce. La pieza que lo explica es el #:: de s.head #:: criba(...): su lado izquierdo se evalúa, su lado derecho no. Cada paso entrega entonces un número y una descripción de lo que vendría después, y la cadena de llamadas se detiene ahí hasta que alguien pida el elemento siguiente.

De ahí sale la forma de contar el trabajo. Pedir el elemento del índice 20 obliga a abrir veintiún pasos de la criba, y cada paso solo mira los números que los pasos anteriores le dejaron pasar. Lo que no se pide no se filtra: sobre la cola del cuarto paso quedan cuatro condiciones puestas que no se han evaluado en ningún número todavía.

La comparación con una lista cierra el asunto. Cribar una lista obliga a declarar el tope antes de empezar, y con el tope viene la decisión de cuántos primos se quieren: si el tope queda corto hay que repetir el cálculo entero con otro. El flujo invierte el orden: la criba se escribe una vez, sin tope, y quien consulta fija cuánto se calcula.