Safe Haskell	None
Language	GHC2024

NumHask.Free.Carriers

Contents

Boolean semiring
Tropical semiring
Field semiring
Viterbi semiring

Description

Concrete semiring carriers useful for demonstrating StarSemiring.

These four carriers are the classic examples of the closed-semiring / algebraic-path-problem literature. They are still, fifty years on, the canonical trio plus the probabilistic addition:

Boolean semiring — reachability / transitive closure (Warshall 1962).
Min-plus semiring — shortest paths (Floyd 1962, Roy 1959, Warshall 1962).
Field semiring — matrix inversion via the Neumann series.
Viterbi semiring — maximum-probability paths.

The unification of path problems over semirings was introduced by Aho, Hopcroft and Ullman in /The Design and Analysis of Computer Algorithms/ (1974) and elaborated by Tarjan in "A Unified Approach to Path Problems" (JACM, 1981). A modern categorical treatment is given by Höfner and Möller in "Dijkstra, Floyd and Warshall Meet Kleene" (2012).

Synopsis

newtype Warshall = Warshall Bool
newtype MinPlus a = MinPlus {
- getMinPlus :: a
}
newtype FieldStar = FieldStar {
- unFieldStar :: Double
}
newtype Viterbi a = Viterbi {
- getViterbi :: a
}

Boolean semiring

newtype Warshall Source #

Boolean semiring for Warshall's transitive closure.

plus is ||, times is &&, star is constantly True.

>>> Warshall True + Warshall False
Warshall True

Constructors

Warshall Bool

Instances

Instances details

Eq Warshall Source #
Instance details Defined in NumHask.Free.Carriers Methods (==) :: Warshall -> Warshall -> Bool # (/=) :: Warshall -> Warshall -> Bool #
Ord Warshall Source #
Instance details Defined in NumHask.Free.Carriers Methods compare :: Warshall -> Warshall -> Ordering # (<) :: Warshall -> Warshall -> Bool # (<=) :: Warshall -> Warshall -> Bool # (>) :: Warshall -> Warshall -> Bool # (>=) :: Warshall -> Warshall -> Bool # max :: Warshall -> Warshall -> Warshall # min :: Warshall -> Warshall -> Warshall #
Show Warshall Source #
Instance details Defined in NumHask.Free.Carriers Methods showsPrec :: Int -> Warshall -> ShowS # show :: Warshall -> String # showList :: [Warshall] -> ShowS #
Additive Warshall Source #
Instance details Defined in NumHask.Free.Carriers Methods (+) :: Warshall -> Warshall -> Warshall Source # zero :: Warshall Source #
Idempotent Warshall Source #
Instance details Defined in NumHask.Free.Carriers
Magma Warshall Source #
Instance details Defined in NumHask.Free.Carriers Methods (⊕) :: Warshall -> Warshall -> Warshall Source #
CompleteJoinSemiLattice Warshall Source #
Instance details Defined in NumHask.Free.Carriers Methods joins :: Foldable f => f Warshall -> Warshall Source #
JoinSemiLattice Warshall Source #	Boolean join-semilattice structure: join is `\|\|`, bottom is `False`.
Instance details Defined in NumHask.Free.Carriers Methods (\/) :: Warshall -> Warshall -> Warshall Source #
LowerBounded Warshall Source #
Instance details Defined in NumHask.Free.Carriers Methods bottom :: Warshall Source #
Multiplicative Warshall Source #
Instance details Defined in NumHask.Free.Carriers Methods (*) :: Warshall -> Warshall -> Warshall Source # one :: Warshall Source #
Quantale Warshall Source #	Boolean quantale: join is disjunction, multiplication is conjunction.
Instance details Defined in NumHask.Algebra.Quantale
Residuated Warshall Source #	Boolean implication as the residual of conjunction. `>>>` `lres (Warshall True) (Warshall False)`Warshall False `>>>` `lres (Warshall False) (Warshall True)`Warshall True
Instance details Defined in NumHask.Algebra.Quantale Methods lres :: Warshall -> Warshall -> Warshall Source # rres :: Warshall -> Warshall -> Warshall Source #
StarAutonomous Warshall Source #	Boolean negation as complement; `par` is disjunction and `bot` is 'Warshall False'.
Instance details Defined in NumHask.Algebra.Quantale Methods neg :: Warshall -> Warshall Source # par :: Warshall -> Warshall -> Warshall Source # bot :: Warshall Source #
KleeneAlgebra Warshall Source #
Instance details Defined in NumHask.Free.Carriers
StarSemiring Warshall Source #	Boolean star is constantly true. `>>>` `star (Warshall False :: Warshall)`Warshall True
Instance details Defined in NumHask.Free.Carriers Methods star :: Warshall -> Warshall Source # plus :: Warshall -> Warshall Source #

Tropical semiring

newtype MinPlus a Source #

Tropical (min-plus) semiring for Floyd–Warshall shortest paths.

Addition is min, multiplication is ordinary addition, the additive unit is positive infinity, and the multiplicative unit is zero.

>>> MinPlus 3 + MinPlus 2 :: MinPlus Double
MinPlus {getMinPlus = 2.0}

>>> MinPlus 3 * MinPlus 2 :: MinPlus Double
MinPlus {getMinPlus = 5.0}

Constructors

MinPlus
Fields getMinPlus :: a

Instances

Instances details

Eq a => Eq (MinPlus a) Source #
Instance details Defined in NumHask.Free.Carriers Methods (==) :: MinPlus a -> MinPlus a -> Bool # (/=) :: MinPlus a -> MinPlus a -> Bool #
Ord a => Ord (MinPlus a) Source #
Instance details Defined in NumHask.Free.Carriers Methods compare :: MinPlus a -> MinPlus a -> Ordering # (<) :: MinPlus a -> MinPlus a -> Bool # (<=) :: MinPlus a -> MinPlus a -> Bool # (>) :: MinPlus a -> MinPlus a -> Bool # (>=) :: MinPlus a -> MinPlus a -> Bool # max :: MinPlus a -> MinPlus a -> MinPlus a # min :: MinPlus a -> MinPlus a -> MinPlus a #
Show a => Show (MinPlus a) Source #
Instance details Defined in NumHask.Free.Carriers Methods showsPrec :: Int -> MinPlus a -> ShowS # show :: MinPlus a -> String # showList :: [MinPlus a] -> ShowS #
Additive (MinPlus Double) Source #
Instance details Defined in NumHask.Free.Carriers Methods (+) :: MinPlus Double -> MinPlus Double -> MinPlus Double Source # zero :: MinPlus Double Source #
Idempotent (MinPlus Double) Source #
Instance details Defined in NumHask.Free.Carriers
Magma (MinPlus Double) Source #
Instance details Defined in NumHask.Free.Carriers Methods (⊕) :: MinPlus Double -> MinPlus Double -> MinPlus Double Source #
CompleteJoinSemiLattice (MinPlus Double) Source #
Instance details Defined in NumHask.Free.Carriers Methods joins :: Foldable f => f (MinPlus Double) -> MinPlus Double Source #
Ord a => JoinSemiLattice (MinPlus a) Source #	Tropical join-semilattice structure: join is `min`, bottom is positive infinity.
Instance details Defined in NumHask.Free.Carriers Methods (\/) :: MinPlus a -> MinPlus a -> MinPlus a Source #
LowerBounded (MinPlus Double) Source #
Instance details Defined in NumHask.Free.Carriers Methods bottom :: MinPlus Double Source #
Multiplicative (MinPlus Double) Source #
Instance details Defined in NumHask.Free.Carriers Methods (*) :: MinPlus Double -> MinPlus Double -> MinPlus Double Source # one :: MinPlus Double Source #
Quantale (MinPlus Double) Source #	Tropical (min-plus) quantale: join is minimum, bottom is positive infinity, multiplication is addition.
Instance details Defined in NumHask.Algebra.Quantale
Residuated (MinPlus Double) Source #	Tropical residual is truncated subtraction. `>>>` `getMinPlus (lres (MinPlus 2) (MinPlus 5) :: MinPlus Double)`3.0 `>>>` `getMinPlus (lres (MinPlus 5) (MinPlus 2) :: MinPlus Double)`-3.0
Instance details Defined in NumHask.Algebra.Quantale Methods lres :: MinPlus Double -> MinPlus Double -> MinPlus Double Source # rres :: MinPlus Double -> MinPlus Double -> MinPlus Double Source #
StarAutonomous (MinPlus Double) Source #	Tropical linear negation is additive inverse; `par` is addition and `bot` is the multiplicative unit `0`.
Instance details Defined in NumHask.Algebra.Quantale Methods neg :: MinPlus Double -> MinPlus Double Source # par :: MinPlus Double -> MinPlus Double -> MinPlus Double Source # bot :: MinPlus Double Source #
KleeneAlgebra (MinPlus Double) Source #
Instance details Defined in NumHask.Free.Carriers
StarSemiring (MinPlus Double) Source #	Star is zero in a min-plus semiring: the cheapest repeated traversal is to stay put. `>>>` `star (MinPlus 2 :: MinPlus Double)`MinPlus {getMinPlus = 0.0} Conway equations for 'MinPlus Double'. `>>>` *`let a = MinPlus 2 :: MinPlus Double; b = MinPlus 3 :: MinPlus Double in star (a b) == one + a * star (b * a) * b`True `>>>` `let a = MinPlus 2 :: MinPlus Double; b = MinPlus 3 :: MinPlus Double in star (a + b) == star (star a * b) * star a`**True
Instance details Defined in NumHask.Free.Carriers Methods star :: MinPlus Double -> MinPlus Double Source # plus :: MinPlus Double -> MinPlus Double Source #

Field semiring

newtype FieldStar Source #

Field semiring for matrix inversion (I − A)⁻¹.

star is the closed Neumann series: star a = recip (1 − a).

Constructors

FieldStar
Fields unFieldStar :: Double

Instances

Instances details

Eq FieldStar Source #
Instance details Defined in NumHask.Free.Carriers Methods (==) :: FieldStar -> FieldStar -> Bool # (/=) :: FieldStar -> FieldStar -> Bool #
Ord FieldStar Source #
Instance details Defined in NumHask.Free.Carriers Methods compare :: FieldStar -> FieldStar -> Ordering # (<) :: FieldStar -> FieldStar -> Bool # (<=) :: FieldStar -> FieldStar -> Bool # (>) :: FieldStar -> FieldStar -> Bool # (>=) :: FieldStar -> FieldStar -> Bool # max :: FieldStar -> FieldStar -> FieldStar # min :: FieldStar -> FieldStar -> FieldStar #
Num FieldStar Source #
Instance details Defined in NumHask.Free.Carriers Methods (+) :: FieldStar -> FieldStar -> FieldStar # (-) :: FieldStar -> FieldStar -> FieldStar # (*) :: FieldStar -> FieldStar -> FieldStar # negate :: FieldStar -> FieldStar # abs :: FieldStar -> FieldStar # signum :: FieldStar -> FieldStar # fromInteger :: Integer -> FieldStar #
Fractional FieldStar Source #
Instance details Defined in NumHask.Free.Carriers Methods (/) :: FieldStar -> FieldStar -> FieldStar # recip :: FieldStar -> FieldStar # fromRational :: Rational -> FieldStar #
Show FieldStar Source #
Instance details Defined in NumHask.Free.Carriers Methods showsPrec :: Int -> FieldStar -> ShowS # show :: FieldStar -> String # showList :: [FieldStar] -> ShowS #
Additive FieldStar Source #
Instance details Defined in NumHask.Free.Carriers Methods (+) :: FieldStar -> FieldStar -> FieldStar Source # zero :: FieldStar Source #
Subtractive FieldStar Source #
Instance details Defined in NumHask.Free.Carriers Methods negate :: FieldStar -> FieldStar Source # (-) :: FieldStar -> FieldStar -> FieldStar Source #
Multiplicative FieldStar Source #
Instance details Defined in NumHask.Free.Carriers Methods (*) :: FieldStar -> FieldStar -> FieldStar Source # one :: FieldStar Source #
StarSemiring FieldStar Source #
Instance details Defined in NumHask.Free.Carriers Methods star :: FieldStar -> FieldStar Source # plus :: FieldStar -> FieldStar Source #

Viterbi semiring

newtype Viterbi a Source #

Viterbi semiring for maximum-probability paths.

plus is max, times is ordinary multiplication, the additive unit is 0 and the multiplicative unit is 1. The star of any value is 1, because the empty path has probability 1 and no repeated path can improve on that.

Constructors

Viterbi
Fields getViterbi :: a

Instances

Instances details

Eq a => Eq (Viterbi a) Source #
Instance details Defined in NumHask.Free.Carriers Methods (==) :: Viterbi a -> Viterbi a -> Bool # (/=) :: Viterbi a -> Viterbi a -> Bool #
Ord a => Ord (Viterbi a) Source #
Instance details Defined in NumHask.Free.Carriers Methods compare :: Viterbi a -> Viterbi a -> Ordering # (<) :: Viterbi a -> Viterbi a -> Bool # (<=) :: Viterbi a -> Viterbi a -> Bool # (>) :: Viterbi a -> Viterbi a -> Bool # (>=) :: Viterbi a -> Viterbi a -> Bool # max :: Viterbi a -> Viterbi a -> Viterbi a # min :: Viterbi a -> Viterbi a -> Viterbi a #
Show a => Show (Viterbi a) Source #
Instance details Defined in NumHask.Free.Carriers Methods showsPrec :: Int -> Viterbi a -> ShowS # show :: Viterbi a -> String # showList :: [Viterbi a] -> ShowS #
Additive (Viterbi Double) Source #
Instance details Defined in NumHask.Free.Carriers Methods (+) :: Viterbi Double -> Viterbi Double -> Viterbi Double Source # zero :: Viterbi Double Source #
Idempotent (Viterbi Double) Source #
Instance details Defined in NumHask.Free.Carriers
Magma (Viterbi Double) Source #
Instance details Defined in NumHask.Free.Carriers Methods (⊕) :: Viterbi Double -> Viterbi Double -> Viterbi Double Source #
Multiplicative (Viterbi Double) Source #
Instance details Defined in NumHask.Free.Carriers Methods (*) :: Viterbi Double -> Viterbi Double -> Viterbi Double Source # one :: Viterbi Double Source #
KleeneAlgebra (Viterbi Double) Source #
Instance details Defined in NumHask.Free.Carriers
StarSemiring (Viterbi Double) Source #
Instance details Defined in NumHask.Free.Carriers Methods star :: Viterbi Double -> Viterbi Double Source # plus :: Viterbi Double -> Viterbi Double Source #