- A Boolean semiring
- Tropical semirings
- A case study
- The semiring of types
- Type distributivity
- A case study
- Table of semirings
- Naming shenanigans
A semiring is like a double monoid. That is, it’s a set equipped with two binary associative operations, often written (+) and (⋅) on analogy with the canonical integer monoids addition and multiplication, such that:
- (+) is a commutative binary operation If you have all the pieces of this structure except the first monoid is not commutative, then you have a quasiring instead of a semiring. with an identity element, e.g., 0;
- (⋅) is a binary operation with an identity element, e.g., 1;
- (⋅) distributes over (+); and
- multiplication by 0 (the identity of (+)) annihilates the set.
Some authors prefer using ⊕ and ⊗ for the first and second operations, respectively, and we’re going to use those through the rest of this article. We hope that the justification for using this notation will make itself obvious when we get to the section regarding tropical semirings.
A semiring is an exciting algebra because the semiring laws more precisely describe the relationship between the “multiplication” and “addition” than having two separate and apparently unrelated monoids over a type can. It is, however, worth noting that just as not all semigroups are also monoids, not all monoids form semirings. As one possible example, vector addition is commutative, so the commutative monoid for the first requirement is in place, but vector multiplication is not uniquely defined and may not have an identity, making the second property a stickier wicket.
There is no
Semiring typeclass in Haskell’s
base library. There are a few in libraries; it’s also worth mentioning that PureScript has the
Semiring class in the base library.
Data.Semiring in PureScript. Whereas
Num, which is a bit like a ring algebra, is the base of the numeric typeclass hierarchy in Haskell, PureScript has
Semiring at the base of theirs.
Semiring class in PureScript looks like this, with infix operators
(*) additionally defined as equal to
There are various Haskell libraries that offer a
Semiring class along with instances and related operations. One of these is
semirings package on Hackage. It’s worth pointing out in connection with this that
Semigroup also started its life in Haskell in a library and was eventually migrated to
base. which offers many instances, giving a good picture of the utility of the semiring algebra. It also includes a module for tropical semirings.
Here we give the
Semiring class from
semirings, with some omissions:
Another project worth mentioning here is the
foundation project, which has the ambitious goal of being an alternate
base library for Haskell. The
foundation project on Hackage and on Read the Docs. The authors have ported some things directly from the standard
base library, but in many cases they are also rethinking things. A source of many complaints about Haskell’s
base package is the
Num is a convenient typeclass but not terribly principled, and the
foundation authors wanted to give a more principled basis for the numeric hierarchy. They’ve gone a different route than PureScript did; instead of a single
Semiring class, they offer two classes, shown here but omitting some of the class methods: