-- |
-- Module : Data.Semiring
-- Description : Semirings
-- Copyright : Copyright (c) 2012, Thomas Wilke, Frank Huch, Sebastian Fischer.
-- Copyright (c) 2014-2016, Peter Harpending.
-- License : BSD3
-- Maintainer : Peter Harpending <peter@harpending.org>
-- Stability : experimental
-- Portability : portable
--
-- 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:
--
-- 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 ≡ ∞
module Data.Semiring where
import Data.Monoid
-- |Alias for 'mappend'.
infixl 5 <+>
(<+>) :: Monoid m => m -> m -> m
(<+>) = mappend
-- |Alias for 'mempty'
zero :: Monoid m => m
zero = mempty
class Monoid m => Semiring m where
one :: m
(<.>) :: m -> m -> m