Popularity
8.2
Declining
Activity
1.5
-
37
5
10

Monthly Downloads: 9
Programming language: Haskell
License: BSD 3-clause "New" or "Revised" License
Tags: Data    
Latest version: v0.5.4

star alternatives and similar packages

Based on the "Data" category.
Alternatively, view star alternatives based on common mentions on social networks and blogs.

Do you think we are missing an alternative of star or a related project?

Add another 'Data' Package

README

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