A Short Cut to Parallelization Theorems
The third list-homomorphism theorem states that if a function is both foldr and foldl, it has a divide-and-conquer parallel implementation as well. In this paper, we develop a theory for obtaining such parallelization theorems. The key is a new proof of the third list-homomorphism theorem based on shortcut deforestation. The proof implies that there exists a divide-and-conquer parallel program of the form of h (x 'merge' y) = h(1) x circle dot h(2) y, where h is the subject of parallelization, merge is the operation of integrating independent substructures, h1 and h2 are computations applied to substructures, possibly in parallel, and circle dot merges the results calculated for substructures, if (i) h can be specified by two certain forms of iterative programs, and (ii) merge can be implemented by a function of a certain polymorphic type. Therefore, when requirement (ii) is fulfilled, h has a divide-and-conquer implementation if h has two certain forms of implementations. We show that our approach is applicable to structure-consuming operations by catamorphisms (folds), structure-generating operations by anamorphisms (unfolds), and their generalizations called hylomorphisms.
third list-homomorphism theorem divide-and-conquer parallelism shortcut deforestation