Modern parallel architectures offer high performance but are challenging to program correctly. Data parallel functional languages offer a solution to this problem, providing a high-level programming model to work with accelerators such as GPUs. Existing languages are designed primarily to work with dense arrays and matrices, limiting their usefulness in expressing irregular data structures, such as graphs and sparse matrices. These structures are fundamental for many application domains, such as sparse linear algebra.

This paper closes this gap by extending a data-parallel functional language with limited dependent types. Particular emphasis is given to the addition of dependent pairs to model entire sparse data structures as values within the language. The approach is demonstrated through three case studies: dense to sparse matrix conversion, sparse matrix-vector multiplication, and parallel breadth-first search.

The experimental results show that this approach outperforms the state-of-the-art implementations on GPUs. Compared to NVidia cuSparse implementation, our automatically generated code achieves an average speedup of 1.2$\times$ for dense to sparse matrix conversion and 1.3$\times$ for sparse matrix-vector multiplication.