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.1, 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-12T23:16:43Z

Modules

[Index] [Quick Jump]

Flags

Manual Flags

NameDescriptionDefault
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

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for semirings-0.3.1.1

[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:

*-semirings

A *-semiring (pron. "star-semiring") is any semiring with an additional operation 'star' (read as "asteration"), such that:

A derived operation called "aplus" can be defined in terms of star by:

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:

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