semirings: two monoids as one, in holy haskimony

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

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 appending <> operation, but does not require a 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,

(R,*) is a monoid with identity element 1,

(*) left and right distributes over addition, and

multiplication by '0' annihilates R.

[Skip to Readme]

Properties

Versions	0.0.0, 0.1.0, 0.1.1, 0.1.2, 0.1.3.0, 0.2.0.0, 0.2.0.1, 0.2.1.0, 0.2.1.1, 0.3.0.0, 0.3.1.0, 0.3.1.0, 0.3.1.1, 0.3.1.2, 0.4, 0.4.1, 0.4.2, 0.5, 0.5.1, 0.5.2, 0.5.3, 0.5.4, 0.6, 0.7
Change log	CHANGELOG.md
Dependencies	base (>=4.5 && <5), containers (>=0.5.4 && <0.6.1.0), hashable (>=1.1 && <1.3), integer-gmp, nats (>=0.1 && <2), semigroups, tagged, transformers, unordered-containers (>=0.2 && <0.3), vector (>=0.7 && <0.13.0.0) [details]
License	BSD-3-Clause
Copyright	Copyright (C) 2018 chessai
Author	chessai
Maintainer	chessai <chessai1996@gmail.com>
Category	Algebra, Data, Data Structures, Math, Maths, Mathematics
Home page	http://github.com/chessai/semirings
Bug tracker	http://github.com/chessai/semirings/issues
Source repo	head: git clone git://github.com/chessai/semirings.git
Uploaded	by chessai at 2019-01-12T22:58:45Z

Modules

[Index] [Quick Jump]

Data
- Data.Semiring
  - Data.Semiring.Generic
  - Data.Semiring.Tropical
- Data.Star

Flags

Manual Flags

Name	Description	Default
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. Note: `-f-hashable` implies `-f-unordered-containers`, as we are necessarily not able to supply those instances as well.	Enabled
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.	Enabled
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.	Enabled
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.	Enabled

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

Downloads

semirings-0.3.1.0.tar.gz [browse] (Cabal source package)
Package description (as included in the package)

Maintainer's Corner

Package maintainers

chessai

For package maintainers and hackage trustees

edit package information

Readme for semirings-0.3.1.0

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