# Semigroups accumulate by Mark Seemann

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

This article is part of a series about semigroups. In short, a *semigroup* is an associative binary operation.

As you've learned in a previous article, you can accumulate an arbitrary number of monoidal values to a single value. A corresponding property holds for semigroups.

### Monoid accumulation #

When an instance method `Op`

forms 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; }

Notice how this generally applicable algorithm starts with the `Identity`

value. One implication of this is that when `foos`

is empty, the return value will be `Identity`

. When `Op`

is a semigroup, however, there's no identity, so this doesn't quite work. You need a value to start the accumulation; something you can return if the collection is empty.

### Semigroup accumulation #

From Haskell you can learn that if you have a semigroup, you can accumulate any non-empty collection:

`sconcat :: Semigroup a => NonEmpty a -> a`

You can read this as: for any generic type `a`

, when `a`

forms a `Semigroup`

, the `sconcat`

function takes a non-empty list of `a`

values, and reduces them to a single `a`

value. `NonEmpty a`

is a list with at least one element.

### NotEmptyCollection #

You can also define a `NotEmptyCollection<T>`

class in C#:

public class NotEmptyCollection<T> : IReadOnlyCollection<T> { public NotEmptyCollection(T head, params T[] tail) { if (head == null) throw new ArgumentNullException(nameof(head)); this.Head = head; this.Tail = tail; } public T Head { get; } public IReadOnlyCollection<T> Tail { get; } public int Count { get => this.Tail.Count + 1; } public IEnumerator<T> GetEnumerator() { yield return this.Head; foreach (var item in this.Tail) yield return item; } IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } }

Because of the way the constructor is defined, you *must* supply at least one element in order to create an instance. You can provide any number of extra elements via the `tail`

array, but one is minimum.

The `Count`

property returns the number of elements in `Tail`

, plus one, because there's always a `Head`

value.

The `GetEnumerator`

method returns an iterator that always starts with the `Head`

value, and proceeds with all the `Tail`

values, if there are any.

### Finding the maximum of a non-empty collection #

As you've already learned, `Math.Max`

is a semigroup. Although the .NET Base Class Library has built-in methods for this, you can use a generally applicable algorithm to find the maximum value in a non-empty list of integers.

private static int Accumulate(NotEmptyCollection<int> numbers) { var acc = numbers.Head; foreach (var n in numbers.Tail) acc = Math.Max(acc, n); return acc; }

Notice how similar this algorithm is to monoid accumulation! The only difference is that instead of using `Identity`

to get started, you can use `Head`

, and then loop over all elements of `Tail`

.

You can use it like this:

var nec = new NotEmptyCollection<int>(42, 1337, 123); var max = Accumulate(nec);

Here, `max`

is obviously `1337`

.

As usual, however, this is much nicer, and more succinct in Haskell:

Prelude Data.Semigroup Data.List.NonEmpty> getMax $ sconcat $ fmap Max $ 42 :| [1337, 123] 1337

That's hardly the idiomatic way of getting a maximum element in Haskell, but it does show how you can 'click together' concepts in order to achieve a goal.

### Aggregate #

Perhaps the observant reader will, at this point, have recalled to him- or herself that the .NET Base Class Library already includes an `Aggregate`

extension method, with an overload that takes a seed. In general, the simpliest `Aggregate`

method doesn't gracefully handle empty collections, but using the overload that takes a seed is more robust. You can rewrite the above `Accumulate`

method using `Aggregate`

:

private static int Accumulate(NotEmptyCollection<int> numbers) { return numbers.Tail.Aggregate( numbers.Head, (x, y) => Math.Max(x, y)); }

Notice how you can pass `Head`

as the seed, and accumulate the `Tail`

using that starting point. The `Aggregate`

method is more like Haskell's `sconcat`

for semigroups than `mconcat`

for monoids.

### Summary #

A semigroup operation can be used to reduce values to a single value, just like a monoid can. The only difference is that a semigroup operation can't reduce an empty collection, whereas a monoid can.

**Next:** Quasigroups