List Processing in Parallel
Tom Axford, Mike S. Joy · Warwick Research Archive Portal (University of Warwick) · 1991
A new model of list processing is proposed which is well suited to parallel implementation. Its main primitive functions are: "concatenate", which concatenates two lists; "split", which partitions a list into two parts; and "length", which gives the number of elements in a list. In the commonly used CREW P-RAM model of parallel computation, common high-level operations on lists such as "map" and "reduce" take O(log n) time in the new model as against O(n) time in the conventional head-tail-cons model of list processing. Parallel simulation of a number of simple programs in the functional language FLIC, using the new model of lists, gives parallel execution times consistent with this analysis. The programs tried use the high-level functions "map, filter" and "reduce", together with an implementation of Hoare's "quicksort".