| License | MIT |
|---|---|
| Maintainer | mail@doisinkidney.com |
| Stability | experimental |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.Semiring
Description
- class Semiring a where
- class Semiring a => StarSemiring a where
- mulFoldable :: (Foldable f, Semiring a) => f a -> a
- addFoldable :: (Foldable f, Semiring a) => f a -> a
- class HasPositiveInfinity a where
- class HasNegativeInfinity a where
- class Semiring a => DetectableZero a where
- newtype Add a = Add {
- getAdd :: a
- newtype Mul a = Mul {
- getMul :: a
- newtype Max a = Max {
- getMax :: a
- newtype Min a = Min {
- getMin :: a
- newtype Matrix f g a = Matrix {
- getMatrix :: f (g a)
- transpose :: (Applicative g, Traversable f) => Matrix f g a -> Matrix g f a
- mulMatrix :: (Applicative n, Traversable m, Applicative m, Applicative p, Semiring a) => n (m a) -> m (p a) -> n (p a)
- rows :: (Foldable f, Foldable g) => Matrix f g a -> [[a]]
- cols :: (Foldable f, Foldable g) => Matrix f g a -> [[a]]
Semiring classes
class Semiring a where Source #
A Semiring is like the
the combination of two Monoids. 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<+>z x<=y => x<+>z<=y<+>zzero<=z&&x<=y => x<.>z<=y<.>z&&z<.>x<=z<.>y
Methods
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.
Instances
class Semiring a => StarSemiring a where Source #
A Star semiring
adds one operation, star to a Semiring, such that it follows the
law:
starx =one<+>x<.>starx =one<+>starx<.>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:
plusx = x<.>starx
This should be recognizable as a non-empty list on types, or the
some operation in
Alternative.
Instances
mulFoldable :: (Foldable f, Semiring a) => f a -> a Source #
The product of the contents of a Foldable.
Helper classes
class HasPositiveInfinity a where Source #
A class for semirings with a concept of "infinity". It's important that
this isn't regarded as the same as "bounded":
x should probably equal <+> positiveInfinitypositiveInfinity.
Minimal complete definition
Methods
positiveInfinity :: a Source #
A positive infinite value
isPositiveInfinity :: a -> Bool Source #
Test if a value is positive infinity.
class HasNegativeInfinity a where Source #
A class for semirings with a concept of "negative infinity". It's important
that this isn't regarded as the same as "bounded":
x should probably equal <+> negativeInfinitynegativeInfinity.
Minimal complete definition
Methods
negativeInfinity :: a Source #
A negative infinite value
isNegativeInfinity :: a -> Bool Source #
Test if a value is negative infinity.
class Semiring a => DetectableZero a where Source #
Useful for operations where zeroes may need to be discarded: for instance in sparse matrix calculations.
Minimal complete definition
Instances
Monoidal wrappers
Instances
| Functor Add Source # | |
| Foldable Add Source # | |
| Traversable Add Source # | |
| Generic1 Add Source # | |
| Eq1 Add Source # | |
| Ord1 Add Source # | |
| Read1 Add Source # | |
| Show1 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 # | |
| DetectableZero a => DetectableZero (Add a) Source # | |
| StarSemiring a => StarSemiring (Add a) Source # | |
| Semiring a => Semiring (Add a) Source # | |
| type Rep1 Add Source # | |
| type Rep (Add a) Source # | |
Instances
| Functor Mul Source # | |
| Foldable Mul Source # | |
| Traversable Mul Source # | |
| Generic1 Mul Source # | |
| Eq1 Mul Source # | |
| Ord1 Mul Source # | |
| Read1 Mul Source # | |
| Show1 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 # | |
| DetectableZero a => DetectableZero (Mul a) Source # | |
| StarSemiring a => StarSemiring (Mul a) Source # | |
| Semiring a => Semiring (Mul a) Source # | |
| type Rep1 Mul Source # | |
| type Rep (Mul a) Source # | |
Ordering wrappers
The "Arctic" or max-plus semiring. It is a semiring where:
<+>=maxzero= -∞<.>=<+>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
negativeInfinity to represent it follows the law.
Instances
The "Tropical" or min-plus semiring. It is a semiring where:
<+>=minzero= ∞<.>=<+>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 positiveInfinity
to represent it follows the law.
Instances
Matrix wrapper
A suitable definition of a square matrix for certain types which are both
Applicative and Traversable. For instance, given a type like so:
>>>:{data Quad a = Quad a a a a deriving Show instance Functor Quad where fmap f (Quad w x y z) = Quad (f w) (f x) (f y) (f z) instance Applicative Quad where pure x = Quad x x x x Quad fw fx fy fz <*> Quad xw xx xy xz = Quad (fw xw) (fx xx) (fy xy) (fz xz) instance Foldable Quad where foldr f b (Quad w x y z) = f w (f x (f y (f z b))) instance Traversable Quad where traverse f (Quad w x y z) = Quad <$> f w <*> f x <*> f y <*> f z :}
The newtype performs as you would expect:
>>>getMatrix one :: Quad (Quad Integer)Quad (Quad 1 0 0 0) (Quad 0 1 0 0) (Quad 0 0 1 0) (Quad 0 0 0 1)
ZipLists are another type which works with this newtype:
>>>:{let xs = (Matrix . ZipList . map ZipList) [[1,2],[3,4]] ys = (Matrix . ZipList . map ZipList) [[5,6],[7,8]] in (map getZipList . getZipList . getMatrix) (xs <.> ys) :} [[19,22],[43,50]]
Instances
transpose :: (Applicative g, Traversable f) => Matrix f g a -> Matrix g f a Source #
Transpose the matrix.
mulMatrix :: (Applicative n, Traversable m, Applicative m, Applicative p, Semiring a) => n (m a) -> m (p a) -> n (p a) Source #
Multiply two matrices.