Download packages/mp-linalg/src/MP/Algebra.hs from SNAPKITTYWEST/montrepol: direct link, hf CLI and curl.
- Browser
- Download file 3.82 kB
-
https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/packages/mp-linalg/src/MP/Algebra.hs
- Command line
-
hf download hf://SNAPKITTYWEST/montrepol/packages/mp-linalg/src/MP/Algebra.hs
-
curl -L -o Algebra.hs https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/packages/mp-linalg/src/MP/Algebra.hs
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 | |