montrepol / packages /mp-linalg /src /MP /Algebra.hs
SNAPKITTYWEST's picture
montrepol: exact mathematics in Haskell, with proofs and a certifying solver
5316c4e verified
Raw History Blame Contribute Delete
3.82 kB
-- SPDX-License-Identifier: AGPL-3.0-or-later
-- | The algebraic structures the matrix code is generic over.
--
-- 'Num' is not used: it bundles 'abs', 'signum' and 'fromInteger', which a
-- semiring does not have, and it would let a tropical or Boolean matrix be
-- negated by accident. Each class here carries exactly its axioms' operations.
-- The axioms themselves are checked by property tests in @test/@, per instance.
module MP.Algebra
( Semiring (..)
, Ring (..)
, (.-.)
, Domain (..)
, Field (..)
, GF2 (..)
, MinPlus (..)
, sumS
, productS
) where
import Data.Ratio (denominator, numerator)
infixl 6 .+.
infixl 7 .*.
infixl 6 .-.
-- | @(a, .+., zero)@ is a commutative monoid, @(a, .*., one)@ a monoid,
-- multiplication distributes over addition and @zero@ annihilates.
class Semiring a where
zero :: a
one :: a
(.+.) :: a -> a -> a
(.*.) :: a -> a -> a
isZero :: a -> Bool
-- | A semiring with additive inverses.
class Semiring a => Ring a where
neg :: a -> a
(.-.) :: Ring a => a -> a -> a
a .-. b = a .+. neg b
-- | A commutative ring without zero divisors, with exact division.
--
-- @exactQuot a b@ is the @q@ with @q .*. b == a@ when one exists and @b@ is
-- non-zero. It is total: on other inputs it returns some value, and every use
-- in this repository is at a point where divisibility is a theorem (Sylvester's
-- identity, for Bareiss). The tests compare against division-free oracles, so
-- a non-exact division would surface as a wrong answer.
class Ring a => Domain a where
exactQuot :: a -> a -> a
class Domain a => Field a where
-- | 'Nothing' exactly for zero.
recipF :: a -> Maybe a
sumS :: Semiring a => [a] -> a
sumS = foldr (.+.) zero
productS :: Semiring a => [a] -> a
productS = foldr (.*.) one
------------------------------------------------------------------------------
-- Integers and rationals
instance Semiring Integer where
zero = 0
one = 1
(.+.) = (+)
(.*.) = (*)
isZero = (== 0)
instance Ring Integer where neg = negate
instance Domain Integer where
exactQuot _ 0 = 0
exactQuot a b = a `quot` b
instance Semiring Rational where
zero = 0
one = 1
(.+.) = (+)
(.*.) = (*)
isZero = (== 0)
instance Ring Rational where neg = negate
instance Domain Rational where
exactQuot a b = maybe 0 (a *) (recipF b)
instance Field Rational where
recipF q
| numerator q == 0 = Nothing
| otherwise = Just (fromInteger (denominator q) / fromInteger (numerator q))
------------------------------------------------------------------------------
-- The field with two elements
newtype GF2 = GF2 Bool
deriving (Eq, Ord)
instance Show GF2 where
show (GF2 b) = if b then "1" else "0"
instance Semiring GF2 where
zero = GF2 False
one = GF2 True
GF2 a .+. GF2 b = GF2 (a /= b)
GF2 a .*. GF2 b = GF2 (a && b)
isZero (GF2 b) = not b
instance Ring GF2 where neg = id
instance Domain GF2 where
exactQuot a (GF2 True) = a
exactQuot _ (GF2 False) = GF2 False
instance Field GF2 where
recipF (GF2 True) = Just (GF2 True)
recipF (GF2 False) = Nothing
------------------------------------------------------------------------------
-- The tropical (min, +) semiring
-- | 'Nothing' is +infinity. Matrix powers over this semiring compute shortest
-- paths, which is the reason it is here: it shows the multiplication really is
-- semiring-generic and is checked against Floyd–Warshall.
newtype MinPlus = MinPlus (Maybe Integer)
deriving (Eq, Show)
instance Semiring MinPlus where
zero = MinPlus Nothing
one = MinPlus (Just 0)
MinPlus Nothing .+. b = b
a .+. MinPlus Nothing = a
MinPlus (Just x) .+. MinPlus (Just y) = MinPlus (Just (min x y))
MinPlus (Just x) .*. MinPlus (Just y) = MinPlus (Just (x + y))
_ .*. _ = MinPlus Nothing
isZero (MinPlus m) = m == Nothing