How can I make a monoid-like interface in C#?

Question

I want to require things which implement an interface (or derive from a class) to have an implementation for Aggregate included. That is, if they are of type T I want them to have something of type Func<T,T,T>. In Haskell this is called a "monoid".

EDIT: What I want to call is something like this:

list.Aggregate((x, accum) => accump.MAppend(x));

Based on DigalD's answer, this is my best attempt, but it doesn't compile:

interface IMonoid<T>
{
    T MAppend(T other);
}

class Test
{
    public static void runTest<T>(IEnumerable<IMonoid<T>> list)
    {
        // doesn't work
        list.Aggregate((x, ac) => ac.MAppend(x));
    }
}

Answer 1

A monoid is an associative operation together with an identity for that operation.

interface Monoid<T> {
  T MAppend(T t1, T t2);
  T MEmpty
}

The contract of a monoid is that for all a, b, and c:

1. Associativity: MAppend(Mappend(a, b), c) = MAppend(a, Mappend(b, c))
2. Left identity: MAppend(MEmpty, a) = a
3. Right identity: MAppend(a, MEmpty) = a

You can use it to add up the elements in a list:

class Test {
  public static T runTest<T>(IEnumerable<T> list, Monoid<T> m) {
    list.Aggregate(m.MEmpty, (a, b) => m.MAppend(a, b));
  }
}

Answer 2

The answer by Apocalisp looks closest to the mark, but I'd prefer something like this:

public interface IMonoid<T>
{
    T Combine(T x, T y);
    T Identity { get; }
}

While Haskell calls the monoid identity mempty, I think it's more reasonable to use the language of abstract algebra, so I named the identity value Identity. Likewise, I prefer the term Combine over Haskell's mappend, because the word append seems to indicate some sort of list append operation, which it doesn't have to be at all. Combine, however, isn't a perfect word either, because neither the first nor the last monoids combine the values; instead, they ignore one of them. I'm open to suggestions of a better name for the binary operation...

(In Haskell, BTW, I prefer using the <> operator alias instead of the mappend function, so that sort of side-steps the naming issue...)

Using the above IMonoid<T> interface, you can now write an extension method like this:

public static class Monoid
{
    public static T Concat<T>(this IMonoid<T> m, IEnumerable<T> values)
    {
        return values.Aggregate(m.Identity, (acc, x) => m.Combine(acc, x));
    }
}

Here, I completely arbitrarily and inconsistently decided to go with Haskell's naming, so I named the method Concat.

As I describe in my article Monoids accumulate, one always has to start the accumulation with the monoidal identity, in this case m.Identity.

As I describe in my article Semigroups accumulate, instead of an imperative for loop, you can use the Aggregate extension method, but you'll have to use the overload that takes an initial seed value. That seed value is m.Identity.

You can now define various monoids, such as Sum:

public class Sum : IMonoid<int>
{
    public int Combine(int x, int y)
    {
        return x + y;
    }

    public int Identity
    {
        get { return 0; }
    }
}

or Product:

public class Product : IMonoid<int>
{
    public int Combine(int x, int y)
    {
        return x * y;
    }

    public int Identity
    {
        get { return 1; }
    }
}

Since I made the monoid argument the this argument of the Concat method, the method extends the IMonoid<T> interface, rather than IEnumerable<T>. I think this gives you a more readable API. For example:

var s = new Sum().Concat(new[] { 1000, 300, 30, 7 });

produces s == 1337, while

var p = new Product().Concat(new[] { 2, 3, 7 });

produces p == 42.

If you don't like having to create a new Sum() or new Product() object every time, you can make your monoids Singletons, like this All monoid:

public class All : IMonoid<bool>
{
    public static All Instance = new All();

    private All() { }

    public bool Combine(bool x, bool y)
    {
        return x && y;
    }

    public bool Identity
    {
        get { return true; }
    }
}

which you can use like this:

var a = All.Instance.Concat(new[] { true, true, true });

Here, a is true. You can use a similarly written Any monoid in the same way:

var a = Any.Instance.Concat(new[] { false, true, false });

I'll leave it as an exercise for the reader to figure out how Any is implemented.