Data Parallel Geometric Operations on Lists

We describe data parallel list operations that exploit pair structure on lists and an algebra that relates them. We illustrate their use in applications such as FFTs, sorting, and dynamic network design, and show that optimal algorithms can often be derived. The operations have a natural implementation on hypercubes and related topologies, and also a geometric implementation as dynamic networks. Equations from the algebra can be used a transformation rules, so that software or hardware development can be done in a calculational way