-- |
-- Module : Data.Semiring
-- Description : Semirings
-- Copyright : 2012, Thomas Wilke, Frank Huch, Sebastian Fischer
-- 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:
--
-- > 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
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