Sequence: evaluación perezosa y cuándo gana de verdad

Hay un detalle en la biblioteca estándar que parece un error de diseño hasta que se entiende, y es el mejor punto de entrada a esta lección: la interfaz Sequence<out T> declara exactamente lo mismo que Iterable<out T>, un único método que devuelve un iterador, sin añadir ni quitar nada. Dos tipos con la misma forma y con comportamientos radicalmente distintos, porque la diferencia no vive en la declaración sino en qué conjunto de funciones de extensión resuelve el compilador cuando escribes map sobre una o sobre la otra. Ese desdoblamiento deliberado es la manera que tiene Kotlin de ofrecer dos estrategias de evaluación con la misma sintaxis: sobre Iterable cada operador construye una colección completa, y sobre Sequence cada operador construye una descripción de trabajo pendiente que no ejecuta nada hasta que alguien pide el resultado. Cambiar de estrategia cuesta una llamada, y decidir cuándo hacerlo cuesta bastante más criterio del que sugiere la fama de la palabra perezoso.

Por etapas o por elemento: lo único que cambia

Una cadena sobre una lista se ejecuta por etapas: el primer operador procesa los mil elementos y produce mil resultados, el segundo procesa esos mil y produce los que pasen el filtro, y así sucesivamente. Una cadena sobre una secuencia se ejecuta por elemento: el primer valor atraviesa todos los pasos hasta el final, después el segundo, y ninguna estructura intermedia llega a existir. La forma más honesta de verlo es imprimir desde dentro de las lambdas.

listOf(1, 2, 3)
    .map { println("map $it"); it * 2 }
    .filter { println("filter $it"); it > 2 }
    .first()
// map 1, map 2, map 3, filter 2, filter 4, filter 6

listOf(1, 2, 3).asSequence()
    .map { println("map $it"); it * 2 }
    .filter { println("filter $it"); it > 2 }
    .first()
// map 1, filter 2, map 2, filter 4  -> y para

En la segunda traza hay dos hechos independientes que conviene no confundir, porque a menudo se atribuye a la pereza un solo beneficio cuando en realidad ofrece dos. El primero es que no se construyó ninguna lista intermedia, lo que ahorra memoria proporcional al tamaño de la entrada. El segundo es que el tercer elemento no se procesó en absoluto, lo que ahorra trabajo. El primer ahorro es siempre real; el segundo solo aparece si el terminal puede detenerse antes de agotar la fuente.

flowchart TD
A[Cadena ansiosa sobre lista] --> B[map recorre todo y crea lista]
B --> C[filter recorre todo y crea lista]
C --> D[first toma el primero y tira el resto]
E[Cadena perezosa sobre secuencia] --> F[Elemento uno pasa por map y filter]
F --> G[Elemento dos pasa por map y filter]
G --> H[first ya tiene resultado y detiene la fuente]

Intermedias, terminales y las que guardan estado

La clasificación primaria es sencilla: una operación intermedia devuelve otra Sequence<T> y no ejecuta nada; una operación terminal devuelve cualquier otra cosa y es la que dispara todo el trabajo. Son intermedias map, filter, take, drop, flatMap, onEach, mapNotNull, zip, plus y withIndex. Son terminales toList, first, firstOrNull, find, count, sum, fold, reduce, any, all, none, forEach, joinToString, maxOrNull, groupBy y associate.

val descripcion = numeros.asSequence()
    .map { it * 2 }        // intermedia: no se ejecuta nada
    .filter { it > 10 }    // intermedia: sigue sin ejecutarse nada

val resultado = descripcion.toList()   // terminal: aqui ocurre todo

La clasificación secundaria es la que produce sorpresas. Entre las intermedias hay algunas que no pueden emitir un elemento sin haber visto los demás, y esas rompen el flujo continuo aunque su firma parezca idéntica. sorted y sortedBy acumulan la secuencia entera en una lista, la ordenan y solo después empiezan a emitir; distinct mantiene un conjunto con todo lo ya visto; chunked y windowed retienen un búfer. Colocar un sorted en medio de una cadena perezosa anula la principal ventaja de memoria y hace imposible el cortocircuito de todo lo que esté antes.

// Sin estado: memoria constante aunque la fuente sea enorme
registros.asSequence().map(::parsear).filter { it.grave }.take(10)

// Con estado: sorted materializa la fuente entera antes de emitir el primero
registros.asSequence().map(::parsear).sortedBy { it.fecha }.take(10)

Hay un tercer eje de clasificación que se descubre normalmente por accidente: si la secuencia se puede recorrer más de una vez. Una secuencia obtenida con asSequence sobre una lista es reiterable, porque cada recorrido pide un iterador nuevo a la lista de origen; una construida sobre un iterador o sobre un recurso de entrada y salida se agota, y volver a consumirla lanza un error. La función constrainOnce marca explícitamente una secuencia como de un solo uso, que es la forma correcta de convertir un fallo tardío y confuso en un mensaje claro en el segundo intento.

val reiterable = listOf(1, 2, 3).asSequence()
reiterable.toList()      // funciona
reiterable.toList()      // vuelve a funcionar: pide un iterador nuevo

val unaVez = origen.iterator().asSequence().constrainOnce()
unaVez.toList()          // funciona
unaVez.toList()          // lanza: la secuencia ya se consumio

La consecuencia de diseño es que devolver un Sequence<T> desde una función pública es una decisión más comprometida de lo que parece, porque el tipo por sí solo no informa a quien lo recibe de si puede recorrerlo dos veces ni de si conserva abierto un recurso. Cuando cualquiera de esas dos cosas es cierta, la firma debe documentarlo o, mejor, el consumo debe quedar dentro del alcance de la función que gestiona el recurso.

El cortocircuito y las fuentes sin final

El cortocircuito es la consecuencia observable de que el terminal controle cuántos elementos pide. first, find, any, none, indexOfFirst y take dejan de tirar de la fuente en cuanto tienen la respuesta, de modo que el trabajo realizado es proporcional a la posición del primer acierto y no al tamaño de la entrada. Sobre una lista de un millón de elementos cuyo primer resultado válido está en la posición diez, la versión ansiosa hace un millón de transformaciones y la perezosa hace diez.

Esa misma propiedad es la que permite algo que la evaluación ansiosa no puede expresar en absoluto: trabajar con fuentes que no tienen final o cuyo tamaño se desconoce hasta agotarlas.

val potencias = generateSequence(1L) { it * 2 }          // infinita
val primeras = potencias.take(20).toList()

val fibonacci = generateSequence(0L to 1L) { (a, b) -> b to (a + b) }
    .map { it.first }

fun contarErrores(ruta: Path): Int = ruta.toFile().useLines { lineas ->
    lineas.filter { "ERROR" in it }.count()   // el fichero no cabe en memoria
}

Las dos primeras son secuencias infinitas y la tercera es una secuencia sobre un recurso que se lee bajo demanda; ninguna de las tres tiene traducción posible al estilo ansioso, porque toList sobre una fuente infinita no termina y leer un fichero de veinte gigabytes en una lista no cabe. Aquí la pereza no es una optimización sino una capacidad expresiva: hay cómputos que sencillamente no se pueden escribir de la otra manera.

Medir en vez de creer

La creencia de que una secuencia es más rápida que una lista es falsa en la mayor parte del código real, y conviene saber exactamente por qué. Los operadores sobre Iterable están marcados inline, así que la lambda desaparece y el bucle resultante es prácticamente el que habrías escrito a mano. Los operadores sobre Sequence no pueden ser inline porque la lambda tiene que sobrevivir hasta que alguien consuma el resultado: cada paso asigna un objeto, guarda la lambda como una instancia de FunctionN y añade una llamada virtual a hasNext y otra a next por elemento y por etapa. Sobre entradas pequeñas, ese sobrecoste por elemento supera con holgura el ahorro de no construir listas.

// Casi siempre mas rapido: la entrada es pequena y todo se procesa
val a = usuarios.filter { it.activo }.map { it.nombre }

// Casi siempre mas rapido: entrada grande y el terminal cortocircuita
val b = registros.asSequence().map(::parsear).first { it.esValido }

La única manera honesta de decidir un caso dudoso es medirlo con una herramienta que sepa lo que hace la máquina virtual. Un cronómetro alrededor de un bucle produce números sin sentido porque no distingue la fase interpretada de la compilada, porque el compilador de tiempo de ejecución puede eliminar por completo un cómputo cuyo resultado no se usa, y porque la primera ejecución paga la carga de clases. Un banco de pruebas con calentamiento previo, varias iteraciones y consumo explícito del resultado da números comparables; cualquier otra cosa mide el ruido.

Mientras llega esa medición, la heurística que sobrevive a la mayoría de los casos se puede enunciar en una frase con tres condiciones: convierte a secuencia cuando la entrada sea grande, cuando la cadena tenga al menos tres etapas y cuando el terminal pueda detenerse antes de agotarla. Si falla cualquiera de las tres, y en el código de aplicación típico fallan casi siempre las tres a la vez, la lista es la elección correcta y además la más legible. La consecuencia práctica es que las secuencias son una herramienta de propósito específico y no un estilo por defecto; sembrar el código de conversiones porque suenan modernas es una pesimización silenciosa que además añade una llamada más que leer en cada cadena.