[yakubin]

> I think if one thinks of mapreduce as an operation on sets not lists, it should be obvious that the monoid must be commutative.

If anything, you could think of it as an operation on multisets, but not sets. Sets don't have repeated elements.