# semirings

two monoids as one, in holy haskimony http://github.com/chessai/semirings

Version on this page: | 0.2.1.1 |

LTS Haskell 13.17: | 0.2.1.1 |

Stackage Nightly 2019-04-19: | 0.3.1.2 |

Latest on Hackage: | 0.3.1.2 |

**chessai**

**chessai**

#### Module documentation for 0.2.1.1

# 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 that supports a commutative and associative operation. Some examples:

- Numbers {Int, Integer, Word, Double, etc.}:
- ‘plus’ is ‘Prelude.+’
- ‘times’ is ‘Prelude.*’
- ‘zero’ is 0.
- ‘one’ is 1.

- Booleans:
- ‘plus’ is ‘||’
- ‘times’ is ‘&&’
- ‘zero’ is ‘False’
- ‘one’ is ‘True’

- Set:
- ‘plus’ is ‘union’
- ‘times’ is ‘intersection’
- ‘zero’ is the empty Set.
- ‘one’ is the singleton Set containing the ‘one’ element of the underlying type.

- NFA:
- ‘plus’ unions two NFAs.
- ‘times’ appends two NFAs.
- ‘zero’ is the NFA that acceptings nothing.
- ‘one’ is the empty NFA.

- DFA:
- ‘plus’ unions two DFAs.
- ‘times’ intersects two DFAs.
- ‘zero’ is the DFA that accepts nothing.
- ‘one’ is the DFA that accepts everything.

*-semirings are useful in a number of applications; such as matrix algebra, regular expressions, kleene algebras, graph theory, tropical algebra, dataflow analysis, power series, and linear recurrence relations.

Some relevant (informal) reading material:

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/

# additional credit

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

## Changes

## 0.3.1.2: [2019.04.02]

- Fix build error on windows caused by providing instances to POSIX types. Thanks to @Bodigrim and @CarlEdman for reporting this.

## 0.3.1.1: [2019.01.12]

- Fix build error caused by disabling building with containers.

## 0.3.1.0: [2019.01.12]

- Add Data.Semiring.Tropical
- Fix build problem on GHC 7.4 caused by introduction of IntSetOf/IntMapOf
- Make sure there are no warnings when building with -Wall, for any GHC

## 0.3.0.0: [2019.01.01]

- Rename the test suite to make
`stack`

happy. - Clarified documentation. See #26.
- Simplify implementation of
`^`

. See #24. - Add ‘GenericSemiring’, a newtype wrapper meant to be used with
`-XDerivingVia`

, helping avoid ‘-XDefaultSignatures’. - Add newtypes for
`IntSet`

and`IntMap`

. - Remove
`Semiring`

and`Ring`

instances for`Product`

and`Sum`

. - Make
`sum`

and`product`

more efficient for base>=4.7

## 0.2.1.1: [2018.10.01]

- Fixed build on GHC-7.4
- Provide
`Semiring`

and`Ring`

for an arbitrary`Num`

via`WrappedNum`

newtype. - Make note of
`Semiring`

semantics for`Vector`

and`[]`

in the documentation. - Require build script to ensure
`semirings`

builds with GHC-8.4.3 and GHC-8.6.1 - Fixed unlawful behaviour of
`[]`

`Semiring`

instance. - Improve performance of
`^`

.

## 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’) change that occured in version 0.2.0.0.

## 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 Free semiring (Data.Semiring.Free)
- 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.