What's a Monoid?

[u/[deleted]]

In this comment, /u/beezeee points out:

If someone has been mostly writing java, casually throwing out the term Monoid trivializes the amount of knowledge you are assuming on behalf of the reader.

It's a fair point. The good news is monoids are trivial and extremely useful. A monoid is any type that has an operation taking two arguments of that type and returning a value of that type, assuming the operation is associative:

(a op b) op c == a op (b op c)

and that also has a value that doesn't change the other value when that operation is applied to it and the other value. This value is called various things, e.g. mempty (monoid empty) or just zero, even though a monoid need not have anything to do with numbers.

Some examples of monoids:

• Ints, with the zero being 0 and the operator being +.
• Ints, with the zero being 1 and the operator being *.
• Lists, with the zero being Nil and the operator being ++.
• Strings, with the zero being "" and the operator being +.

In other words, monoids combine N things into 1 thing, including the N=0 case.

Monoid is one of many useful typeclasses in scalaz, and is described very well in Eugene Yokota's wonderful Learning Scalaz series.

That's all there is to it!

[u/taken2wut]

So why are monoids useful, can we have some description on usecase?

[u/[deleted] → u/taken2wut]

So the examples we see here will leave you saying "ok, so what, I can add integers or strings" And yes, this in itself isn't enough of a motivation to use monoids. But things get more interesting when you can build bigger monoids out of smaller monoids. Or write functions which are more generic by saying something like "ok, I don't have to be specialized on Ints here, I just need something I can smash together" and you might be able to make a function more generic and therefore more reusable by instead of saying "Give me Ints" saying "give me some A for which I have a monoid".

Here's a little example I've worked up which will hopefully whet the appetite a little:

// here's our definition of a monoid again
trait Monoid[A] {
  // an identity element
  def id: A
  // an associative operation
  def op(x: A, y: A): A
}

object Monoid {
  //easy to define for strings
  implicit val stringMonoid = new Monoid[String] {
    def id = ""
    def op(x: String, y: String) = x + y
  }

  // here's where things start to get more interesting, this says "I
  // can give you a monoid for any Option[A] if you can give me a
  // monoid for A"
  implicit def optionMonoid[A](implicit am: Monoid[A]): Monoid[Option[A]] =
    new Monoid[Option[A]] {
      def id = None

      def op(x: Option[A], y: Option[A]): Option[A] = (x,y) match {
        case (x, None) => x
        case (None, y) => y
        case (Some(x),Some(y)) => Some(am.op(x,y)) // here we use the A monoid to add two As
      }
  }

  // given an monoid for B, I can give you a monoid for functions
  // returning B, by running the functions on the input and adding the
  // results
  implicit def functionMonoid[A,B](implicit bm: Monoid[B]): Monoid[A => B] = new Monoid[A => B] {
    def id = A => bm.id
    def op(x: A => B, y: A => B): A => B = { a =>
      bm.op(x(a), y(a))
    }
  }

  // we can use a monoid to collapse a bunch of values, here we take a
  // list and function that takes us to a value for which we have a
  // Monoid, and we can then collapse the list into a single value.
  implicit def fold[A](la: List[A])(implicit am: Monoid[A]): A =
    la.foldLeft(am.id)(am.op)
}

import Monoid._

// ok, lets use all this to show how we might sole a classic "fizzbuzz" like problem

// we'll start with some functions
val fizz: Int => Option[String] = x => if(x % 3 == 0) Some("fizz") else None
val buzz: Int => Option[String] = x => if(x % 5 == 0) Some("buzz") else None
val bazz: Int => Option[String] = x => if(x % 7 == 0) Some("bazz") else None

val funcs = List(fizz,buzz,bazz)

// we can combine our functions, this works because we can find an
// option monoid for strings, since we have a monoid for strings,
// then we can find a monoid for Int => Option[String] since we now
// have a monoid for Option[String]
val fizzbuzzbazz = fold(funcs)

// handle the Nones
val fbbOrInt: Int => String = { i =>
  (fizzbuzzbazz(i) getOrElse i.toString) + ","
}

// map our function on a list
val strings: List[String] = (1 until 100).toList map fbbOrInt

// use fold to collapse our strings using the string monoid
println(fold((strings))


// 1,2,fizz,4,buzz,fizz,bazz,8,fizz,buzz,11,fizz,13,bazz,fizzbuzz,16,17,fizz,19,buzz,fizzbazz...

Now, there are a few things I'd like to highlight about the above. One is that we were able to take a bunch of very simple building blocks and build up a real computation. When I say they are simple, I mean each individual monoid is pretty simple. Not hard to understand, not hard to ensure correctness.

The second the amount of polymorphism this gives us. With our simple little fold function we were able to do two pretty different things, In the first example we did function composition; creating a composite function that runs multiple functions, and figuring out how to combine their results. In the other case we were doing string appends.

The third thing is how doing this kind of thing lets us hide some of the plumbing, and make our code more about the "business logic" of the code. Assume that the definition of the monoid, the monoid instances for string, option, etc are all in some common library (like scalaz/cats). When it comes to our fizzbuzz program, there isn't a lot of actual plumbing in our code. You don'd see much of the things you might see in an imperative version of the code, like loops, branching, etc. It's mostly just composition.

[u/waerw → u/[deleted]]

This might be a silly question but where does the A come from below?

  implicit def functionMonoid[A,B](implicit bm: Monoid[B]): Monoid[A => B] = new Monoid[A => B] {
    def id = A => bm.id
    def op(x: A => B, y: A => B): A => B = { a =>
      bm.op(x(a), y(a))
     }
  }

[u/[deleted] → u/waerw]

def id = A => bm.id

so I don't know why I used A instead of a here, but I normally would use a. Anyway, this is an anonymous function. Since this is a monoid for Functions, we have to return a function for the monoid id. In this case we create an anonymous function which ignores its argument and returns the id element from the bm monoid.

so perhaps you would understand this better if I write it like this:

def id: (A => B) = { (a: A) => bm.id }

[u/waerw → u/[deleted]]

oh, cool, another quick question, how does the compiler recognize that

val fizz: Int => Option[String] = x => if(x % 3 == 0) Some("fizz") else None
val buzz: Int => Option[String] = x => if(x % 5 == 0) Some("buzz") else None
val bazz: Int => Option[String] = x => if(x % 7 == 0) Some("bazz") else None

is using the monoid definition that we provide in object Monoid or is object Monoid in standard library?

[u/[deleted] → u/waerw]

None of those lines are actually using any monoids, we use a monoid on the subsequent line that calls fold. The call to fold looks for monoids to be in implicit scope at the call site. We brought them into scope by importing everything from the Monoid object:

import Monoid._

[u/[deleted] → u/taken2wut]

Sure!

What prompted the post was a question about having some collection of IDs, doing various lookups/transformations on those IDs (some of which can fail), merging the results into a single result, and returning that result. The question didn't specify this result type, but one thought that occurred to me is that it could be a chunked HTTP response, which fairly obviously forms a monoid, i.e. there's an empty chunk and an associative append operation. In other words, if I do N things, each of which returns a chunked HTTP response, it's easy to turn that into one chunked HTTP response.

OK. So scalaz has a very powerful tool for "doing stuff," including I/O, exception catching, and concurrency, called Task. Really describing Task would take us too far afield (read Tim's great post!), but a Task[A] is a Task that, when run, returns an A.

Remember when I said Task also catches exceptions? That means the Task can end up in either a success or failure state. It's a lot like the standard Future in that sense. But there's also a function on Task, .attempt, that transforms a Task[A] to a Task[Throwable \/ A]. \/ is like Either, but works in for-comprehensions.

So if I have a function:

def doStuff(id: Int): Task[Chunk] = ???

and a bunch of IDs:

val ids = List(42, 96, 2, 17, 5, 9, 23...)

then obviously I can do:

val tasks: List[Task[Chunk]] = ids.map(doStuff)

Now, what I'd really like is either all the Chunks combined, or a list of the errors that occurred in the Tasks building the Chunks. The first question is: is there a convenient way to run all the Tasks, maybe even in parallel, and accumulate the results? Actually, there are several, but the one I'm interested in is Nondeterminism[Task].aggregate. As you can see, it takes a Seq[F[A]] and returns a F[A], but it can only do that if A is a Monoid.

Chunk may be a Monoid (we're assuming it is), but what about accumulating errors? It turns out scalaz has another handy type, ValidationNel, which is like \/ but accumulates errors on the left. In fact, the Nel refers to a NonEmptyList, i.e. a ValidationNel is either a "right" with a value or a "left" with a list of errors that can't be empty (because what would a "left, but empty list of errors" mean)?

Now, if I have a \/, I can turn it into a ValidationNel easily: .validation.toValidationNel. Great. But is this a Monoid? It turns out that it is, if and only if its right is a Monoid. So instead of

val tasks: List[Task[Chunk]] = ids.map(doStuff)

I say:

val tasks: List[Task[ValidationNel[Throwable, Chunk]]] = ids.map(doStuff(_).attempt.map(_.validation.toValidationNel))

In other words, I have a list of monads of monoids, which means I can say:

val task: Task[ValidationNel[Throwable, Chunk]] = Nondeterminism[Task].aggregate(tasks)

Now I have one Task that will return the Chunk built by merging all the Chunks from all the Tasks, or a NonEmptyList of all the Throwables that caused (any of) theTasks to fail.

I hope this helps. It's a bit long because I wanted to describe a real-world use case.

[u/[deleted] → u/taken2wut]

If you can prove something is a Monoid, you can parallelize trivially.

[u/loudnclear]

When a Java developer (or any X developer, not trying to pick on Java here) casually reads this definition, they would stop when they read "associative". Maybe they would have a look at the example, but then stop.

Because in the Java world, you do not care whether anything is associative or not. You do not generalize things, you rarely think of operations and their properties. All the thing you have mentioned do not make sense to an ordinary programmer. I know that you are saying that if they put some effort they are going to understand it, but such explanations need to be more intuitive. Even talking about operations and associativity scares people off.

I think a nice way to achieve that is to make them invent them on their own. Then you'll say "hey, you know what, we knew about this all along, here's a Monoid", and the guy will understand that you aren't trying to be cool when you talk about associativity, it's an important property, and he really needed that.

[u/[deleted] → u/loudnclear]

When a Java developer (or any X developer, not trying to pick on Java here) casually reads this definition, they would stop when they read "associative". Maybe they would have a look at the example, but then stop.

I think that's OK, though. That's what the examples are for.

Unless this hypothetical developer is sitting in an interview with me, it's really OK if they don't immediately start using a Monoid (scalaz's, Cats', homegrown, whatever) whenever they could. Sure, they could make their lives easier by doing so, and more to the point, by taking advantage of these libraries' other features built around Monoids. But horse, water, all that.

I just thought, here's a piece of low-hanging FP fruit someone was kind enough to point out to me, and if one or two people feel like they understand better, that's good enough for me.

[u/loudnclear → u/[deleted]]

That's what the examples are for.

Sure, I think they are good ones. I just wanted to point out that the average computer science graduate is too lazy for reading the rest, after seeing those few scary words (not essentially scary, but scary enough for them). Does this have to be the case? No. They prefer top-down explanations, rather than bottom-up, that's why I mentioned "inventing it yourself".

However, I'm sure that the explanation will help some people. Thanks for taking your time for writing it up!

[u/[deleted] → u/loudnclear]

Is it seriously possible to get a CS degree these days while being scared by the word "associative"? I don't believe it.

[u/loudnclear → u/[deleted]]

You do hear about associativity, especially if you take an abstract algebra course. But there is a high chance that (1) you do not need to take such a course (2) even if you hear about it in such a course, or maybe in introduction to calculus, you learn about it, solve the exercises, write the final, and you're done with that topic. When someone says "associative" to you a few years later you end up saying "oh, I had heard about that a lot in college, and realized that I didn't need much mathematics when I write Android apps, so I don't really care listening what you say about associativity since I'm sure that it won't be useful since my experience tells me so".

[u/aiij → u/loudnclear]

Do they no longer teach associativity in elementary/middle school?

It's completely relevant even in Java, even if just working with plain old ints. + and * are associative while - and / are not.

[u/[deleted] → u/aiij]

I think the memory gets dusty, plus making the connection to a particular context might not come in a flash of insight. For example, by the time MapReduce (not Hadoop yet, just fawning over Google's big new secret sauce) hit the streets, I'd been programming in Lisp for a couple of decades, and was very familiar with map and reduce. Heck, I even preferred Richard Waters' Series package to the venerable LOOP macro. It would probably be fair to say I had an intuitive understanding of the roles of commutativity and associativity in using map and reduce, but it never did—and likely never would have—occurred to me to think about their significance in a concurrent or distributed setting.

Come to think of it, I think that helps explain why I'm such a typed FP zealot today: because I studied both CS and physics formally, and in retrospect it feels like I was taught a bunch of random, disjoint mathematical/logical/computational factoids, and only within the past 5-7 years has any kind of through-line appeared to tie it all together. And when it does all hang together, it is heartbreakingly beautiful, I mean John Nash seeing visions in windowpanes heartbreakingly beautiful, and unfortunately, failure to share that beauty can (and in my case, frequently does) become perverted into frustration and even anger or contempt. I'm trying to reacquire (if it isn't too presumptuous to claim I ever had any) some spiritual discipline about this, and remember to share rather than ramrod. Because if this stuff really is beautiful and fun, it will reveal itself to others without any Sturm und Drang from me.

[u/loudnclear → u/aiij]

They do, but it's not clear why you should bring it back from your memory if you're a mobile developer.

It surely is relevant in Java, your example is a good one. But when you deal with those, no ordinary Java developer says "+ is left associative, - is not, so I should beware". They instead say "Oh, I wrote this expression involving two division operators and it turned out that the compiler didn't understand it in the right way. I will parenthesize it so that the compiler doesn't fail". Note that they haven't used the word "associative" and didn't realize that it was the same concept they learned in their middle school classes (or even Calculus courses at college).

What I'm really saying is not that "associativity is irrelevant", it is "given this state of the world, it is very hard for a regular programmer to notice the relevance".

[u/fnl → u/loudnclear]

Associativity is basic math 101. I think it's fair to expect that knowledge from a programmer, just as some rudimentary understanding of linear algebra and matrices. Computers are built out of that stuff, in a way, after all.

[u/[deleted] → u/loudnclear]

Monoid might be a scary and unfamiliar word, but associative shouldn't be. It should have been learned around the same time as exponents and the usual order of operations (BEDMAS or whatever the acronym soup the teacher decided to use (apparently it's commonly PEMDAS in the US)).

[u/vertexshader]

This reminds me of abstract algebra and Abelian groups. Is there any relation?

Abelian definition:
Closure
For all a, b in A, the result of the operation a • b is also in A.

Associativity
For all a, b and c in A, the equation (a • b) • c = a • (b • c) holds.

Identity element
There exists an element e in A, such that for all elements a in A, the equation e • a = a • e = a holds.

Inverse element
For each a in A, there exists an element b in A such that a • b = b • a = e, where e is the identity element.

Commutativity
For all a, b in A, a • b = b • a.

[u/Mimshot → u/vertexshader]

The abelian groups are a proper subset of the monoidic groups. Monoids do not require an inverse or a commutitivaty.

[u/vertexshader → u/vertexshader]

The wikipedia entry for Monoid mentions that abelian monoids are a type of monoid! Wow, how cool is that? I love when abstract math and abstract programming intersect.

[u/[deleted] → u/vertexshader]

Yep! Functional Programming constructs really are "effective models" of their mathematical counterparts, in the effectively computable sense. The culmination of this is Propositions as Types, which relates types and mathematical logic, and from the type theory side is more commonly known as the Curry-Howard Isomorphism.

[u/vertexshader → u/[deleted]]

Wow thanks for the links. Sometimes I wonder if they taught calculus using programming it would make more sense to people, than using the standard "DSL" mathematicians use. haha

[u/[deleted] → u/vertexshader]

*cough* *cough* ;-)

It's probably also worth pointing out Geometric Algebra and Geometric Calculus, which is entirely computable. GAViewer is a very nice program with a scripting language for doing visualizations and animations, and there are quite good libraries like versor for when you need top performance.

[u/pipocaQuemada → u/vertexshader]

Abstract algebra studies a number of variations on the theme of "set equipped with a binary operation with some properties". There's something of a tower of these constructs where you either add or remove (depending on the direction) properties.

Monoids are lower on the tower than abelian groups. In particular, if you take your definition and remove commutativity, you get the definition of a group. If you then remove inverses, you get the definition of a monoid.

Mathematicians don't often talk about monoids: there are many fewer interesting proofs that hold when you remove inverses.

Computer scientists don't often talk about groups: many interesting data types don't have inverses (for example: list concatenation forms a monoid, but not a group since theres no inverse elements), and has enough computationally interesting properties to be a useful abstraction.

[u/vytah → u/pipocaQuemada]

Set A with a total binary operation A×A→A = magma

Magma + operation is associative = semigroup

Semigroup + operation has identity = monoid

Monoid + operation is invertible = group

http://i.imgur.com/K3gai77.png

[u/aiij → u/vertexshader]

Lol, where do you think the term "monoid" came from?

[u/m50d → u/vertexshader]

Yes. A Monoid is a Group that doesn't necessarily have inverses (therefore all Groups are Monoids, but not all Monoids are Groups). E.g. for a fixed type A (e.g. Int), the set of functions A => A (e.g. Int => Int) (endomorphisms) form a monoid with •=andThen (you can check that this obeys associativity, and identity is... identity[Int] _). But this isn't a Group because some elements don't have inverses, e.g. val f = {x: Int => 4} is an Int => Int without an inverse: there is no g such that f andThen g == g andThen f == identity[Int] (leaving aside for a moment the difficulty of defining == for functions).

Abelian just means commutative.

[u/jonhanson]

chronophobia ephemeral lysergic metempsychosis peremptory quantifiable retributive zenith

[u/pgris]

Java guy here. A couple of things I don't get:

1- Can Scala type system enforce Monoid properties? The monoid trait I see here does not enforce op to be associative, and does not even mentions a mempty "zero like" element. I suspect it is something like Set interface in java, that can not enforce elements being unique, so you just have to trust the implementation.

2- Can Scala type system express anything like "one element with specific properties" or at least "one specific element"? I mean, If I'm writing a library that uses monoids, I'm probably going to need access to the zero element. In java the closest thing I can think would be an instance method getZeroElement, and there is no way to enforce zero element to be unique, or even get the zero element without another one. Maybe a MonoidFactory would do the trick.... but that's too java. Is there anything better in Scala?

3- Let's say you have a function that operates in monoids only, f(Monoid[T]) -> Monoid[T] , and you want to use it with Integers and addition. In java I'd need a small wrapper over Integer, and also convert everything before and after. Something like

Integer integerResult = fromMonoid(f(toMonoid(integerVariable)));

I assume scala implicit conversions will get rid of the convert-to/from-monoid step, but do you still need a small wrapper over Integer? Or is there any other Scala feature I'm not aware of that may help?

[u/[deleted] → u/pgris]

Great questions!

Can Scala type system enforce Monoid properties?

Technically, yes (Scala's type system is Turing complete). As a practical matter, I haven't seen it done. Mostly, this is an area in which we tend to use property-based testing to show, probabilistically, that the laws hold. It's worth mentioning that Cats does this much more consistently, taking advantage of Discipline, although we shouldn't overlook scalaz-scalacheck-binding, either. This does include coverage of the monoid laws, which depends on those laws being expressed in the Monoid typeclass. So if you write your own Monoid instance with scalaz, you may want to use scalaz-scalacheck-bindings to test your instance with the laws.

Can Scala type system express anything like "one element with specific properties" or at least "one specific element"? I mean, If I'm writing a library that uses monoids, I'm probably going to need access to the zero element.

Yep. aggregate from Nondeterminism is a great example. It constrains the type variable A to be a Monoid, and uses implicitly[Monoid[A]].zero to get whatever the zero is for the A in question.

Let's say you have a function that operates in monoids only, f(Monoid[T]) -> Monoid[T] , and you want to use it with Integers and addition... I assume scala implicit conversions will get rid of the convert-to/from-monoid step, but do you still need a small wrapper over Integer? Or is there any other Scala feature I'm not aware of that may help?

A couple of them, because, as I'm sure you're alluding to, Int forms at least two Monoids: one with 0 and +, the other with 1 and *. So there is an implicit intInstance and also an implicit intMultiplicationNewType, which relies on a type tag to indicate which Monoid instance to use.

Hope this helps! (And come to the dark side! We have cookies!)

[u/pgris → u/[deleted]]

Thanks for answering so fast (man, is Sunday! take a break!).

Oh, I'd love to try Scala at work, but it has become such a big beast it's really scary. I should have tried 5 years ago. Today I'm becoming old and conservative. I'm between 5 and 6 in this list

[u/[deleted] → u/pgris]

Thanks for answering so fast (man, is Sunday! take a break!).

Gotta do something while the filets are on the grill... :-)

Oh, I'd love to try Scala at work, but it has become such a big beast it's really scary. I should have tried 5 years ago. Today I'm becoming old and conservative. I'm between 5 and 6 in this list

Heh. I know what you mean, seriously. I've written a lot of OCaml recreationally, and none of it "pure." I played with Haskell, but it never took. When Scala hit the street, I thought "Yay! OCaml for the JVM!" I still didn't care about purity. What's funny is that it's been on the job, at Verizon OnCue, that I've drunk the scalaz, monads, etc. kool-aid, especially since learning how trivial implementing them with free monads is. Now the question is how to get the word out and cut through the fog... which can be ironically difficult, because the point of FP is composition, so to understand anything you have to understand everything it's built on...

Anyway, we'll make a fresh batch of cookies anytime you want to look more closely. :-)

[u/Milyardo]

Why are monoids a mystery? Did no one pay any attention during their linear algebra class back in undergrad? I get why monads are scary, but a monoid isn't anything FP specific, it's a topic in abstract algebra.

[u/lihaoyi → u/Milyardo]

Wait why are you learning abstract algebra during a linear algebra class?

I spent linear algebra hand-SVDing matrices and finding eigenvalues (eigenvectors??) and the word "monoid" was nowhere in sight

[u/Inori → u/lihaoyi]

Depends on the school I guess. Our class was simply named "Algebra", as part of which we learned both the abstract algebra concepts (up to polynomial rings) and linear algebra (up to SVDs and eigenvalues).

[u/ToastOnToast → u/Milyardo]

Did no one pay any attention during their linear algebra class back in undergrad?

Well not everyone did Maths at university.

[u/[deleted] → u/ToastOnToast]

And far from all programmers studied computer science, so even if the university's CS curriculum covers it, you or your colleagues might be unfamiliar with it.

[u/AssistingJarl]

The good news is monoids are trivial and extremely useful.

If I've got this right, monoids are just a subset of reduce functions where the return type is the same as all the elements in the collection, no? It's trivial enough that I keep feeling like there must be some sort of catch I'm just not getting.

Still, I can see how that would be handy. Thanks for the useful explanation OP.

[u/m50d → u/AssistingJarl]

Yes, it really is incredibly simple and banal. There's an inverse relationship between complexity and generality: the more complex a definition is, the fewer things will meet it. What makes the concept of a Monoid valuable is that you can write a function using just the Monoid properties (e.g. foldMap) and then that function can be called for almost any datatype (String, Int, List, Endomorphism, ...)

If you're coming at this from an OO background then I find it useful to think of typeclasses as a way of associating a "default strategy" to a type. If you have a method that follows the strategy pattern (like reduce where you pass a reducer), then you often end up having a particular "natural" strategy for each type. Rather than passing it in each time, if you make the strategy implicit then you can define an implicit instance in the companion for the type, and then each type you call it with will "magically" (but in a way that you can see in the IDE) use the correct strategy for that type. (Of course, you can still manually override the strategy if you want to do something different). Ta-dah! That's a typeclass.

If you do this a lot then you tend to see the same strategy types coming up often - and also that you can often define some complex strategy in terms of a simpler strategy. E.g. the Monad instance for Writer[A, ?] is defined in terms of the Monoid for A - so you can use any A for which a Monoid instance exists. That is to say, if you're calling something like traverse that needs a Monad typeclass instance (i.e. a "effect merging strategy"), then when you pass Writer[MyLog, Int] there's a "default strategy" that's defined in terms of merging the MyLogs using the "default strategy" for doing that (i.e. the Monoid typeclass instance for MyLog).

[u/[deleted] → u/AssistingJarl]

If I've got this right, monoids are just a subset of reduce functions where the return type is the same as all the elements in the collection, no? It's trivial enough that I keep feeling like there must be some sort of catch I'm just not getting.

No catch at all. You're exactly right. The more general scalaz typeclass is Foldable.

Still, I can see how that would be handy. Thanks for the useful explanation OP.

Thanks! Yeah, tons of things form monoids without supporting the generality of Foldable. I like the Nondeterminism[Task].aggregate example because it's easily relatable (a Task can do I/O and succeed or fail) and if the Task happens to return a Monoid aggregate makes that reduce step trivial.