List homomorphisms are functions which can be efficiently computed in parallel since they ideally suit the divide-and-conquer paradigm. We propose a simple approach to testing whether a function is a homomorphism and, if so, how it can be parallelized. For some interesting functions which are not homomorphisms, e.g. the maximum segment sum problem, the methodology provides a systematic way of embedding into a homomorphism. The approach is based on analyzing two inherently sequential representations of the function based on cons- and snoc-lists.
Ulrike Peiker, Martin Griebl