# Semiring

Contents
• Classes
• A Boolean semiring
• Tropical semirings
• Distributivity
• Annihilation
• 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.

## Classes

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. 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.

The `Semiring` class in PureScript looks like this, with infix operators `(+)` and `(*)` additionally defined as equal to `add` and `mul`, respectively:

``````class Semiring a where
add  :: a -> a -> a
zero :: a
mul  :: a -> a -> a
one  :: a``````

There are various Haskell libraries that offer a `Semiring` class along with instances and related operations. One of these is `semirings`The `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:

``````class Semiring a where
{-# MINIMAL plus, times, (zero, one | fromNatural) #-}
plus  :: a -> a -> a -- ^ Commutative Operation
zero  :: a           -- ^ Commutative Unit
times :: a -> a -> a -- ^ Associative Operation
one   :: a           -- ^ Associative Unit``````

Another project worth mentioning here is the `foundation` project, which has the ambitious goal of being an alternate `base` library for Haskell. 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` hierarchy. `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:

``````class Additive a where
{-# MINIMAL azero, (+) #-}
azero :: a           -- the identity element over addition
(+)   :: a -> a -> a -- the addition

class Multiplicative a where
{-# MINIMAL midentity, (*) #-}
midentity :: a      -- the identity element over multiplication
(*) :: a -> a -> a  -- multiplication``````

Join Type Classes for courses and projects to get you started and make you an expert in FP with Haskell.