Semiring

Monoid
Alternative
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
Tags

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

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