[_lm_]

For the Map-Reduce transformation, you require f(r(a,b)) = r(f(a),f(b)). This is equivalent to requiring r to be a homomorphism, I think.

You could probably generalize that condition to situations where f can be lifted over the output of r so you don't have to require that r's output type is the same as its input.

[pschanely]

Unfortunately, I took barely enough grad school classes to be dangerous! It's worth clarifying that the lifting of f through r can change r (to, say r'), in which case, yes, f is a homomorphism from an algebra with r' to an algebra with r. (hopefully I got that right?)

I am curious about the idea that the inputs and outputs of r may not need to be of the same type, and want to investigate further (help is appreciated!). Since r is given to reduce(), at least one of its inputs must match its output, depending on how you define reduce(). Haskell's fold(l/r) permit the non-accumulator side to differ in type from the output, but the output must match the accumulator side. I think some similar transformation may apply to folds, but haven't thought about it enough.