# HaskellForMaths patch for GHC 7.4.1.

```Hi David,

GHC-7.4.1 on Debian, due to Num not implying Eq any more. I hope you can
make use of the patch.

Greetings,
Joachim

--
Joachim "nomeata" Breitner
Debian Developer
nomeata@debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C
JID: nomeata@joachim-breitner.de | http://people.debian.org/~nomeata
```
```Description: Add Eq Constraints
to make it compile with GHC 7.4.1
Author: Joachim Breitner <nomeata@debian.org>

===================================================================
@@ -19,7 +19,7 @@
-- Elements of Vect k b consist of k-linear combinations of elements of b.
newtype Vect k b = V [(b,k)] deriving (Eq,Ord)

-instance (Num k, Show b) => Show (Vect k b) where
+instance (Show k, Eq k, Num k, Show b) => Show (Vect k b) where
show (V []) = "0"
show (V ts) = concatWithPlus \$ map showTerm ts
where showTerm (b,x) | show b == "1" = show x
@@ -52,11 +52,11 @@
zerov = V []

-add :: (Ord b, Num k) => Vect k b -> Vect k b -> Vect k b
+add :: (Ord b, Eq k, Num k) => Vect k b -> Vect k b -> Vect k b

-(<+>) :: (Ord b, Num k) => Vect k b -> Vect k b -> Vect k b
+(<+>) :: (Ord b, Eq k, Num k) => Vect k b -> Vect k b -> Vect k b

@@ -68,33 +68,33 @@

-- |Sum of a list of vectors
-sumv :: (Ord b, Num k) => [Vect k b] -> Vect k b
+sumv :: (Ord b, Eq k, Num k) => [Vect k b] -> Vect k b
sumv = foldl (<+>) zerov

-- |Negation of vector
-neg :: (Num k) => Vect k b -> Vect k b
+neg :: (Eq k, Num k) => Vect k b -> Vect k b
neg (V ts) = V \$ map (\(b,x) -> (b,-x)) ts

-- |Subtraction of vectors
-(<->) :: (Ord b, Num k) => Vect k b -> Vect k b -> Vect k b
+(<->) :: (Ord b, Eq k, Num k) => Vect k b -> Vect k b -> Vect k b
(<->) u v = u <+> neg v

-- |Scalar multiplication (on the left)
-smultL :: (Num k) => k -> Vect k b -> Vect k b
+smultL :: (Eq k, Num k) => k -> Vect k b -> Vect k b
smultL 0 _ = zero -- V []
smultL k (V ts) = V [(ei,k*xi) | (ei,xi) <- ts]

-- |Same as smultL. Mnemonic is \"multiply through (from the left)\"
-(*>) :: (Num k) => k -> Vect k b -> Vect k b
+(*>) :: (Eq k, Num k) => k -> Vect k b -> Vect k b
(*>) = smultL

-- |Scalar multiplication on the right
-smultR :: (Num k) => Vect k b -> k -> Vect k b
+smultR :: (Eq k, Num k) => Vect k b -> k -> Vect k b
smultR _ 0 = zero -- V []
smultR (V ts) k = V [(ei,xi*k) | (ei,xi) <- ts]

-- |Same as smultR. Mnemonic is \"multiply through (from the right)\"
-(<*) :: (Num k) => Vect k b -> k -> Vect k b
+(<*) :: (Eq k, Num k) => Vect k b -> k -> Vect k b
(<*) = smultR

-- same as return
@@ -107,7 +107,7 @@

-- |Convert an element of Vect k b into normal form. Normal form consists in having the basis elements in ascending order,
-- with no duplicates, and all coefficients non-zero
-nf :: (Ord b, Num k) => Vect k b -> Vect k b
+nf :: (Ord b, Eq k, Num k) => Vect k b -> Vect k b
nf (V ts) = V \$ nf' \$ L.sortBy compareFst ts where
nf' ((b1,x1):(b2,x2):ts) =
case compare b1 b2 of
@@ -135,7 +135,7 @@
--
-- If we have A = Vect k a, B = Vect k b, and f :: a -> Vect k b is a function from the basis elements of A into B,
-- then @linear f@ is the linear map that this defines by linearity.
-linear :: (Ord b, Num k) => (a -> Vect k b) -> Vect k a -> Vect k b
+linear :: (Ord b, Eq k, Num k) => (a -> Vect k b) -> Vect k a -> Vect k b
linear f v = nf \$ v >>= f

newtype EBasis = E Int deriving (Eq,Ord)
@@ -154,7 +154,7 @@
-- but in the code, we need this if we want to be able to put k as one side of a tensor product.
type Trivial k = Vect k ()

-wrap :: Num k => k -> Vect k ()
+wrap :: (Eq k, Num k) => k -> Vect k ()
wrap 0 = zero
wrap x = V [( (),x)]

===================================================================
@@ -27,7 +27,7 @@

-- |The coproduct of two linear functions (with the same target).
-- Satisfies the universal property that f == coprodf f g . i1 and g == coprodf f g . i2
-coprodf :: (Num k, Ord t) =>
+coprodf :: (Eq k, Num k, Ord t) =>
(Vect k a -> Vect k t) -> (Vect k b -> Vect k t) -> Vect k (DSum a b) -> Vect k t
coprodf f g = linear fg' where
fg' (Left a) = f (return a)
@@ -35,33 +35,33 @@

-- |Projection onto left summand from direct sum
-p1 :: (Num k, Ord a) => Vect k (DSum a b) -> Vect k a
+p1 :: (Eq k, Num k, Ord a) => Vect k (DSum a b) -> Vect k a
p1 = linear p1' where
p1' (Left a) = return a
p1' (Right b) = zero

-- |Projection onto right summand from direct sum
-p2 :: (Num k, Ord b) => Vect k (DSum a b) -> Vect k b
+p2 :: (Eq k, Num k, Ord b) => Vect k (DSum a b) -> Vect k b
p2 = linear p2' where
p2' (Left a) = zero
p2' (Right b) = return b

-- |The product of two linear functions (with the same source).
-- Satisfies the universal property that f == p1 . prodf f g and g == p2 . prodf f g
-prodf :: (Num k, Ord a, Ord b) =>
+prodf :: (Eq k, Num k, Ord a, Ord b) =>
(Vect k s -> Vect k a) -> (Vect k s -> Vect k b) -> Vect k s -> Vect k (DSum a b)
prodf f g = linear fg' where
fg' b = fmap Left (f \$ return b) <+> fmap Right (g \$ return b)

-- |The direct sum of two vector space elements
-dsume :: (Num k, Ord a, Ord b) => Vect k a -> Vect k b -> Vect k (DSum a b)
+dsume :: (Eq k, Num k, Ord a, Ord b) => Vect k a -> Vect k b -> Vect k (DSum a b)
-- dsume x y = fmap Left x <+> fmap Right y
dsume x y = i1 x <+> i2 y

-- |The direct sum of two linear functions.
-- Satisfies the universal property that f == p1 . dsumf f g . i1 and g == p2 . dsumf f g . i2
-dsumf :: (Num k, Ord a, Ord b, Ord a', Ord b') =>
+dsumf :: (Eq k, Num k, Ord a, Ord b, Ord a', Ord b') =>
(Vect k a -> Vect k a') -> (Vect k b -> Vect k b') -> Vect k (DSum a b) -> Vect k (DSum a' b')
dsumf f g ab = (i1 . f . p1) ab <+> (i2 . g . p2) ab

@@ -80,7 +80,7 @@

-- Implicit assumption - f and g are linear
-- |The tensor product of two linear functions
-tf :: (Num k, Ord a', Ord b') => (Vect k a -> Vect k a') -> (Vect k b -> Vect k b')
+tf :: (Eq k, Num k, Ord a', Ord b') => (Vect k a -> Vect k a') -> (Vect k b -> Vect k b')
-> Vect k (Tensor a b) -> Vect k (Tensor a' b')
tf f g (V ts) = sum [x *> te (f \$ return a) (g \$ return b) | ((a,b), x) <- ts]
where sum = foldl add zero -- (V [])
@@ -107,16 +107,16 @@
unitOutR :: Vect k (Tensor a ()) -> Vect k a
unitOutR = fmap ( \(a,()) -> a )

-twist :: (Num k, Ord a, Ord b) => Vect k (Tensor a b) -> Vect k (Tensor b a)
+twist :: (Eq k, Num k, Ord a, Ord b) => Vect k (Tensor a b) -> Vect k (Tensor b a)
twist v = nf \$ fmap ( \(a,b) -> (b,a) ) v
-- note the nf call, as f is not order-preserving

-distrL :: (Num k, Ord a, Ord b, Ord c)
+distrL :: (Eq k, Num k, Ord a, Ord b, Ord c)
=> Vect k (Tensor a (DSum b c)) -> Vect k (DSum (Tensor a b) (Tensor a c))
distrL v = nf \$ fmap (\(a,bc) -> case bc of Left b -> Left (a,b); Right c -> Right (a,c)) v

-undistrL :: (Num k, Ord a, Ord b, Ord c)
+undistrL :: (Eq k, Num k, Ord a, Ord b, Ord c)
=> Vect k (DSum (Tensor a b) (Tensor a c)) -> Vect k (Tensor a (DSum b c))
undistrL v = nf \$ fmap ( \abc -> case abc of Left (a,b) -> (a,Left b); Right (a,c) -> (a,Right c) ) v

@@ -132,11 +132,11 @@
-- Left (e1,e2)

-ev :: (Num k, Ord b) => Vect k (Tensor (Dual b) b) -> k
+ev :: (Eq k, Num k, Ord b) => Vect k (Tensor (Dual b) b) -> k
ev = unwrap . linear (\(Dual bi, bj) -> delta bi bj *> return ())
-- slightly cheating, as delta i j is meant to compare indices, not the basis elements themselves

delta i j = if i == j then 1 else 0

-reify :: (Num k, Ord b) => Vect k (Dual b) -> (Vect k b -> k)
+reify :: (Eq k, Num k, Ord b) => Vect k (Dual b) -> (Vect k b -> k)
reify f x = ev (f `te` x)
===================================================================
@@ -43,7 +43,7 @@
antipode :: Vect k b -> Vect k b

-instance (Num k, Eq b, Ord b, Show b, Algebra k b) => Num (Vect k b) where
+instance (Eq k, Num k, Eq b, Ord b, Show b, Algebra k b) => Num (Vect k b) where
x+y = x <+> y
negate x = neg x
-- negate (V ts) = V \$ map (\(b,x) -> (b, negate x)) ts
@@ -66,7 +66,7 @@
-}

-instance Num k => Algebra k () where
+instance (Eq k, Num k) => Algebra k () where
unit = wrap
-- unit 0 = zero -- V []
-- unit x = V [( (),x)]
@@ -74,7 +74,7 @@
-- mult (V [( ((),()), x)]) = V [( (),x)]
-- mult (V []) = zerov

-instance Num k => Coalgebra k () where
+instance (Eq k, Num k) => Coalgebra k () where
counit = unwrap
-- counit (V []) = 0
-- counit (V [( (),x)]) = x
@@ -82,10 +82,10 @@
-- comult (V [( (),x)]) = V [( ((),()), x)]
-- comult (V []) = zerov

-unit' :: (Num k, Algebra k b) => Trivial k -> Vect k b
+unit' :: (Eq k, Num k, Algebra k b) => Trivial k -> Vect k b
unit' = unit . unwrap -- where unwrap = counit :: Num k => Trivial k -> k

-counit' :: (Num k, Coalgebra k b) => Vect k b -> Trivial k
+counit' :: (Eq k, Num k, Coalgebra k b) => Vect k b -> Trivial k
counit' = wrap . counit -- where wrap = unit :: Num k => k -> Trivial k

-- unit' and counit' enable us to form tensors of these functions
@@ -94,7 +94,7 @@
-- Kassel p4
-- |The direct sum of k-algebras can itself be given the structure of a k-algebra.
-- This is the product object in the category of k-algebras.
-instance (Num k, Ord a, Ord b, Algebra k a, Algebra k b) => Algebra k (DSum a b) where
+instance (Eq k, Num k, Ord a, Ord b, Algebra k a, Algebra k b) => Algebra k (DSum a b) where
unit k = i1 (unit k) <+> i2 (unit k)
-- unit == (i1 . unit) <<+>> (i2 . unit)
mult = linear mult'
@@ -108,7 +108,7 @@

-- |The direct sum of k-coalgebras can itself be given the structure of a k-coalgebra.
-- This is the coproduct object in the category of k-coalgebras.
-instance (Num k, Ord a, Ord b, Coalgebra k a, Coalgebra k b) => Coalgebra k (DSum a b) where
+instance (Eq k, Num k, Ord a, Ord b, Coalgebra k a, Coalgebra k b) => Coalgebra k (DSum a b) where
counit = unwrap . linear counit'
where counit' (Left a) = (wrap . counit) (return a)
counit' (Right b) = (wrap . counit) (return b)
@@ -123,7 +123,7 @@

-- Kassel p32
-- |The tensor product of k-algebras can itself be given the structure of a k-algebra
-instance (Num k, Ord a, Ord b, Algebra k a, Algebra k b) => Algebra k (Tensor a b) where
+instance (Eq k, Num k, Ord a, Ord b, Algebra k a, Algebra k b) => Algebra k (Tensor a b) where
-- unit 0 = V []
unit x = x *> (unit 1 `te` unit 1)
mult = linear m where
@@ -131,7 +131,7 @@

-- Kassel p42
-- |The tensor product of k-coalgebras can itself be given the structure of a k-coalgebra
-instance (Num k, Ord a, Ord b, Coalgebra k a, Coalgebra k b) => Coalgebra k (Tensor a b) where
+instance (Eq k, Num k, Ord a, Ord b, Coalgebra k a, Coalgebra k b) => Coalgebra k (Tensor a b) where
counit = counit . (counit' `tf` counit')
-- counit = counit . linear (\(T x y) -> counit' (return x) * counit' (return y))
comult = assocL . (id `tf` assocR) . (id `tf` (twist `tf` id))
@@ -139,20 +139,20 @@

-- The set coalgebra - can be defined on any set
-instance Num k => Coalgebra k EBasis where
+instance (Eq k, Num k) => Coalgebra k EBasis where
counit (V ts) = sum [x | (ei,x) <- ts]  -- trace
comult = fmap ( \ei -> (ei,ei) )        -- diagonal

newtype SetCoalgebra b = SC b deriving (Eq,Ord,Show)

-instance Num k => Coalgebra k (SetCoalgebra b) where
+instance (Eq k, Num k) => Coalgebra k (SetCoalgebra b) where
counit (V ts) = sum [x | (m,x) <- ts]  -- trace
comult = fmap ( \m -> (m,m) )          -- diagonal

newtype MonoidCoalgebra m = MC m deriving (Eq,Ord,Show)

-instance (Num k, Ord m, Mon m) => Coalgebra k (MonoidCoalgebra m) where
+instance (Eq k, Num k, Ord m, Mon m) => Coalgebra k (MonoidCoalgebra m) where
counit (V ts) = sum [if m == MC munit then x else 0 | (m,x) <- ts]
comult = linear cm
where cm m = if m == MC munit then return (m,m) else return (m, MC munit) <+> return (MC munit, m)
@@ -184,13 +184,13 @@

-- Kassel p57-8

-instance (Num k, Ord a, Ord u, Ord v, Algebra k a, Module k a u, Module k a v)
+instance (Eq k, Num k, Ord a, Ord u, Ord v, Algebra k a, Module k a u, Module k a v)
=> Module k (Tensor a a) (Tensor u v) where
-- action x = nf \$ x >>= action'
action = linear action'
where action' ((a,a'), (u,v)) = (action \$ return (a,u)) `te` (action \$ return (a',v))

-instance (Num k, Ord a, Ord u, Ord v, Bialgebra k a, Module k a u, Module k a v)
+instance (Eq k, Num k, Ord a, Ord u, Ord v, Bialgebra k a, Module k a u, Module k a v)
=> Module k a (Tensor u v) where
-- action x = nf \$ x >>= action'
action = linear action'
@@ -200,7 +200,7 @@
-- On the other hand, if a == Tensor u v, then we have overlapping instance with the earlier instance

-- Kassel p63
-instance (Num k, Ord a, Ord m, Ord n, Bialgebra k a, Comodule k a m, Comodule k a n)
+instance (Eq k, Num k, Ord a, Ord m, Ord n, Bialgebra k a, Comodule k a m, Comodule k a n)
=> Comodule k a (Tensor m n) where
coaction = (mult `tf` id) . twistm . (coaction `tf` coaction)
where twistm x = nf \$ fmap ( \((h,m), (h',n)) -> ((h,h'), (m,n)) ) x
===================================================================
@@ -18,7 +18,7 @@

x = UP [0,1] :: UPoly Integer

-instance (Show a, Num a) => Show (UPoly a) where
+instance (Show a, Eq a, Num a) => Show (UPoly a) where
-- show (UP []) = "0"
show (UP as) = showUP "x" as

@@ -39,7 +39,7 @@
| i == 1 = v -- "x"
| i > 1  = v ++ "^" ++ show i -- "x^" ++ show i

-instance Num a => Num (UPoly a) where
+instance (Eq a, Num a) => Num (UPoly a) where
UP as + UP bs = toUPoly \$ as <+> bs
negate (UP as) = UP \$ map negate as
UP as * UP bs = toUPoly \$ as <*> bs
@@ -78,7 +78,7 @@
monomial a i = UP \$ replicate i 0 ++ [a]

-- quotRem for UPolys over a field
-quotRemUP :: (Num k, Fractional k) => UPoly k -> UPoly k -> (UPoly k, UPoly k)
+quotRemUP :: (Eq k, Num k, Fractional k) => UPoly k -> UPoly k -> (UPoly k, UPoly k)
quotRemUP f g = qr 0 f where
qr q r = if deg r < deg_g
then (q,r)
@@ -105,12 +105,12 @@

data ExtensionField k poly = Ext (UPoly k) deriving (Eq,Ord)

-instance Num k => Show (ExtensionField k poly) where
+instance (Show k, Eq k, Num k) => Show (ExtensionField k poly) where
-- show (Ext f) = show f
-- show (Ext (UP [])) = "0"
show (Ext (UP as)) = showUP "a" as

-instance (Num k, Fractional k, PolynomialAsType k poly) => Num (ExtensionField k poly) where
+instance (Eq k, Num k, Fractional k, PolynomialAsType k poly) => Num (ExtensionField k poly) where
Ext x + Ext y = Ext \$ (x+y) -- `modUP` pvalue (undefined :: (k,poly))
Ext x * Ext y = Ext \$ (x*y) `modUP` pvalue (undefined :: (k,poly))
negate (Ext x) = Ext \$ negate x
@@ -118,7 +118,7 @@
abs _ = error "Prelude.Num.abs: inappropriate abstraction"
signum _ = error "Prelude.Num.signum: inappropriate abstraction"

-instance (Num k, Fractional k, PolynomialAsType k poly) => Fractional (ExtensionField k poly) where
+instance (Eq k, Num k, Fractional k, PolynomialAsType k poly) => Fractional (ExtensionField k poly) where
recip 0 = error "ExtensionField.recip 0"
recip (Ext f) = let g = pvalue (undefined :: (k,poly))
(u,v,d@(UP [c])) = extendedEuclidUP f g
@@ -130,7 +130,7 @@
c /> f@(UP as) | c == 1 = f
| c /= 0 = UP (map (c' *) as) where c' = recip c

-instance (FiniteField k, PolynomialAsType k poly) => FiniteField (ExtensionField k poly) where
+instance (Eq k, FiniteField k, PolynomialAsType k poly) => FiniteField (ExtensionField k poly) where
eltsFq _ = map Ext (polys (d-1) fp) where
fp = eltsFq (undefined :: k)
d = deg \$ pvalue (undefined :: (k,poly))
@@ -243,4 +243,4 @@
-- conjugate of a + b sqrt d is a - b sqrt d
conjugate :: ExtensionField Q (Sqrt d) -> ExtensionField Q (Sqrt d)
conjugate (Ext (UP [a,b])) = Ext (UP [a,-b])
-conjugate x = x -- the zero or constant cases
\ No newline at end of file
+conjugate x = x -- the zero or constant cases
===================================================================
@@ -58,7 +58,7 @@
then "+(" ++ c:cs ++ ")"
else if c == '-' then c:cs else '+':c:cs

-instance (Ord v, Show v, Num r) => Num (NPoly r v) where
+instance (Ord v, Show v, Eq r, Num r) => Num (NPoly r v) where
NP ts + NP us = NP (mergeTerms ts us)
negate (NP ts) = NP \$ map (\(m,c) -> (m,-c)) ts
NP ts * NP us = NP \$ collect \$ L.sortBy cmpTerm \$ [(g*h,c*d) | (g,c) <- ts, (h,d) <- us]
@@ -85,7 +85,7 @@

-- Fractional instance so that we can enter fractional coefficients
-- Only lets us divide by field elements (with unit monomial), not any other polynomials
-instance (Ord v, Show v, Fractional r) => Fractional (NPoly r v) where
+instance (Ord v, Show v, Eq r, Fractional r) => Fractional (NPoly r v) where
recip (NP [(1,c)]) = NP [(1, recip c)]
recip _ = error "NPoly.recip: only supported for (non-zero) constants"

@@ -210,4 +210,4 @@
class Invertible a where
inv :: a -> a

-x ^- k = inv x ^ k
\ No newline at end of file
+x ^- k = inv x ^ k
===================================================================
@@ -47,7 +47,7 @@
-}

-- This is the monoid algebra for commutative monomials (which are the free commutative monoid)
-instance (Num k, Ord v) => Algebra k (GlexMonomial v) where
+instance (Eq k, Num k, Ord v) => Algebra k (GlexMonomial v) where
unit x = x *> return munit
where munit = Glex 0 []
mult xy = nf \$ fmap (\(a,b) -> a `mmult` b) xy
@@ -55,7 +55,7 @@

-- GlexPoly can be given the set coalgebra structure, which is compatible with the monoid algebra structure
-instance Num k => Coalgebra k (GlexMonomial v) where
+instance (Eq k, Num k) => Coalgebra k (GlexMonomial v) where
counit = unwrap . nf . fmap (\m -> () )  -- trace
-- counit (V ts) = sum [x | (m,x) <- ts]  -- trace
comult = fmap (\m -> (m,m) )             -- diagonal
@@ -78,7 +78,7 @@
-- |In effect, we have (Num k, Monomial m) => Monad (\v -> Vect k (m v)), with return = var, and (>>=) = bind.
-- However, we can't express this directly in Haskell, firstly because of the Ord b constraint,
-- secondly because Haskell doesn't support type functions.
-bind :: (Monomial m, Num k, Ord b, Show b, Algebra k b) =>
+bind :: (Monomial m, Eq k, Num k, Ord b, Show b, Algebra k b) =>
Vect k (m v) -> (v -> Vect k b) -> Vect k b
V ts `bind` f = sum [c *> product [f x ^ i | (x,i) <- powers m] | (m, c) <- ts]
-- flipbind f = linear (\m -> product [f x ^ i | (x,i) <- powers m])
@@ -120,7 +120,7 @@
infixl 7 %%

-- |(%%) reduces a polynomial with respect to a list of polynomials.
-(%%) :: (Fractional k, Ord b, Show b, Algebra k b, DivisionBasis b)
+(%%) :: (Eq k, Fractional k, Ord b, Show b, Algebra k b, DivisionBasis b)
=> Vect k b -> [Vect k b] -> Vect k b
f %% gs = r where (_,r) = quotRemMP f gs

===================================================================
@@ -20,7 +20,7 @@
type GroupAlgebra k = Vect k (Permutation Int)

-- Monoid Algebra instance
-instance Num k => Algebra k (Permutation Int) where
+instance (Eq k, Num k) => Algebra k (Permutation Int) where
unit 0 = zero -- V []
unit x = V [(munit,x)]
mult = nf . fmap (\(a,b) -> a `mmult` b)
@@ -28,14 +28,14 @@
-- Set Coalgebra instance
-- instance SetCoalgebra (Permutation Int) where {}

-instance Num k => Coalgebra k (Permutation Int) where
+instance (Eq k, Num k) => Coalgebra k (Permutation Int) where
counit (V ts) = sum [x | (m,x) <- ts] -- trace
comult = fmap (\m -> (m,m)) -- diagonal

-instance Num k => Bialgebra k (Permutation Int) where {}
+instance (Eq k, Num k) => Bialgebra k (Permutation Int) where {}
-- should check that the algebra and coalgebra structures are compatible

-instance (Num k) => HopfAlgebra k (Permutation Int) where
+instance (Eq k, Num k) => HopfAlgebra k (Permutation Int) where
antipode (V ts) = nf \$ V [(g^-1,x) | (g,x) <- ts]

-- inject permutation into group algebra
@@ -43,7 +43,7 @@
ip cs = return \$ p cs

-instance Num k => Module k (Permutation Int) Int where
+instance (Eq k, Num k) => Module k (Permutation Int) Int where
action = nf . fmap (\(g,x) -> x .^ g)

===================================================================
@@ -31,7 +31,7 @@
munit = LM 0 []
mmult (LM si xis) (LM sj yjs) = LM (si+sj) \$ addmerge xis yjs

-instance Num k => Algebra k LaurentMonomial where
+instance (Eq k, Num k) => Algebra k LaurentMonomial where
unit 0 = zero -- V []
unit x = V [(munit,x)]
mult (V ts) = nf \$ fmap (\(a,b) -> a `mmult` b) (V ts)
@@ -49,7 +49,7 @@

lvar v = V [(LM 1 [(v,1)], 1)] :: LaurentPoly Q

-instance Fractional k => Fractional (LaurentPoly k) where
+instance (Eq k, Fractional k) => Fractional (LaurentPoly k) where
recip (V [(LM si xis,c)]) = V [(LM (-si) \$ map (\(x,i)->(x,-i)) xis, recip c)]
recip _ = error "LaurentPoly.recip: only defined for single terms"

===================================================================
@@ -22,7 +22,7 @@
data Mat2 = E2 Int Int deriving (Eq,Ord,Show)
-- E i j represents the elementary matrix with a 1 at the (i,j) position, and 0s elsewhere

-instance Num k => Algebra k Mat2 where
+instance (Eq k, Num k) => Algebra k Mat2 where
unit x = x *> V [(E2 i i, 1) | i <- [1..2] ]
mult = linear mult' where
mult' (E2 i j, E2 k l) = delta j k *> return (E2 i l)
@@ -33,7 +33,7 @@
-- mult (a1 b1) `te` (a2 b2) = (a1 b1) * (a2 b2) = (a b)
--      (c1 d1)      (c2 d2)   (c1 d1)   (c2 d2)   (c d)

-instance Num k => Module k Mat2 EBasis where
+instance (Eq k, Num k) => Module k Mat2 EBasis where
-- action ax = nf \$ ax >>= action' where
action = linear action' where
action' (E2 i j, E k) = delta j k `smultL` return (E i)
@@ -55,7 +55,7 @@
-- E2' i j represents the dual basis element corresponding to E i j

-- Kassel p42
-instance Num k => Coalgebra k Mat2' where
+instance (Eq k, Num k) => Coalgebra k Mat2' where
counit (V ts) = sum [xij * delta i j | (E2' i j, xij) <- ts]
-- comult (V ts) = V \$ concatMap (\(E2' i j,xij) -> [(T (E2' i k) (E2' k j), xij) | k <- [1..2]]) ts
comult = linear (\(E2' i j) -> foldl (<+>) zero [return (E2' i k, E2' k j) | k <- [1..2]])
@@ -73,7 +73,7 @@
data M3 = E3 Int Int deriving (Eq,Ord,Show)
-- E i j represents the elementary matrix with a 1 at the (i,j) position, and 0s elsewhere

-instance Num k => Algebra k M3 where
+instance (Eq k, Num k) => Algebra k M3 where
unit 0 = zero -- V []
unit x = V [(E3 i i, x) | i <- [1..3] ]
-- mult (V ts) = nf \$ V \$ map (\((E3 i j, E3 k l), x) -> (E3 i l, delta j k * x)) ts
@@ -87,4 +87,4 @@
counit (V ts) = sum [xij * delta i j | (E3 i j, xij) <- ts]
comult (V ts) = V \$ concatMap (\(E3 i j,xij) -> [((E3 i k, E3 k j), xij) | k <- [1..3]]) ts
-- (is this order preserving?)
--}
\ No newline at end of file
+-}
===================================================================
@@ -29,7 +29,7 @@
munit = NCM 0 []
mmult (NCM i xs) (NCM j ys) = NCM (i+j) (xs++ys)

-instance (Num k, Ord v) => Algebra k (NonComMonomial v) where
+instance (Eq k, Num k, Ord v) => Algebra k (NonComMonomial v) where
unit 0 = zero -- V []
unit x = V [(munit,x)]
mult = nf . fmap (\(a,b) -> a `mmult` b)
===================================================================
@@ -34,7 +34,7 @@
munit = TA 0 []
mmult (TA i xs) (TA j ys) = TA (i+j) (xs++ys)

-instance (Num k, Ord a) => Algebra k (TensorAlgebra a) where
+instance (Eq k, Num k, Ord a) => Algebra k (TensorAlgebra a) where
unit x = x *> return munit
mult = nf . fmap (\(a,b) -> a `mmult` b)

@@ -50,7 +50,7 @@
-- The Num k context is not strictly necessary

-- |Inject an element of the set\/type A\/a into the tensor algebra T(A) = Vect k (TensorAlgebra a).
-injectTA' :: Num k => a -> Vect k (TensorAlgebra a)
+injectTA' :: (Eq k, Num k) => a -> Vect k (TensorAlgebra a)
injectTA' = injectTA . return
-- injectTA' a = return (TA 1 [a])

@@ -59,7 +59,7 @@
-- where T(A) is the tensor algebra Vect k (TensorAlgebra a).
-- f' will agree with f on A itself (considered as a subspace of T(A)).
-- In other words, f = f' . injectTA
-liftTA :: (Num k, Ord b, Show b, Algebra k b) =>
+liftTA :: (Eq k, Num k, Ord b, Show b, Algebra k b) =>
(Vect k a -> Vect k b) -> Vect k (TensorAlgebra a) -> Vect k b
liftTA f = linear (\(TA _ xs) -> product [f (return x) | x <- xs])
-- The Show b constraint is required because we use product (and Num requires Show)!!
@@ -67,7 +67,7 @@
-- |Given a set\/type A\/a, and a vector space B = Vect k b, where B is also an algebra,
-- lift a function f: A -> B to an algebra morphism f': T(A) -> B.
-- f' will agree with f on A itself. In other words, f = f' . injectTA'
-liftTA' :: (Num k, Ord b, Show b, Algebra k b) =>
+liftTA' :: (Eq k, Num k, Ord b, Show b, Algebra k b) =>
(a -> Vect k b) -> Vect k (TensorAlgebra a) -> Vect k b
liftTA' = liftTA . linear
-- liftTA' f = linear (\(TA _ xs) -> product [f x | x <- xs])
@@ -77,7 +77,7 @@
-- |Tensor algebra is a functor from k-Vect to k-Alg.
-- The action on objects is Vect k a -> Vect k (TensorAlgebra a).
-- The action on arrows is f -> fmapTA f.
-fmapTA :: (Num k, Ord b, Show b) =>
+fmapTA :: (Eq k, Num k, Ord b, Show b) =>
(Vect k a -> Vect k b) -> Vect k (TensorAlgebra a) -> Vect k (TensorAlgebra b)
fmapTA f = liftTA (injectTA . f)
-- fmapTA f = linear (\(TA _ xs) -> product [injectTA (f (return x)) | x <- xs])
@@ -86,18 +86,18 @@
-- we obtain a functor Set -> k-Alg, the free algebra functor.
-- The action on objects is a -> Vect k (TensorAlgebra a).
-- The action on arrows is f -> fmapTA' f.
-fmapTA' :: (Num k, Ord b, Show b) =>
+fmapTA' :: (Eq k, Num k, Ord b, Show b) =>
(a -> b) -> Vect k (TensorAlgebra a) -> Vect k (TensorAlgebra b)
fmapTA' = fmapTA . fmap
-- fmapTA' f = liftTA' (injectTA' . f)
-- fmapTA' f = linear (\(TA _ xs) -> product [injectTA' (f x) | x <- xs])

-bindTA :: (Num k, Ord b, Show b) =>
+bindTA :: (Eq k, Num k, Ord b, Show b) =>
Vect k (TensorAlgebra a) -> (Vect k a -> Vect k (TensorAlgebra b)) -> Vect k (TensorAlgebra b)
bindTA = flip liftTA

-bindTA' :: (Num k, Ord b, Show b) =>
+bindTA' :: (Eq k, Num k, Ord b, Show b) =>
Vect k (TensorAlgebra a) -> (a -> Vect k (TensorAlgebra b)) -> Vect k (TensorAlgebra b)
bindTA' = flip liftTA'
@@ -121,14 +121,14 @@
munit = Sym 0 []
mmult (Sym i xs) (Sym j ys) = Sym (i+j) \$ L.sort (xs++ys)

-instance (Num k, Ord a) => Algebra k (SymmetricAlgebra a) where
+instance (Eq k, Num k, Ord a) => Algebra k (SymmetricAlgebra a) where
unit x = x *> return munit
mult = nf . fmap (\(a,b) -> a `mmult` b)

-- |Algebra morphism from tensor algebra to symmetric algebra.
-- The kernel of the morphism is the ideal generated by all
-- differences of products u&#x2297;v - v&#x2297;u.
-toSym :: (Num k, Ord a) =>
+toSym :: (Eq k, Num k, Ord a) =>
Vect k (TensorAlgebra a) -> Vect k (SymmetricAlgebra a)
toSym = linear toSym'
where toSym' (TA i xs) = return \$ Sym i (L.sort xs)
@@ -147,31 +147,31 @@
injectSym' = injectSym . return
-- injectSym' a = return (Sym 1 [a])

-liftSym :: (Num k, Ord b, Show b, Algebra k b) =>
+liftSym :: (Eq k, Num k, Ord b, Show b, Algebra k b) =>
(Vect k a -> Vect k b) -> Vect k (SymmetricAlgebra a) -> Vect k b
liftSym f = linear (\(Sym _ xs) -> product [f (return x) | x <- xs])

-liftSym' :: (Num k, Ord b, Show b, Algebra k b) =>
+liftSym' :: (Eq k, Num k, Ord b, Show b, Algebra k b) =>
(a -> Vect k b) -> Vect k (SymmetricAlgebra a) -> Vect k b
liftSym' = liftSym . linear
-- liftSym' f = linear (\(Sym _ xs) -> product [f x | x <- xs])

-fmapSym :: (Num k, Ord b, Show b) =>
+fmapSym :: (Eq k, Num k, Ord b, Show b) =>
(Vect k a -> Vect k b) -> Vect k (SymmetricAlgebra a) -> Vect k (SymmetricAlgebra b)
fmapSym f = liftSym (injectSym . f)
-- fmapSym f = linear (\(Sym _ xs) -> product [injectSym (f (return x)) | x <- xs])

-fmapSym' :: (Num k, Ord b, Show b) =>
+fmapSym' :: (Eq k, Num k, Ord b, Show b) =>
(a -> b) -> Vect k (SymmetricAlgebra a) -> Vect k (SymmetricAlgebra b)
fmapSym' = fmapSym . fmap
-- fmapSym' f = liftSym' (injectSym' . f)
-- fmapSym' f = linear (\(Sym _ xs) -> product [injectSym' (f x) | x <- xs])

-bindSym :: (Num k, Ord b, Show b) =>
+bindSym :: (Eq k, Num k, Ord b, Show b) =>
Vect k (SymmetricAlgebra a) -> (Vect k a -> Vect k (SymmetricAlgebra b)) -> Vect k (SymmetricAlgebra b)
bindSym = flip liftSym

-bindSym' :: (Num k, Ord b, Show b) =>
+bindSym' :: (Eq k, Num k, Ord b, Show b) =>
Vect k (SymmetricAlgebra a) -> (a -> Vect k (SymmetricAlgebra b)) -> Vect k (SymmetricAlgebra b)
bindSym' = flip liftSym'
@@ -190,7 +190,7 @@
show (Ext _ xs) = filter (/= '"') \$ concat \$ L.intersperse "^" \$ map show xs

-instance (Num k, Ord a) => Algebra k (ExteriorAlgebra a) where
+instance (Eq k, Num k, Ord a) => Algebra k (ExteriorAlgebra a) where
unit x = x *> return (Ext 0 [])
mult xy = nf \$ xy >>= (\(Ext i xs, Ext j ys) -> signedMerge 1 (0,[]) (i,xs) (j,ys))
where signedMerge s (k,zs) (i,x:xs) (j,y:ys) =
@@ -206,7 +206,7 @@
-- |Algebra morphism from tensor algebra to exterior algebra.
-- The kernel of the morphism is the ideal generated by all
-- self-products u&#x2297;u and sums of products u&#x2297;v + v&#x2297;u
-toExt :: (Num k, Ord a) =>
+toExt :: (Eq k, Num k, Ord a) =>
Vect k (TensorAlgebra a) -> Vect k (ExteriorAlgebra a)
toExt = linear toExt'
where toExt' (TA i xs) = let (sign,xs') = signedSort 1 True [] xs
@@ -230,31 +230,31 @@
injectExt' = injectExt . return
-- injectExt' a = return (Ext 1 [a])

-liftExt :: (Num k, Ord b, Show b, Algebra k b) =>
+liftExt :: (Eq k, Num k, Ord b, Show b, Algebra k b) =>
(Vect k a -> Vect k b) -> Vect k (ExteriorAlgebra a) -> Vect k b
liftExt f = linear (\(Ext _ xs) -> product [f (return x) | x <- xs])

-liftExt' :: (Num k, Ord b, Show b, Algebra k b) =>
+liftExt' :: (Eq k, Num k, Ord b, Show b, Algebra k b) =>
(a -> Vect k b) -> Vect k (ExteriorAlgebra a) -> Vect k b
liftExt' = liftExt . linear
-- liftExt' f = linear (\(Ext _ xs) -> product [f x | x <- xs])

-fmapExt :: (Num k, Ord b, Show b) =>
+fmapExt :: (Eq k, Num k, Ord b, Show b) =>
(Vect k a -> Vect k b) -> Vect k (ExteriorAlgebra a) -> Vect k (ExteriorAlgebra b)
fmapExt f = liftExt (injectExt . f)
-- fmapExt f = linear (\(Ext _ xs) -> product [injectExt (f (return x)) | x <- xs])

-fmapExt' :: (Num k, Ord b, Show b) =>
+fmapExt' :: (Eq k, Num k, Ord b, Show b) =>
(a -> b) -> Vect k (ExteriorAlgebra a) -> Vect k (ExteriorAlgebra b)
fmapExt' = fmapExt . fmap
-- fmapExt' f = liftExt' (injectExt' . f)
-- fmapExt' f = linear (\(Ext _ xs) -> product [injectExt' (f x) | x <- xs])

-bindExt :: (Num k, Ord b, Show b) =>
+bindExt :: (Eq k, Num k, Ord b, Show b) =>
Vect k (ExteriorAlgebra a) -> (Vect k a -> Vect k (ExteriorAlgebra b)) -> Vect k (ExteriorAlgebra b)
bindExt = flip liftExt

-bindExt' :: (Num k, Ord b, Show b) =>
+bindExt' :: (Eq k, Num k, Ord b, Show b) =>
Vect k (ExteriorAlgebra a) -> (a -> Vect k (ExteriorAlgebra b)) -> Vect k (ExteriorAlgebra b)
bindExt' = flip liftExt'
@@ -265,7 +265,7 @@
-- Kassel p67
data TensorCoalgebra c = TC Int [c] deriving (Eq,Ord,Show)

-instance (Num k, Ord c) => Coalgebra k (TensorCoalgebra c) where
+instance (Eq k, Num k, Ord c) => Coalgebra k (TensorCoalgebra c) where
counit = unwrap . linear counit'
where counit' (TC 0 []) = return () -- 1
counit' _ = zerov
@@ -278,14 +278,14 @@
-- coliftTC f is a coalgebra morphism, and f == projectTC . coliftTC f

-- projection onto the underlying vector space
-projectTC :: (Num k, Ord b) => Vect k (TensorCoalgebra b) -> Vect k b
+projectTC :: (Eq k, Num k, Ord b) => Vect k (TensorCoalgebra b) -> Vect k b
projectTC = linear projectTC' where projectTC' (TC 1 [b]) = return b; projectTC' _ = zerov
-- projectTC t = V [(b,c) | (TC 1 [b], c) <- terms t]

-- lift a vector space morphism C -> D to a coalgebra morphism C -> T'(D)
-- this function returns an approximation, valid only up to second order terms
-coliftTC :: (Num k, Coalgebra k c, Ord d) =>
+coliftTC :: (Eq k, Num k, Coalgebra k c, Ord d) =>
(Vect k c -> Vect k d) -> Vect k c -> Vect k (TensorCoalgebra d)
coliftTC f = sumf [coliftTC' i f | i <- [0..2] ]

@@ -299,7 +299,7 @@
fn' c = fmap (\(TC 1 [x], TC _ xs) -> TC n (x:xs)) \$ ( (f1' `tf` fn1') . comult) (return c)

-cobindTC :: (Num k, Ord c, Ord d) =>
+cobindTC :: (Eq k, Num k, Ord c, Ord d) =>
(Vect k (TensorCoalgebra c) -> Vect k d) -> Vect k (TensorCoalgebra c) -> Vect k (TensorCoalgebra d)
cobindTC = coliftTC

===================================================================
@@ -77,7 +77,7 @@
else if c == '-' then c:cs else '+':c:cs
-- we don't attempt sign reversal within brackets in case we have expressions like t^-1 inside the brackets

-instance Num r => Num (LaurentMPoly r) where
+instance (Eq r, Num r) => Num (LaurentMPoly r) where
LP ts + LP us = LP (mergeTerms ts us)
negate (LP ts) = LP \$ map (\(m,c)->(m,-c)) ts
LP ts * LP us = LP \$ collect \$ sortBy cmpTerm \$ [(g*h,c*d) | (g,c) <- ts, (h,d) <- us]
@@ -104,7 +104,7 @@

-- Fractional instance so that we can enter fractional coefficients
-- Only lets us divide by single terms, not any other polynomials
-instance Fractional r => Fractional (LaurentMPoly r) where
+instance (Eq r, Fractional r) => Fractional (LaurentMPoly r) where
recip (LP [(m,c)]) = LP [(recip m, recip c)]
recip _ = error "LaurentMPoly.recip: only supported for (non-zero) constants or monomials"

@@ -191,4 +191,4 @@
in if any (==0) (concatMap (\(LM m,c) -> M.elems m) us)
then Left f
else Right f'
--}
\ No newline at end of file
+-}
===================================================================
@@ -138,7 +138,7 @@

-- |The inverse of a matrix (over a field), if it exists
-inverse :: (Fractional a) => [[a]] -> Maybe [[a]]
+inverse :: (Eq a, Fractional a) => [[a]] -> Maybe [[a]]
inverse m =
let d = length m -- the dimension
i = idMx d
@@ -179,7 +179,7 @@
r:_ -> rowEchelonForm (((x:xs) <+> r) : rs)
rowEchelonForm zs@([]:_) = zs

-reducedRowEchelonForm :: (Fractional a) => [[a]] -> [[a]]
+reducedRowEchelonForm :: (Eq a, Fractional a) => [[a]] -> [[a]]
reducedRowEchelonForm m = reverse \$ reduce \$ reverse \$ rowEchelonForm m where
reduce (r:rs) = let r':rs' = reduceStep (r:rs) in r' : reduce rs' -- is this scanl or similar?
reduce [] = []
@@ -218,7 +218,7 @@
-- t (M m) = M (L.transpose m)

-- |The determinant of a matrix (over a field)
-det :: (Fractional a) => [[a]] -> a
+det :: (Eq a, Fractional a) => [[a]] -> a
det [[x]] = x
det ((x:xs):rs) =
if x /= 0
@@ -240,4 +240,4 @@
data S a
instance IntegerAsType a => IntegerAsType (S a) where
value _ = value (undefined :: a) + 1
--}
\ No newline at end of file
+-}
===================================================================
@@ -43,7 +43,7 @@
i_ :: Num k => Int -> Octonion k
i_ n = return (O n)

-instance (Num k) => Algebra k OBasis where
+instance (Eq k, Num k) => Algebra k OBasis where
unit x = x *> return (O (-1))
mult = linear m where
m (O (-1), O n) = return (O n)
@@ -57,7 +57,7 @@
5 -> -1 *> i_ ((a+4) `mod` 7) -- i_n+4 * i_n+2 == -i_n+1
6 -> -1 *> i_ ((a+2) `mod` 7) -- i_n+2 * i_n+1 == -i_n+4

-instance Num k => HasConjugation k OBasis where
+instance (Eq k, Num k) => HasConjugation k OBasis where
conj = (>>= conj') where
conj' (O n) = (if n == -1 then 1 else -1) *> return (O n)
-- ie conj = linear conj', but avoiding unnecessary nf call
===================================================================
@@ -27,7 +27,7 @@
show J = "j"
show K = "k"

-instance (Num k) => Algebra k HBasis where
+instance (Eq k, Num k) => Algebra k HBasis where
unit x = x *> return One
mult = linear mult'
where mult' (One,b) = return b
@@ -69,7 +69,7 @@

-- |If an algebra has a conjugation operation, then it has multiplicative inverses,
-- via 1/x = conj x / sqnorm x
-instance (Fractional k, Ord a, Show a, HasConjugation k a) => Fractional (Vect k a) where
+instance (Eq k, Fractional k, Ord a, Show a, HasConjugation k a) => Fractional (Vect k a) where
recip 0 = error "recip 0"
recip x = (1 / sqnorm x) *> conj x
fromRational q = fromRational q *> 1
@@ -79,10 +79,10 @@
scalarPart = coeff One

-- |The vector part of the quaternion w+xi+yj+zk is xi+yj+zk. Also called the pure part.
-vectorPart :: (Num k) => Quaternion k -> Quaternion k
+vectorPart :: (Eq k, Num k) => Quaternion k -> Quaternion k
vectorPart q = q - scalarPart q *> 1

-instance Num k => HasConjugation k HBasis where
+instance (Eq k, Num k) => HasConjugation k HBasis where
conj = (>>= conj') where
conj' One = return One
conj' imag = -1 *> return imag
@@ -126,7 +126,7 @@
-- This shows that the multiplicative group of unit quaternions is isomorphic to Spin3, the double cover of SO3.
--
-- @reprSO3 q@ returns the 3*3 matrix representing this map.
-reprSO3 :: (Fractional k) => Quaternion k -> [[k]]
+reprSO3 :: (Eq k, Fractional k) => Quaternion k -> [[k]]
reprSO3 q = reprSO3' q `asMatrix` [i,j,k]
-- It's clear from the definition that repr3' q leaves scalars invariant

@@ -145,7 +145,7 @@
-- is isomorphic to Spin4, the double cover of SO4.
--
-- @reprSO4 (l,r)@ returns the 4*4 matrix representing this map.
-reprSO4 :: (Fractional k) => (Quaternion k, Quaternion k) -> [[k]]
+reprSO4 :: (Eq k, Fractional k) => (Quaternion k, Quaternion k) -> [[k]]
reprSO4 (l,r) = reprSO4' (l,r) `asMatrix` [1,i,j,k]
-- could consider checking that l,r are unit length - except that this is hard to achieve working over Q

@@ -164,7 +164,7 @@

-- Coalgebra structure on the dual vector space to the quaternions
-- The comult is the transpose of mult
-instance Num k => Coalgebra k (Dual HBasis) where
+instance (Eq k, Num k) => Coalgebra k (Dual HBasis) where
counit = unwrap . linear counit'
where counit' (Dual One) = return ()
counit' _ = zero
@@ -204,4 +204,4 @@
counit (V ts) = sum [x | (One,x) <- ts]
comult = linear cm
where cm m = if m == One then return (m,m) else return (m,One) <+> return (One,m)
--}
\ No newline at end of file
+-}
===================================================================
@@ -148,7 +148,7 @@
-- flatsAG :: (FiniteField a) => Int -> [a] -> Int -> [[[a]]]

-- |flatsAG n fq k returns the k-flats in AG(n,Fq), where fq are the elements of Fq.
-flatsAG :: (Num a) => Int -> [a] -> Int -> [[[a]]]
+flatsAG :: (Eq a, Num a) => Int -> [a] -> Int -> [[[a]]]
flatsAG n fq k = [map tail (r : map (r <+>) rs) | r:rs <- flatsPG n fq k, head r == 1]
-- The head r == 1 condition is saying that we want points which are in the "finite" part of PG(n,Fq), not points at infinity
-- The reason we add r to each of the rs is to bring them into the "finite" part
@@ -164,7 +164,7 @@
-- linesAG :: (FiniteField a) => Int -> [a] -> [[[a]]]

-- |The lines (1-flats) in AG(n,fq)
-linesAG :: (Num a) => Int -> [a] -> [[[a]]]
+linesAG :: (Eq a, Num a) => Int -> [a] -> [[[a]]]
linesAG n fq = flatsAG n fq 1

@@ -228,4 +228,4 @@

-- Heawood graph = incidence graph of Fano plane
-heawood = to1n \$ incidenceGraphPG 2 f2
\ No newline at end of file
+heawood = to1n \$ incidenceGraphPG 2 f2
===================================================================
@@ -97,7 +97,7 @@
-- with multiplication defined by concatenation of intervals.
-- The incidence algebra can also be thought of as the vector space of functions from intervals to k, with multiplication
-- defined by the convolution (f*g)(x,y) = sum [ f(x,z) g(z,y) | x <= z <= y ].
-instance (Num k, Ord a) => Algebra k (Interval a) where
+instance (Eq k, Num k, Ord a) => Algebra k (Interval a) where
-- |Note that we are not able to give a generic definition of unit for the incidence algebra,
-- because it depends on which poset we are working in,
-- and that information is encoded at the value level rather than the type level. See unitIA.
@@ -111,14 +111,14 @@

-- |The unit of the incidence algebra of a poset
-unitIA :: (Num k, Ord t) => Poset t -> Vect k (Interval t)
+unitIA :: (Eq k, Num k, Ord t) => Poset t -> Vect k (Interval t)
unitIA poset@(Poset (set,_)) = sumv [return (Iv poset (x,x)) | x <- set]

basisIA :: Num k => Poset t -> [Vect k (Interval t)]
basisIA poset = [return (Iv poset xy) | xy <- intervals poset]

-- |The zeta function of a poset
-zetaIA :: (Num k, Ord t) => Poset t -> Vect k (Interval t)
+zetaIA :: (Eq k, Num k, Ord t) => Poset t -> Vect k (Interval t)
zetaIA poset = sumv \$ basisIA poset

-- Then for example, zeta^2 counts the number of points in each interval
@@ -132,7 +132,7 @@

-- calculate the mobius function of a poset, with memoization
-- |The Mobius function of a poset
-muIA :: (Num k, Ord t) => Poset t -> Vect k (Interval t)
+muIA :: (Eq k, Num k, Ord t) => Poset t -> Vect k (Interval t)
muIA poset@(Poset (set,po)) = sumv [mus M.! (x,y) *> return (Iv poset (x,y)) | x <- set, y <- set]
where mu (x,y) | x == y    = 1
| po x y    = negate \$ sum [mus M.! (x,z) | z <- set, po x z, po z y, z /= y]
@@ -152,7 +152,7 @@
-- Stanley, Enumerative Combinatorics I, p144
-- |The inverse of an element in the incidence algebra of a poset.
-- This is only defined for elements which are non-zero on all intervals (x,x)
-invIA :: (Fractional k, Ord t) => Vect k (Interval t) -> Maybe (Vect k (Interval t))
+invIA :: (Eq k, Fractional k, Ord t) => Vect k (Interval t) -> Maybe (Vect k (Interval t))
invIA f | f == zerov = Nothing -- error "invIA 0"
| any (==0) [f' (x,x) | x <- set] = Nothing -- error "invIA: not invertible"
| otherwise = Just g
@@ -210,7 +210,7 @@
-- INCIDENCE COALGEBRA
-- Schmitt, Incidence Hopf Algebras

-instance (Num k, Ord a) => Coalgebra k (Interval a) where
+instance (Eq k, Num k, Ord a) => Coalgebra k (Interval a) where
counit = unwrap . linear counit'
where counit' (Iv _ (x,y)) = (if x == y then 1 else 0) *> return ()
comult = linear comult'
@@ -228,7 +228,7 @@
-- rather than of intervals themselves.
-- Note that if this operation is to be performed repeatedly for the same poset,
-- then it is more efficient to use @toIsoClasses' poset@, which memoizes the isomorphism class lookup table.
-toIsoClasses :: (Num k, Ord a) => Vect k (Interval a) -> Vect k (Interval a)
+toIsoClasses :: (Eq k, Num k, Ord a) => Vect k (Interval a) -> Vect k (Interval a)
toIsoClasses v
| v == zerov = zerov
| otherwise = toIsoClasses' poset v
@@ -236,7 +236,7 @@

-- |Given a poset, @toIsoClasses' poset@ is the linear map from the incidence Hopf algebra of the poset to itself,
-- in which each interval is mapped to (the minimal representative of) its isomorphism class.
-toIsoClasses' :: (Num k, Ord a) => Poset a -> Vect k (Interval a) -> Vect k (Interval a)
+toIsoClasses' :: (Eq k, Num k, Ord a) => Poset a -> Vect k (Interval a) -> Vect k (Interval a)
toIsoClasses' poset = linear isoRep
where isoRep iv = case isoMap M.! iv of
Nothing  -> return iv
===================================================================
@@ -171,13 +171,13 @@
-- |Given a matrix, represented as a list of rows, number the columns [1..],
-- and construct the matroid whose independent sets correspond to those sets of columns which are linearly independent
-- (or in case there are repetitions, those multisets of columns which are sets, and which are linearly independent).
-vectorMatroid :: (Fractional k) => [[k]] -> Matroid Int
+vectorMatroid :: (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid = vectorMatroid' . L.transpose

-- |Given a list of vectors (or rows of a matrix), number the vectors (rows) [1..], and construct the matroid whose independent sets
-- correspond to those sets of vectors (rows) which are linearly independent
-- (or in case there are repetitions, those multisets which are sets, and which are linearly independent).
-vectorMatroid' :: (Fractional k) => [[k]] -> Matroid Int
+vectorMatroid' :: (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid' vs = fromBases (map fst vs') bs
where vs' = zip [1..] vs
bs = dfs [] [([],[],vs')]
@@ -613,7 +613,7 @@
--
-- A multiset of points in k^n is said to be affinely dependent if it contains two identical points,
-- or three collinear points, or four coplanar points, or ... - and affinely independent otherwise.
-affineMatroid :: (Fractional k) => [[k]] -> Matroid Int
+affineMatroid :: (Eq k, Fractional k) => [[k]] -> Matroid Int
affineMatroid vs = vectorMatroid' \$ map (1:) vs

-- |fromGeoRep returns a matroid from a geometric representation consisting of dependent flats of various ranks.
@@ -790,11 +790,11 @@
-- REPRESENTABILITY

-- |@matroidPG n fq@ returns the projective geometry PG(n,Fq), where fq is a list of the elements of Fq
-matroidPG :: (Fractional a) => Int -> [a] -> Matroid Int
+matroidPG :: (Eq a, Fractional a) => Int -> [a] -> Matroid Int
matroidPG n fq = vectorMatroid' \$ ptsPG n fq

-- |@matroidAG n fq@ returns the affine geometry AG(n,Fq), where fq is a list of the elements of Fq
-matroidAG :: (Fractional a) => Int -> [a] -> Matroid Int
+matroidAG :: (Eq a, Fractional a) => Int -> [a] -> Matroid Int
matroidAG n fq = vectorMatroid' \$ ptsAG n fq

@@ -889,7 +889,7 @@

-- |Find representations of the matroid m over fq. Specifically, this function will find one representative
-- of each projective equivalence class of representation.
-representations :: (Fractional fq, Ord a) => [fq] -> Matroid a -> [[[fq]]]
+representations :: (Eq fq, Fractional fq, Ord a) => [fq] -> Matroid a -> [[[fq]]]
representations fq m = map L.transpose \$ representations' (reverse \$ zip b ir) (zip b' dhash')
where fq' = tail fq -- fq \ {0}
b = head \$ bases m
@@ -905,7 +905,7 @@
representations' ls [] = [map snd \$ reverse ls]

-- |Is the matroid representable over Fq? For example, to find out whether a matroid m is binary, evaluate @isRepresentable f2 m@.
-isRepresentable :: (Fractional fq, Ord a) => [fq] -> Matroid a -> Bool
+isRepresentable :: (Eq fq, Fractional fq, Ord a) => [fq] -> Matroid a -> Bool
isRepresentable fq m = (not . null) (representations fq m)

-- |A binary matroid is a matroid which is representable over F2
===================================================================
@@ -146,7 +146,7 @@
-- This is the projective geometry PG(n,q)
-- |posetL n fq is the lattice of subspaces of the vector space Fq^n, ordered by inclusion.
-- Subspaces are represented by their reduced row echelon form.
-posetL :: FiniteField fq => Int -> [fq] -> Poset [[fq]]
+posetL :: (Eq fq, FiniteField fq) => Int -> [fq] -> Poset [[fq]]
posetL n fq = Poset ( subspaces fq n, isSubspace )

===================================================================
@@ -281,10 +281,10 @@
where h // g = let ([u],_) = quotRemMP h [g] in u

-- |@eliminate vs gs@ returns the elimination ideal obtained from the ideal generated by gs by eliminating the variables vs.
-eliminate :: (Fractional k, Ord k, MonomialConstructor m, Monomial (m v), Ord (m v)) =>
+eliminate :: (Eq k, Fractional k, Ord k, MonomialConstructor m, Monomial (m v), Ord (m v)) =>
[Vect k (m v)] -> [Vect k (m v)] -> [Vect k (m v)]
eliminate vs gs = let subs = subFst vs in eliminateFst [g `bind` subs | g <- gs]
-    where subFst :: (Num k, MonomialConstructor m, Eq (m v), Mon (m v)) =>
+    where subFst :: (Eq k, Num k, MonomialConstructor m, Eq (m v), Mon (m v)) =>
[Vect k (m v)] -> v -> Vect k (Elim2 (m v) (m v))
subFst vs = (\v -> let v' = var v in if v' `elem` vs then toElimFst v' else toElimSnd v')

@@ -386,4 +386,4 @@
-- The dimension of a variety
dim vs gs = 1 + deg (hilbertPolyQA vs gs)

-dim' gs = 1 + deg (hilbertPolyQA' gs)
\ No newline at end of file
+dim' gs = 1 + deg (hilbertPolyQA' gs)
===================================================================
@@ -157,7 +157,7 @@
lexvar v = return \$ Lex \$ M 1 [(v,1)]
-- lexvar = var

-instance (Num k, Ord v, Show v) => Algebra k (Lex v) where
+instance (Eq k, Num k, Ord v, Show v) => Algebra k (Lex v) where
unit x = x *> return munit
mult xy = nf \$ fmap (\(a,b) -> a `mmult` b) xy

@@ -191,7 +191,7 @@
glexvar v = return \$ Glex \$ M 1 [(v,1)]
-- glexvar = var

-instance (Num k, Ord v, Show v) => Algebra k (Glex v) where
+instance (Eq k, Num k, Ord v, Show v) => Algebra k (Glex v) where
unit x = x *> return munit
mult xy = nf \$ fmap (\(a,b) -> a `mmult` b) xy

@@ -227,7 +227,7 @@
grevlexvar v = return \$ Grevlex \$ M 1 [(v,1)]
-- grevlexvar = var

-instance (Num k, Ord v, Show v) => Algebra k (Grevlex v) where
+instance (Eq k, Num k, Ord v, Show v) => Algebra k (Grevlex v) where
unit x = x *> return munit
mult xy = nf \$ fmap (\(a,b) -> a `mmult` b) xy

@@ -258,7 +258,7 @@
mcoprime (Elim2 a1 b1) (Elim2 a2 b2) = mcoprime a1 a2 && mcoprime b1 b2
mdeg (Elim2 a b) = mdeg a + mdeg b

-instance (Num k, Ord a, Mon a, Ord b, Mon b) => Algebra k (Elim2 a b) where
+instance (Eq k, Num k, Ord a, Mon a, Ord b, Mon b) => Algebra k (Elim2 a b) where
unit x = x *> return munit
mult xy = nf \$ fmap (\(a,b) -> a `mmult` b) xy

@@ -286,7 +286,7 @@
-- This is occasionally useful.

-- |bind performs variable substitution
-bind :: (Num k, MonomialConstructor m, Ord a, Show a, Algebra k a) =>
+bind :: (Eq k, Num k, MonomialConstructor m, Ord a, Show a, Algebra k a) =>
Vect k (m v) -> (v -> Vect k a) -> Vect k a
v `bind` f = linear (\m -> product [f x ^ i | (x,i) <- mindices m]) v
-- V ts `bind` f = sum [c *> product [f x ^ i | (x,i) <- mindices m] | (m, c) <- ts]
@@ -298,7 +298,7 @@

-- |Evaluate a polynomial at a point.
-- For example @eval (x^2+y^2) [(x,1),(y,2)]@ evaluates x^2+y^2 at the point (x,y)=(1,2).
-eval :: (Num k, MonomialConstructor m, Eq (m v), Show v) =>
+eval :: (Eq k, Num k, MonomialConstructor m, Eq (m v), Show v) =>
Vect k (m v) -> [(Vect k (m v), k)] -> k
eval f vs = unwrap \$ f `bind` sub
where sub x = case lookup (var x) vs of
@@ -307,7 +307,7 @@

-- |Perform variable substitution on a polynomial.
-- For example @subst (x*z-y^2) [(x,u^2),(y,u*v),(z,v^2)]@ performs the substitution x -> u^2, y -> u*v, z -> v^2.
-subst :: (Num k, MonomialConstructor m, Eq (m u), Show u, Ord (m v), Show (m v), Algebra k (m v)) =>
+subst :: (Eq k, Num k, MonomialConstructor m, Eq (m u), Show u, Ord (m v), Show (m v), Algebra k (m v)) =>
Vect k (m u) -> [(Vect k (m u), Vect k (m v))] -> Vect k (m v)
subst f vs = f `bind` sub
where sub x = case lookup (var x) vs of
@@ -392,7 +392,7 @@
-- In the case where the gs are a Groebner basis for an ideal I,
-- then @f %% gs@ is the equivalence class representative of f in R/I,
-- and is zero if and only if f is in I.
-(%%) :: (Fractional k, Monomial m, Ord m, Algebra k m) =>
+(%%) :: (Eq k, Fractional k, Monomial m, Ord m, Algebra k m) =>
Vect k m -> [Vect k m] -> Vect k m
f %% gs = rewrite f gs
-- f %% gs = r where (_,r) = quotRemMP f gs
@@ -402,7 +402,7 @@
-- The instance is well-defined only for scalars, and gives an error if used on other values.
-- The purpose of this is to allow entry of fractional scalars, in expressions such as @x/2@.
-- On the other hand, an expression such as @2/x@ will return an error.
-instance (Fractional k, Monomial m, Ord m, Algebra k m) => Fractional (Vect k m) where
+instance (Eq k, Fractional k, Monomial m, Ord m, Algebra k m) => Fractional (Vect k m) where
recip (V [(m,c)]) | m == munit = V [(m,1/c)]
| otherwise = error "Polynomial recip: only defined for scalars"
fromRational x = V [(munit, fromRational x)]
===================================================================
@@ -24,7 +24,7 @@

-- type TensorAlgebra k a = Vect k [a]

-instance (Num k, Ord a) => Algebra k [a] where
+instance (Eq k, Num k, Ord a) => Algebra k [a] where
unit 0 = zero -- V []
unit x = V [(munit,x)]
mult = nf . fmap (\(a,b) -> a `mmult` b)
```

Attachment: signature.asc
Description: This is a digitally signed message part