Data.Semiring

This library provides a type class for semirings.

A semiring is an additive commutative monoid with identity zero:

Most Haskellers are familiar with the Monoid typeclass:

     zero <+> a ≡ a
(a <+> b) <+> c ≡ a <+> (b <+> c)

In this case, we've aliased

zero = mempty
(<+>) = mappend

A commutative monoid adds the requirement of symmetry:

        a <+> b ≡ b <+> a

A semiring adds the requirement of a multiplication-like operator. However, it does not require the existence of multiplicative inverses, i.e. division. Moreover, multiplication does not need to be commutative.

       one <.> a ≡ a
       a <.> one ≡ a
 (a <.> b) <.> c ≡ a <.> (b <.> c)

Multiplication distributes over addition:

a <.> (b <+> c) ≡ (a <.> b) <+> (a <.> b)
(a <+> b) <>. c ≡ (a <.> c) <+> (b <.> c)

zero annihilates a semiring with respect to multiplication:

zero <.> a ≡ zero
a <.> zero ≡ zero

The classic example of a semiring is the "Tropical numbers". The Tropical numbers, or T, are just real numbers with different operators.

zero = ∞
a <+> b = minimum {a, b}
one = 0
a <.> b = a + b

We can easily verify that these satisfy the semiring axioms:

minimum {∞, a} = minimum {a, ∞} = a, for all a
minimum {a, b} = minimum {b, a}, for all a, b
minimum {a, minimum{b, c}} = minimum {minimum {a, b}, c}, for all a, b, c

0 + a = a + 0 = a, for all a
a + (b + c) = (a + b) + c, for all a, b, c
a + minimum {b, c} = minimum {a, b} + minimum{a, c}, for all a, b, c
minimum {a, b} + c = minimum {a, c} + minimum{b, c}, for all a, b, c
a + ∞ = ∞ + a = ∞, for all a

Documentation

(<+>) :: Monoid m => m -> m -> m infixl 5

Alias for mappend.

zero :: Monoid m => m

Alias for mempty

class Monoid m => Semiring m where

Minimal complete definition

one, (<.>)

Methods

one :: m

(<.>) :: m -> m -> m