Hackage :: [Package]

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]

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

Candidates

Versions [RSS] 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, 0.5, 0.5.1, 0.5.2, 0.5.3, 0.5.4, 0.6
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:54Z
Distributions Arch:0.6, LTSHaskell:0.6, NixOS:0.6, Stackage:0.6
Reverse Dependencies 18 direct, 7741 indirect [details]
Downloads 19770 total (184 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2019-01-12 [all 1 reports]

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:

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