Data Parallel Haskell: Mixing old and new glue

John Hughes [10] argues that the ability to decompose a problem into parts, depends upon the ability to `glue' those parts together. A functional programming language such as Haskell [9] provides the user with two powerful kinds of glue: higher order functions and lazy evaluation. Although many data parallel extensions to functional languages exist--- Connection Machine Lisp [16], Paralation Lisp [15], Parallel EuLisp [13], and Tuple [21], they all lack the special glue of a lazy language. This paper describes two data parallel extensions to the lazy functional language Haskell: pods and pod comprehensions. These enable parallel algorithms to be expressed by decomposing a problem into smaller sequential parts, which are then glued together in parallel. We contrast an implementation of a text searching algorithm and an LL(1) parser [7], and show that the parallelism within both can be expressed in terms of the same higher order parallel map and scan functions. In the first example, we..