Data.Semiring.Tropical

A tropical semiring is an extension of another totally ordered semiring with the operations of minimum or maximum as addition. The extended semiring is given positive or negative infinity as its zero element, so that the following hold:

plus Infinity y = y
plus x Infinity = x

i.e., In the max-plus tropical semiring (where plus is max), Infinity unifies with the typical interpretation of negative infinity, and thus it is the identity for the maximum, and in the min-plus tropical semiring (where plus is min), Infinity unifies with the typical interpretation of positive infinity, and thus it is the identity for the minimum.

Documentation

data Tropical (e :: Extrema) a

The tropical semiring.

Tropical 'Minima a is equivalent to the semiring \( (a \cup \{+\infty\}, \oplus, \otimes) \), where \( x \oplus y = min\{x,y\}\) and \(x \otimes y = x + y\).

Tropical 'Maxima a is equivalent to the semiring \( (a \cup \{-\infty\}, \oplus, \otimes) \), where \( x \oplus y = max\{x,y\}\) and \(x \otimes y = x + y\).

In literature, the Semiring instance of the Tropical semiring lifts the underlying semiring's additive structure. One might ask why this lifting doesn't instead witness a Monoid, since we only lift zero and plus - the reason is that usually the additive structure of a semiring is monotonic, i.e. a + (min b c) == min (a + b) (a + c), but in general this is not true. For example, lifting Product Word into Tropical is lawful, but Product Int is not, lacking distributivity: (-1) * (min 0 1) /= min ((-1) * 0) ((-1) * 1). So, we deviate from literature and instead witness the lifting of a Monoid, so the user must take care to ensure that their implementation of mappend is monotonic.

Constructors

Infinity

Tropical a

Instances

Eq a => Eq (Tropical e a)

Defined in Data.Semiring.Tropical

Methods

(==) :: Tropical e a -> Tropical e a -> Bool

(/=) :: Tropical e a -> Tropical e a -> Bool

(Typeable e, Data a) => Data (Tropical e a)

Defined in Data.Semiring.Tropical

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Tropical e a -> c (Tropical e a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Tropical e a)

toConstr :: Tropical e a -> Constr

dataTypeOf :: Tropical e a -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Tropical e a))

dataCast2 :: Typeable t => (forall d e0. (Data d, Data e0) => c (t d e0)) -> Maybe (c (Tropical e a))

gmapT :: (forall b. Data b => b -> b) -> Tropical e a -> Tropical e a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tropical e a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tropical e a -> r

gmapQ :: (forall d. Data d => d -> u) -> Tropical e a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> Tropical e a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tropical e a -> m (Tropical e a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tropical e a -> m (Tropical e a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tropical e a -> m (Tropical e a)

(Ord a, Extremum e) => Ord (Tropical e a)

Defined in Data.Semiring.Tropical

Methods

compare :: Tropical e a -> Tropical e a -> Ordering

(<) :: Tropical e a -> Tropical e a -> Bool

(<=) :: Tropical e a -> Tropical e a -> Bool

(>) :: Tropical e a -> Tropical e a -> Bool

(>=) :: Tropical e a -> Tropical e a -> Bool

max :: Tropical e a -> Tropical e a -> Tropical e a

min :: Tropical e a -> Tropical e a -> Tropical e a

Read a => Read (Tropical e a)

Defined in Data.Semiring.Tropical

Methods

readsPrec :: Int -> ReadS (Tropical e a)

readList :: ReadS [Tropical e a]

readPrec :: ReadPrec (Tropical e a)

readListPrec :: ReadPrec [Tropical e a]

Show a => Show (Tropical e a)

Defined in Data.Semiring.Tropical

Methods

showsPrec :: Int -> Tropical e a -> ShowS

show :: Tropical e a -> String

showList :: [Tropical e a] -> ShowS

(Ord a, Monoid a, Extremum e) => Semiring (Tropical e a)

Defined in Data.Semiring.Tropical

Methods

plus :: Tropical e a -> Tropical e a -> Tropical e a

zero :: Tropical e a

times :: Tropical e a -> Tropical e a -> Tropical e a

one :: Tropical e a

fromNatural :: Natural -> Tropical e a

(Ord a, Monoid a, Extremum e) => Star (Tropical e a)

Defined in Data.Semiring.Tropical

Methods

star :: Tropical e a -> Tropical e a

aplus :: Tropical e a -> Tropical e a

data Extrema

A datatype to be used at the kind-level. Its only purpose is to decide the ordering for the tropical semiring in a type-safe way.

Constructors

Minima

Maxima

class Extremum (e :: Extrema) where

The Extremum typeclass exists for us to match on the kind-level Extrema, so that we can recover which ordering to use in the Semiring instance for Tropical.

Methods

extremum :: EProxy e -> Extrema

Instances

Extremum Minima

Defined in Data.Semiring.Tropical

Methods

extremum :: EProxy Minima -> Extrema

Extremum Maxima

Defined in Data.Semiring.Tropical

Methods

extremum :: EProxy Maxima -> Extrema

data EProxy (e :: Extrema)

On older GHCs, Proxy is not polykinded, so we provide our own proxy type for Extrema. This turns out not to be a problem, since Extremum is a closed typeclass.

Constructors

EProxy