The fact that a monoid operation is associative means that if we have to chain multiple operations, we could probably do it in parallel. For example, if we have the numbers 1, 2, 3, and 4 and wanted to find 4!, we can use what we used previously, which would end up being evaluated to the following:
op(op(op(1, 2), 3), 4)
The associativity, however, would allow us to do the following:
op(op(1, 2), op(3, 4))
Here, the nested operations could be done independently and in parallel. This is also called balanced fold. An implementation of a balanced fold would look like the following:
def balancedFold[T, Y](list: IndexedSeq[T], m: Monoid[Y])(f: T => Y): Y = if (list.length == 0) { m.zero } else if (list.length ...
