License | MIT |
---|---|
Maintainer | mail@doisinkidney.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
- 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 f, Traversable g, Applicative g, Semiring a) => Matrix f g a -> Matrix g f a -> Matrix f f a
Semiring classes
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<+>
z x<=
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.
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
.
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 <+>
positiveInfinity
positiveInfinity
.
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 <+>
negativeInfinity
negativeInfinity
.
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.
Monoidal wrappers
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 # | |
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:
<+>
=max
zero
= -∞<.>
=<+>
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.
Functor Max Source # | |
Foldable Max Source # | |
Traversable Max Source # | |
Generic1 Max Source # | |
Eq1 Max Source # | |
Ord1 Max Source # | |
Read1 Max Source # | |
Show1 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, HasNegativeInfinity a) => DetectableZero (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
= ∞<.>
=<+>
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.
Functor Min Source # | |
Foldable Min Source # | |
Traversable Min Source # | |
Generic1 Min Source # | |
Eq1 Min Source # | |
Ord1 Min Source # | |
Read1 Min Source # | |
Show1 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) => DetectableZero (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 # | |
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)
ZipList
s 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]]
transpose :: (Applicative g, Traversable f) => Matrix f g a -> Matrix g f a Source #
Transpose the matrix.
mulMatrix :: (Applicative f, Traversable g, Applicative g, Semiring a) => Matrix f g a -> Matrix g f a -> Matrix f f a Source #
Multiply two matrices.