# semirings: two monoids as one, in holy haskimony

[ algebra, bsd3, data, data-structures, library, math, mathematics, maths ] [ Propose Tags ]

In mathematics, a semiring is an algebraic structure consisting of a set together with two binary operations, one commutative and one associative. A semiring has two identity elements respective to its operations. Thus a semiring can be seen as a combination of two monoids, a commutative monoid and an associative monoid. For some useful semirings, see the semirings-types package.

Versions 0.0.0, 0.1.0, 0.1.1, 0.1.2, 0.1.3.0 CHANGELOG.md base (>=4.5 && <5), containers (>=0.3 && <0.6), hashable (>=1.1 && <1.3), integer-gmp, nats (>=0.1 && <2), semigroups, transformers, unordered-containers (==0.2.*), vector (>=0.7 && <0.13.0.0) [details] BSD-3-Clause Copyright (C) 2018 chessai chessai chessai Algebra, Data, Data Structures, Math, Maths, Mathematics http://github.com/chessai/semirings http://github.com/chessai/semirings/issues head: git clone git://github.com/chessai/semirings.git by chessai at Thu May 24 02:44:21 UTC 2018 NixOS:0.1.3.0 176 total (28 in the last 30 days) (no votes yet) [estimated by rule of succession] λ λ λ Docs available Last success reported on 2018-05-24 Hackage Matrix CI

[Index]

• Data

## Flags

NameDescriptionDefaultType
hashable

You can disable the use of the hashable package using -f-hashable.

Disabling this may be useful for accelerating builds in sandboxes for expert users.

If disabled we will not supply instances of Hashable

Note: -f-hashable implies -f-unordered-containers, as we are necessarily not able to supply those instances as well.

EnabledManual
containers

You can disable the use of the containers package using -f-containers.

Disabling this may be useful for accelerating builds in sandboxes for expert users.

EnabledManual
unordered-containers

You can disable the use of the unordered-containers package using -f-unordered-containers.

Disabling this may be useful for accelerating builds in sandboxes for expert users.

EnabledManual
vector

You can disable the use of the vector package using -f-vector.

Disabling this may be useful for accelerating builds in sandboxes for expert users. default: True manual: True

EnabledAutomatic

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

#### Maintainer's Corner

For package maintainers and hackage trustees

[back to package description]

# 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 <i>R</i> 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.