DATA-PARALLEL GEOMETRIC OPERATIONS ON LISTS

We describe data parallel list operations that exploit pair structure on lists and an algebra that relates them. Equations from the algebra are used as transformation rules, so that development is done in a cal culational way. We illustrate their use in applications such as FFTs a nd sorting, and show that optimal or near-optimal algorithms can resul t from a systematic calculational process. The operations have a natur al, direct implementation on hypercubes.