Use diff-lists (more generally, diff-monoids) in fold?

[byorgey]

See http://www.cis.upenn.edu/~byorgey/pub/monoid-pearl.pdf for context. It might be good to ensure the results are always right-nested; although this should be well-documented since in theory not all monoids will be more efficient that way.