# semirings

two monoids as one, in holy haskimony

http://github.com/chessai/semirings

 Version on this page: 0.2.1.1 LTS Haskell 21.23: 0.6@rev:1 Stackage Nightly 2023-12-08: 0.6@rev:1 Latest on Hackage: 0.6@rev:1

See all snapshots `semirings` appears in

Maintained by
This version can be pinned in stack with:`semirings-0.2.1.1@sha256:83bdfd8d3abf2e404056dbc70da02d05d68fdc87fdbaa63d06f815155947e7e2,3376`

#### Module documentation for 0.2.1.1

There are no documented modules for this package.

Depends on 6 packages(full list with versions):
Used by 1 package in lts-13.19(full list with versions):

# semirings

Haskellers are usually familiar with monoids and semigroups. A monoid has an appending operation `<>` or `mappend` and an identity element `mempty`. A semigroup has an append `<>`, but does not require an `mempty` element.

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

# *-semirings

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.

# use cases

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.

http://stedolan.net/research/semirings.pdf

http://r6.ca/blog/20110808T035622Z.html

https://byorgey.wordpress.com/2016/04/05/the-network-reliability-problem-and-star-semirings/

Some of the code in this library was lifted directly from the Haskell library ‘semiring-num’.

## 0.2.1.1: [2018.XX.XX]

• Fixed build on GHC-7.4
• Provide `Semiring` and `Ring` for an arbitrary `Num` via `WrappedNum` newtype.

## 0.2.1.0: [2018.09.26]

• Removed use of DefaultSignatures
• Removed free semiring

## 0.2.0.1: [2018.07.28]

• Add instances for `Op`, `Equivalence`, `Comparison`, and `Predicate` from Data.Functor.Contravariant (upcoming base 4.12.0.0)
• docfix for (prod -> product, prod’ -> product’)

## 0.2.0.0: [2018.07.23]

• Fixed the `Semiring` instances of `Set`, `HashSet`, `Vector`, `Storable Vector`, `Unboxed Vector`.
• Removed the `Semiring` instances of `Seq`, `Alt`, `Endo`.
• Added comprehensive test suite that tests all `Semiring` instances defined in Data.Semiring
• Added newtypes: `Add`, `Mul`
• Bounds for containers: [0.3,0.6] -> [0.5.4,0.6.0.9]
• Add semiring instance for `Proxy`
• names changed: (prod -> product, prod’ -> product’)
• sum’ and product’ now use foldl’ instead of foldr’

## 0.1.2: [2018.05.04]

• `semirings` now builds back to GHC-7.4.1.
• many doc fixes.

## 0.1.1: [2018.04.20]

• Remove unused `coerce-util` dependency.

## 0.1.0:

• Initial version.