semirings: two monoids as one, in holy haskimony

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

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]
Versions [faq] 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.2, 0.4, 0.4.1, 0.4.2
Change log CHANGELOG.md
Dependencies base (>=4.5 && <5), containers (>=0.5.4 && <0.6.1.0), hashable (>=1.1 && <1.4), integer-gmp, nats (>=0.1 && <2), semigroups, tagged, transformers, unordered-containers (==0.2.*) [details]
License BSD-3-Clause
Copyright Copyright (C) 2018 chessai
Author chessai
Maintainer chessai <chessai1996@gmail.com>
Revised Revision 1 made by ErikDeCastroLopo at Fri Jun 21 06:06:19 UTC 2019
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 Thu Jun 6 19:49:51 UTC 2019
Distributions LTSHaskell:0.2.1.1, NixOS:0.4.2, Stackage:0.4.2
Downloads 2408 total (360 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2019-06-06 [all 1 reports]

Modules

[Index] [Quick Jump]

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.

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

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

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

For package maintainers and hackage trustees


Readme for semirings-0.4.2

[back to package description]

semirings

Hackage Build Status

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