semirings

two monoids as one, in holy haskimony http://github.com/chessai/semirings

Version on this page:0.1.3.0
LTS Haskell 15.14:0.5.3
Stackage Nightly 2020-05-30:0.5.3
Latest on Hackage:0.5.3

See all snapshots semirings appears in

BSD-3-Clause licensed by chessai
Maintained by chessai

Module documentation for 0.1.3.0

This version can be pinned in stack with:[email protected]:376d1fdb9e2e755d64a3feb559f71017c1095fb6683dbbb8daeaf34be6af6950,3406

There are no documented modules for this package.

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

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

Changes

0.1.3.0: [2018.05.23]

  • remove dependency on constrictor.
  • some doc fixes.

0.1.2: [2018.05.04]

  • semirings now builds back to GHC-7.4.1.
  • many doc fixes.

0.1.1: [2018.04.20]

  • Remove unused coerce-util dependency.

0.1.0:

  • Initial version.