List Homomorphisms and Parallelism
A list homomorphism is a function h on lists for which there exists an associative binary operator such that. H = h x h y. for any x and y, where ++ denotes list concatenation. The identity function, with being ++. Summation, with being +. Operationally, when computing a list homomorphism we can split the input into any number of chunks, compute a result per chunk, and then combine the results into a final result for the whole list. The first two list homomorphism theorems were published by Richard S. Bird in 1987, and the third by Gibbons in 1995. If h is a list homomorphism, then there is an operator and function f such that. In a parallel implementation of reduction, we might break the input into a chunk per processor, then use the second list homomorphism theorem to compute an optimised sequential fold for each chunk. If h can be expressed with both a leftwards and rightwards fold, then h is also a list homomorphism.