semiring-simple-1.0.0.1: A module for dealing with semirings.

Data.Semiring

Description

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)```

```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:

First, the requirements for a commutative monoid

```            minimum {∞, a} ≡ minimum {a, ∞} ≡ a
minimum {a, ∞} ≡ a
minimum {a, b} ≡ minimum {b, a}
minimum {a, minimum{b, c}} ≡ minimum {minimum {a, b}, c}```
```             0 + a ≡ a
a + 0 ≡ a
a + (b + c) ≡ (a + b) + c
a + minimum {b, c} ≡ minimum {a + b, a + c}
minimum {a, b} + c ≡ minimum {a + c, b + c}
a + ∞ ≡ ∞
∞ + a ≡ ∞```

Synopsis

# Documentation

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

Alias for `mappend`.

zero :: Monoid m => m Source

Alias for `mempty`

class Monoid m => Semiring m where Source

Methods

one :: m Source

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