semirings

two monoids as one, in holy haskimony

http://github.com/chessai/semirings

Version on this page:0.4.1
LTS Haskell 24.28:0.7
Stackage Nightly 2026-01-14:0.7
Latest on Hackage:0.7

See all snapshots semirings appears in

BSD-3-Clause licensed by chessai
Maintained by chessai
This version can be pinned in stack with:semirings-0.4.1@sha256:329b37c855e9be4632ef5f5cdbc6dc2a6ad1cb358b2588e36471dbdd1136d45c,3592

Module documentation for 0.4.1

There are no documented modules for this package.

Used by 3 packages in nightly-2019-05-07(full list with versions):
arithmoi, fib, quickcheck-classes

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

Changes

0.4.1: [2019.05.04]

  • Remove unlawful and useless Ring instance for GHC.Natural.Natural.
  • Correct behaviour/docs of Data.Semiring.(^)

0.4: [2019.05.01]

  • Remove unlawful instances of Ring (thanks to @Bodigrim for noticing these)
  • Add fromNatural to Semiring typeclass (thanks @Bodigrim)
  • Remove Semiring/Ring instances for [] and Vector. (thanks @Bodigrim) These instances are better served by a dedicated polynomial package, which @Bodigrim has made at http://hackage.haskell.org/package/poly.
  • Add isZero/isOne predicates.

0.3.1.2: [2019.04.02]

  • Fix build error on windows caused by providing instances to POSIX types. Thanks to @Bodigrim and @CarlEdman for reporting this.

0.3.1.1: [2019.01.12]

  • Fix build error caused by disabling building with containers.

0.3.1.0: [2019.01.12]

  • Add Data.Semiring.Tropical
  • Fix build problem on GHC 7.4 caused by introduction of IntSetOf/IntMapOf
  • Make sure there are no warnings when building with -Wall, for any GHC

0.3.0.0: [2019.01.01]

  • Rename the test suite to make stack happy.
  • Clarified documentation. See #26.
  • Simplify implementation of ^. See #24.
  • Add ‘GenericSemiring’, a newtype wrapper meant to be used with -XDerivingVia, helping avoid ‘-XDefaultSignatures’.
  • Add newtypes for IntSet and IntMap.
  • Remove Semiring and Ring instances for Product and Sum.
  • Make sum and product more efficient for base>=4.7

0.2.1.1: [2018.10.01]

  • Fixed build on GHC-7.4
  • Provide Semiring and Ring for an arbitrary Num via WrappedNum newtype.
  • Make note of Semiring semantics for Vector and [] in the documentation.
  • Require build script to ensure semirings builds with GHC-8.4.3 and GHC-8.6.1
  • Fixed unlawful behaviour of [] Semiring instance.
  • Improve performance of ^.

0.2.1.0: [2018.09.26]

  • Removed use of DefaultSignatures
  • Removed free semiring

0.2.0.1: [2018.07.28]

  • Add instances for Op, Equivalence, Comparison, and Predicate from Data.Functor.Contravariant (upcoming base 4.12.0.0)
  • docfix for (prod -> product, prod’ -> product’) change that occured in version 0.2.0.0.

0.2.0.0: [2018.07.23]

  • Fixed the Semiring instances of Set, HashSet, Vector, Storable Vector, Unboxed Vector.
  • Removed the Semiring instances of Seq, Alt, Endo.
  • Added comprehensive test suite that tests all Semiring instances defined in Data.Semiring
  • Added Free semiring (Data.Semiring.Free)
  • Added newtypes: Add, Mul
  • Bounds for containers: [0.3,0.6] -> [0.5.4,0.6.0.9]
  • Add semiring instance for Proxy
  • names changed: (prod -> product, prod’ -> product’)
  • sum’ and product’ now use foldl’ instead of foldr’

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.