Semigroups/Monoids/Groups with absorbing elements

[armanbilge]

I recently had a need for a Monoid and Group which also have an absorbing element a defined by

combine(a, x) === combine(x, a) === a

These seem to go by various names, including "monoid/group with zero", "0-group", and "binoid".

Might they find a home in the cats hierarchy?

For reference, my current implementations: Binoid (laws) and Group0 (laws).

Edit: In fact, this hierarchy should probably start from a semigroup with an absorbing element (Semigroup0?).

[rossabaker]

I thought something like this might exist in Algebra, but my search only pulled up an old Frank gist. Anyway, pinging @fthomas for his thoughts. :smile:

[fthomas]

That gist was written in response to a question and blog post about annihilators by @noelwelsh. I found the type class interesting because it has the same structure as Monoid but different laws, but I never needed or used that type class in other code.

[armanbilge]

Thank you both for following up! My use-case is for a Writer-style datatype that short-circuits subsequent computation (like option) once the log type L enters the absorbing state.

[rossabaker]

Two libraries serve as precedent in Haskell:

• zero: this one introduces a Zero[A] extends Semigroup[A].
• monoid-zero: introduces a MonoidZero[A] extends Monoid[A]. Also has a MonoidLZero and MonoidRZero.

Wikipedia calls it a null semigroup or zero semigroup. The Binoid name doesn't seem to have a lot of traction, and I found a another reference to it being something that's both a Monoid and Comonoid.

Starting at ZeroSemigroup, and working up to ZeroMonoid and ZeroGroup makes some sense to me. You could mix in the left and right, but then you'd have, uh, nine new traits?

I think the considerations for new typeclasses in Cats are:

• Is it lawful? Yes.
• Is it generally useful? Your case is neat and we can define a handful of instances. But Cats needs to maintain binary compatibility over the long haul. Where will this appear as a constraint outside your application?

My feeling is that it would be best to incubate these as a microlibrary to start, and if we can get more people excited about them, adopt them into cats-core.

[armanbilge]

Wow, thank you for looking into this in such depth, much much appreciated (next time I know to look to Haskell for precedents :)

But Cats needs to maintain binary compatibility over the long haul. Where will this appear as a constraint outside your application?

Makes sense :+1: I'll do some more research into use-cases and I'm also curious how those Haskell libraries are used in the wild.

My feeling is that it would be best to incubate these as a microlibrary to start

I'd be more than happy to spin this up :) and then, how to make people aware of it?

[rossabaker]

We could added it to typelevelEcosystem.md, which would get it on the Cats site as a related project. We can also mention it in the Cats channel and I'd be happy to retweet it.

If you need any help deciphering the Haskell, that's my daytime language. :smile:

[armanbilge]

@rossabaker Thank you for your support. If you wouldn't mind reviewing my implementations at https://github.com/armanbilge/litter/pull/1 I would really appreciate it! :pray:

[armanbilge]

Where will this appear as a constraint outside your application?

I finally found the answer that I was looking for to @rossabaker's question. As I mentioned above, my use case for a ZeroSemigroup[A] (aka a semigroup with an absorbing element) is to support

a Writer-style datatype that short-circuits subsequent computation (like option) once the log type L enters the absorbing state.

I just learned about the MTL type class Chronicle with a very similar purpose.

Chronicle[F, E] allows us to both accumulate values and also short-circuit computations with a final output.

In Chronicle, to short-circuit the user must explicitly confess an E (to use the Chronicle-terminology). However, by having a ZeroSemigroup[E] available (with an appropriate equivalence relation Eq[E] to identify the absorbing element i.e. an equivalence class of fatal errors) the implementation could determine by itself whether a "dictation" rises to the level of a "confession" (i.e., the error is absorbing aka "fatal") and thus whether to short-circuit.

The power of this is that by selecting the instance for ZeroSemigroup[E] you define exactly what constitutes a "fatal" error. Unlike Chronicle, where dictate and confess are baked into your program, this strategy would enable you to defer this choice.

tl;dr if Chronicle is useful, then a ZeroSemigroup ought to be as well :wink: