# Monoids accumulate by Mark Seemann

*You can accumulate an arbitrary number of monoidal values to a single value. An article for object-oriented programmers.*

This article is part of a series about monoids. In short, a *monoid* is an associative binary operation with a neutral element (also known as *identity*).

Recall that a binary operation is an operation involving two arguments of the same type, and returning a value of that type.

public static Foo Op(Foo x, Foo y)

Notice that such an operation reduces two `Foo`

values to a single `Foo`

value.

### Accumulation #

Since you have an operation that can reduce two values to a single value, you can use that single value as the input for yet another binary operation. This enables you to accumulate, or aggregate, an arbitrary number of values.

Consider the instance variation of the above `Op`

method:

public Foo Op(Foo foo)

This is another representation of the operation, but instead of being a static method, it's an instance method on the `Foo`

class.

When `Op`

is a monoid, you can easily write a function that accumulates an arbitrary number of `Foo`

values:

public static Foo Accumulate(IReadOnlyCollection<Foo> foos) { var acc = Identity; foreach (var f in foos) acc = acc.Op(f); return acc; }

You start with the `Identity`

value, which also becomes the return value if `foos`

is empty. Then you simply loop over each value in `foos`

and use `Op`

with the value accumulated so far (`acc`

) and the current element in the sequence.

Once you're done looping, you return the accumulator.

This implementation isn't always guaranteed to be the most efficient, but you can *always* write accumulation like that. Sometimes, a more efficient algorithm exists, but that doesn't change the overall result that you can always reduce an arbitrary number of values whenever a monoid exists for those values.

### Generalisation #

You can do this with any monoid. In Haskell, this function is called `mconcat`

, and it has this type:

mconcat :: Monoid a => [a] -> a

The way you can read this is that for any monoid `a`

, `mconcat`

is a function that takes a linked list of `a`

values as input, and returns a single `a`

value as output.

This function seems both more general, and more constrained, than the above C# example. It's more general than the C# example because it works on any monoid, instead of just `Foo.Op`

. On the other hand, it seems more limited because it works only on Haskell lists. The C# example, in contrast, can accumulate any `IReadOnlyCollection<Foo>`

. Could you somehow combine those two generalisations?

Nothing stops you from doing that, but it's already in Haskell's `Data.Foldable`

module:

fold :: (Monoid m, Foldable t) => t m -> m

The way to read this is that there's a function called `fold`

, and it accumulates any monoid `m`

contained in any 'foldable' data container `t`

. That a data container is 'foldable' means that there's a way to somehow fold, or aggregate, the element(s) in the container into a value.

Linked lists, arrays, and other types of sequences are foldable, as are Maybe and trees.

In fact, there's little difference between Haskell's `Foldable`

type class and .NET's `IEnumerable<T>`

, but as the names suggest, their foci are different. In Haskell, the focus is being able to fold, accumulate, or aggregate a data structure, whereas on .NET the focus is on being able to enumerate the values inside the data structure. Ultimately, though, both abstractions afford the same capabilities.

In .NET, the focal abstraction is the Iterator pattern, which enables you to enumerate the values in the data container. On top of that abstraction, you can derive other behaviour, such as the ability to Aggregate data.

In Haskell, the focus is on the ability to fold, but from that central abstraction follows the ability to convert the data container into a linked list, which you can then enumerate.

### Summary #

You can accumulate an arbitrary number of monoidal values as long as they're held in a container that enables you to 'fold' it. This includes all sorts of lists and arrays.

This article concludes the article series about monoids. In the next series of articles, you'll learn about a related category of operations.

**Next: ** Semigroups.

## Comments

@ploeh as always I loved your blog post but I don't 100% agree on your comparison of the iterator pattern with Foldable - the iterator pattern allows usually sideeffects and you have Traversable for that - you might also like this: http://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf …

(Comment submitted via Twitter)