Haskellers are usually familiar with monoids and semigroups. A monoid has an appending operation
mappend and an identity element
mempty. A semigroup has an append
<>, but does not require an
A Semiring has two appending operations, ‘plus’ and ‘times’, and two respective identity elements, ‘zero’ and ‘one’.
More formally, A semiring R is a set equipped with two binary relations + and *, such that:
- (R, +) is a commutative monoid with identity element 0:
- (a + b) + c = a + (b + c)
- 0 + a = a + 0 = a
- a + b = b + a
- (R, *) is a monoid with identity element 1:
- (a * b) * c = a * (b * c)
- 1 * a = a * 1 = a
- Multiplication left and right distributes over addition
- a * (b + c) = (a * b) + (a * c)
- (a + b) * c = (a * c) + (b * c)
- Multiplication by ‘0’ annihilates R:
- 0 * a = a * 0 = 0
A *-semiring (pron. “star-semiring”) is any semiring with an additional operation ‘star’ (read as “asteration”), such that:
- star a = 1 + a * star a = 1 + star a * a
A derived operation called “aplus” can be defined in terms of star by:
- star :: a -> a
- star a = 1 + aplus a
- aplus :: a -> a
- aplus a = a * star a
As such, a minimal instance of the typeclass ‘Star’ requires only ‘star’ or ‘aplus’ to be defined.
semirings themselves are useful as a way to express that a type is both a commutative and associative monoid.
*-semirings are useful in a number of applications; such as matrix algebra, regular expressions, kleene algebras, graph theory, tropical algebra, dataflow analysis, power series, linear recurrence relations.
Some relevant (informal) reading material:
Some of the code in this library was lifted directly from the Haskell library ‘semiring-num’.
- Fixed build on GHC-7.4
Ringfor an arbitrary
- Removed use of DefaultSignatures
- Removed free semiring
- Add instances for
Predicatefrom Data.Functor.Contravariant (upcoming base 22.214.171.124)
- docfix for (prod -> product, prod’ -> product’)
- Fixed the
- Removed the
- Added comprehensive test suite that tests all
Semiringinstances defined in Data.Semiring
- Added Free semiring (Data.Semiring.Free)
- Added newtypes:
- Bounds for containers: [0.3,0.6] -> [0.5.4,0.6.0.9]
- Add semiring instance for
- names changed: (prod -> product, prod’ -> product’)
- sum’ and product’ now use foldl’ instead of foldr’
semiringsnow builds back to GHC-7.4.1.
- many doc fixes.
- Remove unused
- Initial version.