February 2017

Appeared at ICFP 2017

Parallel programming, whether imperative or functional, has long focused on arrays as the central data type. Meanwhile, typed functional programming has explored a variety of data types, including lists and various forms of trees.

Genericfunctional programming decomposes these data types into a small set of fundamental building blocks: sum, product, composition, and their associated identities. Definitions over these few fundamental type constructions then automatically assemble into algorithms for an infinite variety of data typesâ€”some familiar and some new. This paper presents generic functional formulations for two important and well-known classes of parallel algorithms: parallel scan (generalized prefix sum) and fast Fourier transform (FFT). Notably, arrays play no role in these formulations. Consequent benefits include a simpler and more compositional style, much use of common algebraic patterns and freedom from possibility of run-time indexing errors. The functional generic style also clearly reveals deep commonality among what otherwise appears to be quite different algorithms. Instantiating the generic formulations, two well-known algorithms for each of parallel scan and FFT naturally emerge, as well as two possibly new algorithms.

```
@Article{Elliott-2017-generic-parallel-functional,
author = {Conal Elliott},
title = {Generic functional parallel algorithms: Scan and {FFT}},
journal = {Proc. ACM Program. Lang.},
volume = {1},
number = {ICFP},
articleno = {48},
numpages = {24},
month = sep,
year = {2017},
url = {http://conal.net/papers/generic-parallel-functional},
doi = {http://dx.doi.org/10.1145/3110251},
}
```