Hacker News new | ask | show | jobs
by mcguire 3296 days ago
Are you sure that Semiring shouldn't be a Monoid?

What happens if you feel the urge to define several Semirings (or Monoids) on the data type?

2 comments

I'm not sure I follow, sorry. The line says that we also pledge to produce a Semiring from this Foldable structure. Given it's a length function it's about as general a specification I think you can give it without becoming something completely different.
To the first question, a Semiring has two operations, + and × conventionally (along with ...). That seems to be more than length needs. A Monoid is just an operation and its identity, which should be exactly what you need for length.

For the second question, traditional (+,×,...) is a Semiring for integers; so is (&,|,...) (bitwise boolean operations). How can you define both Semiring implementations without getting them confused?

There is another reply to my comment that I haven't digested yet. Maybe it answers the second.

"A Monoid is just an operation and its identity, which should be exactly what you need for length."

And I'm wrong about that. You need a zero and a one, right. What would that structure be?

I've been experimenting with answering that question.

An extremely heavily-commented approach to defining equality for things like Double (where there are multiple sensible ways to compare things) will probably be a better introduction to these ideas:

https://github.com/mrkgnao/noether/blob/master/library/Noeth...

https://github.com/mrkgnao/noether/blob/master/library/Noeth...

The rest of the repo implements abstract algebraic structures along similar lines.

Here is what monoids look like in this formalism at present. It's a bit involved: first I use a fine-grained separation into highly polymorphic Magma and Neutral classes:

https://github.com/mrkgnao/noether/blob/master/library/Noeth...

And there are "strategies" for combining those pieces of structure, whose use looks like

  type instance MonoidS (op :: BinaryNumeric) Rational 
    = DeriveMonoid_Semigroup_Neutral op Rational
Which means "derive the preferred monoid structure with operation op" (MonoidS op) on Rational from the preferred semigroup structure and preferred neutral element on it with that operation.

https://github.com/mrkgnao/noether/blob/master/library/Noeth...

You can always use some other monoid structure for the same combination of type and operation (!) if you like. For instance, here's a demo of using the self-action of a ring on itself (i.e. considering a ring as a module over itself) to compute something, even if your preferred choice of action has been declared to be something else (or hasn't been defined at all).

https://github.com/mrkgnao/noether/blob/master/library/Noeth...

This says "here, use the self-action derived from the multiplicative magma structure on R".

That is way more advanced Haskell than I am familiar with, but it does look like what I was wondering about. Thanks!