semirings
two monoids as one, in holy haskimony
http://github.com/chessai/semirings
Version on this page: | 0.6 |
LTS Haskell 23.0: | 0.7 |
Stackage Nightly 2024-12-13: | 0.7 |
Latest on Hackage: | 0.7 |
semirings-0.6@sha256:9a93e426449e440b727d497a53cd5df8962711e90c000bbda005bc2c667e8e78,2569
Module documentation for 0.6
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.6: [2021-01-07]
- Remove hashable flag (only necessary was unordered-containers flag)
- Drop redundant
Eq
constraint on default definition ofcoprime
- Document (lack of guaranteed) rounding behaviour of quotRem
- Fix totally broken Ord instance for Tropical
- Stop depending on integer-gmp
0.5.4: [2020.07.13]
- Drop support for GHCs prior to 7.10
- Add default quotRem implementation
- Expose Data.Semiring.Generic.gfromNatural
0.5.3: [2020.02.18]
- Fix non-terminating GenericSemiring instances
- Fix incorrect implementation of gtimes’ for product types in GSemiring
- Implement GcdDomain.divide explicitly
- Remove redundant imports
- Disambiguate all haddock identifiers
0.5.2: [2019.11.01]
- Add
gcdExt
function - Bump upper bound on base
- Add GcdDomain/Euclidean instances for
Mod2
- Add GcdDomain/Euclidean instances for {Int|Word}{8|16|32|64}
- Mention
RebindableSyntax
in haddocks
rev: b4334fe06635f106b1f08bac127c1ae259cddae6
0.5.1: [2019.09.13]
- Bump upper bound on containers to 0.7
- Bump upper bound on hashable to 1.4
- Remove redundant constraints from WrappedFractional instances
- Add lower bound on semigroups
rev: 7e6f5e312bec5495ce9390664578bfb09d6e3eb9
0.5: [2019.09.05]
- Add
Field
typeclass, instances, and functions. - Add
Euclidean
andGcdDomain
instances for()
,CDouble
,CFloat
, andComplex
. - Add
Ring
andBits
instances forWrappedFractional
andWrappedIntegral
. - Add
fromInteger
andfromIntegral
functions forRing
.
rev: eb2617d93d354085fe5b706a145108d090dbc027
0.4.2: [2019.06.06]
- Add
GcdDomain
andEuclidean
typeclasses. - Add
Mod2
, the integers modulo 2, along with its Semiring/Ring/Star instances.
rev: b5af2fa403c68a66a3282b2a452b9be1c98e3fd6
0.4.1: [2019.05.04]
- Remove unlawful and useless
Ring
instance forGHC.Natural.Natural
. - Correct behaviour/docs of Data.Semiring.(^)
rev: d6c42aeea602499e32081e84974910d0fe955db6
0.4: [2019.05.01]
- Remove unlawful instances of
Ring
(thanks to @Bodigrim for noticing these) - Add
fromNatural
toSemiring
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.
rev: 1285d3e42242db310083fbf78d2e611bccecc63a
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.
rev: 13d4b3920912f8030b5d47777fb57b6e0dd15c10
0.3.1.1: [2019.01.12]
- Fix build error caused by disabling building with containers.
rev: 5f02279613bfcd20c2e9d68f01d669e563540ced
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
rev: 68c604250e2cf5688b3c641fd40b66fe7e1d45bf
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
andIntMap
. - Remove
Semiring
andRing
instances forProduct
andSum
. - Make
sum
andproduct
more efficient for base>=4.7
rev: d7d47c3db82a8e85330bb138169b9783eb346f38
0.2.1.1: [2018.10.01]
- Fixed build on GHC-7.4
- Provide
Semiring
andRing
for an arbitraryNum
viaWrappedNum
newtype. - Make note of
Semiring
semantics forVector
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
^
.
rev: e9b85d8aa6a238d07a061402f0ba365190eee7aa
0.2.1.0: [2018.09.26]
- Removed use of DefaultSignatures
- Removed free semiring
rev: 68e97e82280a50c374f50500a73222a5432cc45e
0.2.0.1: [2018.07.28]
- Add instances for
Op
,Equivalence
,Comparison
, andPredicate
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.
rev: 60869059d2959676877c9661427814b2bafd5d97
0.2.0.0: [2018.07.23]
- Fixed the
Semiring
instances ofSet
,HashSet
,Vector
,Storable Vector
,Unboxed Vector
. - Removed the
Semiring
instances ofSeq
,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’
rev: b985dcf37b919facc2dfbec66ea923ca5427c9f6
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.