License | MIT |
---|---|
Maintainer | mail@doisinkidney.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
- class Semiring a where
- class Semiring a => StarSemiring a where
- class HasPositiveInfinity a where
- class HasNegativeInfinity a where
- data PositiveInfinite a
- = PosFinite !a
- | PositiveInfinity
- data NegativeInfinite a
- = NegativeInfinity
- | NegFinite !a
- data Infinite a
- newtype Add a = Add {
- getAdd :: a
- newtype Mul a = Mul {
- getMul :: a
- add :: (Foldable f, Semiring a) => f a -> a
- mul :: (Foldable f, Semiring a) => f a -> a
- newtype Max a = Max {
- getMax :: a
- newtype Min a = Min {
- getMin :: a
Documentation
class Semiring a where Source #
A Semiring is like the
the combination of two Monoid
s. The first
is called <+>
; it has the identity element zero
, and it is
commutative. The second is called <.>
; it has identity element one
,
and it must distribute over <+>
.
Laws
Normal Monoid
laws
(a<+>
b)<+>
c = a<+>
(b<+>
c)zero
<+>
a = a<+>
zero
= a (a<.>
b)<.>
c = a<.>
(b<.>
c)one
<.>
a = a<.>
one
= a
Commutativity of <+>
a<+>
b = b<+>
a
Distribution of <.>
over <+>
a<.>
(b<+>
c) = (a<.>
b)<+>
(a<.>
c) (a<+>
b)<.>
c = (a<.>
c)<+>
(b<.>
c)
Annihilation
zero
<.>
a = a<.>
zero
=zero
An ordered semiring follows the laws:
x
<=
y => x <+>
z <=
y <+>
zx
<=
y => x <+>
z <=
y <+>
zzero
<=
z &&
x <=
y => x <.>
z <=
y <.>
z &&
z <.>
x <=
z <.>
y
The identity of <+>
.
The identity of <.>
.
(<.>) :: a -> a -> a infixl 7 Source #
An associative binary operation, which distributes over <+>
.
(<+>) :: a -> a -> a infixl 6 Source #
An associative, commutative binary operation.
The identity of <+>
.
The identity of <.>
.
(<+>) :: Num a => a -> a -> a infixl 6 Source #
An associative, commutative binary operation.
(<.>) :: Num a => a -> a -> a infixl 7 Source #
An associative binary operation, which distributes over <+>
.
class Semiring a => StarSemiring a where Source #
A Star semiring
adds one operation, star
to a Semiring
, such that it follows the
law:
star
x =one
<+>
x<.>
star
x =one
<+>
star
x<.>
x
For the semiring of types, this is equivalent to a list. When looking
at the Applicative
and Alternative
classes as
(near-) semirings, this is equivalent to the
many
operation.
Another operation, plus
, can be defined in relation to star
:
plus
x = x<.>
star
x
This should be recognizable as a non-empty list on types, or the
some
operation in
Alternative
.
class HasPositiveInfinity a where Source #
positiveInfinity :: a Source #
positiveInfinity :: RealFloat a => a Source #
class HasNegativeInfinity a where Source #
negativeInfinity :: a Source #
negativeInfinity :: RealFloat a => a Source #
data PositiveInfinite a Source #
Functor PositiveInfinite Source # | |
Applicative PositiveInfinite Source # | |
Foldable PositiveInfinite Source # | |
Traversable PositiveInfinite Source # | |
Generic1 PositiveInfinite Source # | |
Bounded a => Bounded (PositiveInfinite a) Source # | |
(Enum a, Bounded a, Eq a) => Enum (PositiveInfinite a) Source # | |
Eq a => Eq (PositiveInfinite a) Source # | |
Num a => Num (PositiveInfinite a) Source # | |
Ord a => Ord (PositiveInfinite a) Source # | |
Read a => Read (PositiveInfinite a) Source # | |
Show a => Show (PositiveInfinite a) Source # | |
Generic (PositiveInfinite a) Source # | |
Monoid a => Monoid (PositiveInfinite a) Source # | |
Storable a => Storable (PositiveInfinite a) Source # | |
HasPositiveInfinity (PositiveInfinite a) Source # | |
(Eq a, Semiring a) => StarSemiring (PositiveInfinite a) Source # | |
Semiring a => Semiring (PositiveInfinite a) Source # | Not lawful. Only for convenience. |
type Rep1 PositiveInfinite Source # | |
type Rep (PositiveInfinite a) Source # | |
data NegativeInfinite a Source #
Functor NegativeInfinite Source # | |
Applicative NegativeInfinite Source # | |
Foldable NegativeInfinite Source # | |
Traversable NegativeInfinite Source # | |
Generic1 NegativeInfinite Source # | |
Bounded a => Bounded (NegativeInfinite a) Source # | |
(Enum a, Bounded a, Eq a) => Enum (NegativeInfinite a) Source # | |
Eq a => Eq (NegativeInfinite a) Source # | |
Num a => Num (NegativeInfinite a) Source # | |
Ord a => Ord (NegativeInfinite a) Source # | |
Read a => Read (NegativeInfinite a) Source # | |
Show a => Show (NegativeInfinite a) Source # | |
Generic (NegativeInfinite a) Source # | |
Monoid a => Monoid (NegativeInfinite a) Source # | |
Storable a => Storable (NegativeInfinite a) Source # | |
HasNegativeInfinity (NegativeInfinite a) Source # | |
Semiring a => Semiring (NegativeInfinite a) Source # | Not lawful. Only for convenience. |
type Rep1 NegativeInfinite Source # | |
type Rep (NegativeInfinite a) Source # | |
Functor Infinite Source # | |
Applicative Infinite Source # | |
Foldable Infinite Source # | |
Traversable Infinite Source # | |
Generic1 Infinite Source # | |
Bounded (Infinite a) Source # | |
(Enum a, Bounded a, Eq a) => Enum (Infinite a) Source # | |
Eq a => Eq (Infinite a) Source # | |
Num a => Num (Infinite a) Source # | |
Ord a => Ord (Infinite a) Source # | |
Read a => Read (Infinite a) Source # | |
Show a => Show (Infinite a) Source # | |
Generic (Infinite a) Source # | |
Monoid a => Monoid (Infinite a) Source # | |
Storable a => Storable (Infinite a) Source # | |
HasNegativeInfinity (Infinite a) Source # | |
HasPositiveInfinity (Infinite a) Source # | |
Semiring a => Semiring (Infinite a) Source # | Not lawful. Only for convenience. |
type Rep1 Infinite Source # | |
type Rep (Infinite a) Source # | |
Functor Add Source # | |
Foldable Add Source # | |
Traversable Add Source # | |
Generic1 Add Source # | |
Bounded a => Bounded (Add a) Source # | |
Enum a => Enum (Add a) Source # | |
Eq a => Eq (Add a) Source # | |
Fractional a => Fractional (Add a) Source # | |
Num a => Num (Add a) Source # | |
Ord a => Ord (Add a) Source # | |
Read a => Read (Add a) Source # | |
Real a => Real (Add a) Source # | |
RealFrac a => RealFrac (Add a) Source # | |
Show a => Show (Add a) Source # | |
Generic (Add a) Source # | |
Semiring a => Semigroup (Add a) Source # | |
Semiring a => Monoid (Add a) Source # | |
Storable a => Storable (Add a) Source # | |
StarSemiring a => StarSemiring (Add a) Source # | |
Semiring a => Semiring (Add a) Source # | |
type Rep1 Add Source # | |
type Rep (Add a) Source # | |
Functor Mul Source # | |
Foldable Mul Source # | |
Traversable Mul Source # | |
Generic1 Mul Source # | |
Bounded a => Bounded (Mul a) Source # | |
Enum a => Enum (Mul a) Source # | |
Eq a => Eq (Mul a) Source # | |
Fractional a => Fractional (Mul a) Source # | |
Num a => Num (Mul a) Source # | |
Ord a => Ord (Mul a) Source # | |
Read a => Read (Mul a) Source # | |
Real a => Real (Mul a) Source # | |
RealFrac a => RealFrac (Mul a) Source # | |
Show a => Show (Mul a) Source # | |
Generic (Mul a) Source # | |
Semiring a => Semigroup (Mul a) Source # | |
Semiring a => Monoid (Mul a) Source # | |
Storable a => Storable (Mul a) Source # | |
StarSemiring a => StarSemiring (Mul a) Source # | |
Semiring a => Semiring (Mul a) Source # | |
type Rep1 Mul Source # | |
type Rep (Mul a) Source # | |
The "Arctic" or max-plus semiring. It is a semiring where:
<+>
=max
zero
= -∞ -- represented byNothing
<.>
=<+>
one
=zero
Note that we can't use Max
from Semigroup
because annihilation needs to hold:
-∞<+>
x = x<+>
-∞ = -∞
Taking -∞ to be minBound
would break the above law. Using Nothing
to represent it follows the law.
Functor Max Source # | |
Foldable Max Source # | |
Traversable Max Source # | |
Generic1 Max Source # | |
Bounded a => Bounded (Max a) Source # | |
Enum a => Enum (Max a) Source # | |
Eq a => Eq (Max a) Source # | |
Fractional a => Fractional (Max a) Source # | |
Num a => Num (Max a) Source # | |
Ord a => Ord (Max a) Source # | |
Read a => Read (Max a) Source # | |
Real a => Real (Max a) Source # | |
RealFrac a => RealFrac (Max a) Source # | |
Show a => Show (Max a) Source # | |
Generic (Max a) Source # | |
Ord a => Semigroup (Max a) Source # | |
(Ord a, HasNegativeInfinity a) => Monoid (Max a) Source # |
|
Storable a => Storable (Max a) Source # | |
(Semiring a, Ord a, HasPositiveInfinity a, HasNegativeInfinity a) => StarSemiring (Max a) Source # | |
(Semiring a, Ord a, HasNegativeInfinity a) => Semiring (Max a) Source # | |
type Rep1 Max Source # | |
type Rep (Max a) Source # | |
The "Tropical" or min-plus semiring. It is a semiring where:
<+>
=min
zero
= ∞ -- represented byNothing
<.>
=<+>
one
=zero
Note that we can't use Min
from Semigroup
because annihilation needs to hold:
∞<+>
x = x<+>
∞ = ∞
Taking ∞ to be maxBound
would break the above law. Using Nothing
to represent it follows the law.
Functor Min Source # | |
Foldable Min Source # | |
Traversable Min Source # | |
Generic1 Min Source # | |
Bounded a => Bounded (Min a) Source # | |
Enum a => Enum (Min a) Source # | |
Eq a => Eq (Min a) Source # | |
Fractional a => Fractional (Min a) Source # | |
Num a => Num (Min a) Source # | |
Ord a => Ord (Min a) Source # | |
Read a => Read (Min a) Source # | |
Real a => Real (Min a) Source # | |
RealFrac a => RealFrac (Min a) Source # | |
Show a => Show (Min a) Source # | |
Generic (Min a) Source # | |
Ord a => Semigroup (Min a) Source # | |
(Ord a, HasPositiveInfinity a) => Monoid (Min a) Source # |
|
Storable a => Storable (Min a) Source # | |
(Semiring a, Ord a, HasPositiveInfinity a, HasNegativeInfinity a) => StarSemiring (Min a) Source # | |
(Semiring a, Ord a, HasPositiveInfinity a) => Semiring (Min a) Source # | |
type Rep1 Min Source # | |
type Rep (Min a) Source # | |