1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
semirings
==========
[](https://hackage.haskell.org/package/semirings) [](https://travis-ci.org/chessai/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'.
|
