Futhark, un lenguaje de programación funcional orientado a la computación paralela en GPU, tradicionalmente prohíbe los arrays irregulares (aquellos cuyos subarrays difieren en tamaño) por motivos de eficiencia de compilación. El blog oficial del proyecto explica cómo los autores proponen sortear esa restricción mediante un nuevo constructor de orden superior denominado flatmap, sin necesidad de añadir soporte general para arrays irregulares en el sistema de tipos.
Flatmap funciona como map, pero la función mapeada puede devolver un array de tamaño distinto en cada iteración; el resultado es la concatenación de todos esos arrays. Para preservar el sistema de tipos basado en tamaños (size types), la operación recibe un vector con los tamaños esperados de cada salida, de forma que el tamaño total del resultado queda determinado de antemano. El artículo recorre tres generalizaciones sucesivas: una versión básica válida para algoritmos donde el tamaño de la salida se conoce previamente (como quicksort), una variante con tamaño existencial acompañada de un vector de formas para algoritmos como Quickhull, y una última versión que también permite resultados uniformes en cada elemento de entrada.
Con esta extensión, los autores muestran implementaciones funcionales de quicksort y Quickhull, comparándolas con las versiones históricas en NESL. Concluyen que flatmap es una adición mínima al lenguaje —apenas una “extensión”—, con una semántica trivial pero suficiente para recuperar buena parte de la expresividad que aportan los arrays irregulares, manteniendo al mismo tiempo la capacidad del compilador de generar código GPU eficiente.