GHC, el compilador de Haskell, incluye una extensión llamada ApplicativeDo que traduce bloques do-notation en operaciones aplicativas (<*>) cuando no existen dependencias entre instrucciones, habilitando paralelismo automático. Sin embargo, el algoritmo que produce la planificación óptima de esas operaciones tiene complejidad O(n³): para bloques de 1.000 instrucciones puede tardar 55 segundos, frente a los menos de 2 segundos del algoritmo voraz por defecto. Por ello, la planificación óptima permanece oculta tras un flag raramente activado.
Ian Duncan, autor del artículo, investigó cómo reducir ese coste. Su análisis parte de un modelo de árbol (Seq/Par) sobre las instrucciones y de una función de coste basada en el número de rondas de E/S o cómputo necesarias. El problema se reduce a una recurrencia sobre tramos de instrucciones (de i a j) cuya última línea es responsable de la complejidad cúbica, al probar todos los puntos de corte posibles en cada subtramo con dependencias cruzadas.
El texto detalla un atajo clave de la literatura previa: en un bloque enmarañado basta comprobar dos cortes extremos, despegar la primera o la última instrucción, porque la función de coste es monótona creciente y cualquier corte intermedio suma dos sub-bloques mayores sin mejorar el resultado. Solo ante empate entre los dos extremos se requiere una búsqueda más profunda, lo que reduce el trabajo a O(1) en la mayoría de los casos.
Duncan describe además dos heurísticas fallidas: medir la cadena de dependencias más larga, que no captura el coste real cuando una flecha cruza otras, y un escaneo monótono izquierda-derecha que pierde información sobre dependencias que salen de la ventana analizada. La analogía con el plegamiento de ARN surge al comparar la recurrencia del layout óptimo con la programación dinámica de Nussinov, usada por biólogos para predecir la estructura secundaria de cadenas de ARN. El objetivo declarado es alcanzar la respuesta óptima sin pagar el coste cúbico original, aunque el artículo queda cortado antes de presentar la solución final.