How should Futhark expose irregular arrays to the programmer?

Futhark, a functional array programming language, recently introduced new features like flattening nonuniform data parallelism and recursive functions. However, a significant challenge in implementing these features is handling irregular arrays—multidimensional arrays where subarrays differ in size. These arrays, unlike regular arrays, pose a problem for the language's size type system, making them not well-typed.

Despite this, flattening can handle irregular arrays by encoding them as regular arrays, without the need for the rest of the compiler to understand them.

The issue lies in how to expose the power of irregular arrays in the source language without adding support for general irregular arrays. An example of code that requires irregular arrays is a recursive data-parallel quicksort written in NESL. The challenge is to implement a similar algorithm in Futhark while accommodating irregular arrays.

Futhark's solution involves introducing a new second-order array combinator called flatmap. This combinator semantically functions like map, except it allows the results returned by the mapped function to differ in size. The flatmap function concatenates the arrays returned by the function, handling irregular arrays efficiently.

The implementation of flatmap involves size types, where the function accepts two arrays of the same size and returns an array whose size is the sum of the sizes of the input arrays. This allows for parallel execution across input elements and within the mapped function. However, this approach has limitations, as it requires knowing the size of the result in advance.

To address these limitations, another extension to flatmap can be made, where the size of the array returned by the mapped function is existentially quantified. This change allows the function to return arrays of varying sizes, thus accommodating more complex algorithms like Quickhull. However, this approach can become impractical as it eliminates the ability to determine the size of the result in advance.

Finally, a further extension allows flatmap to return a uniform result for each input element, similar to a normal map. This final type provides the flexibility to express a wide range of algorithms, including those with varying result sizes. This extension is particularly useful for algorithms that do not require a uniform output size, such as Quickhull, allowing for more expressive and efficient code in Futhark.