HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Modulesemirings-0.7Haskell98

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.

  • 3 types
  • 1 class
  • Packagesemirings-0.7
  • Exports4
  • LanguageHaskell98
  • LicenceBSD-3-Clause
  • SourceTropical.hs
datadata 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

Instances7Eq, Data, Ord, Read, Show, Semiring, …
datadata 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.

MinimaMaxima
datadata 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.

EProxy