-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Combinatorics, group theory, commutative algebra, non-commutative algebra
--
@package HaskellForMaths
@version 0.4.7
-- | A module defining classes and example instances of categories,
-- monoidal categories and braided categories
module Math.QuantumAlgebra.TensorCategory
class MCategory c where data family Ob c :: * data family Ar c :: *
id_ :: MCategory c => Ob c -> Ar c
source, target :: MCategory c => Ar c -> Ob c
(>>>) :: MCategory c => Ar c -> Ar c -> Ar c
class (MCategory a, MCategory b) => MFunctor a b
fob :: MFunctor a b => Ob a -> Ob b
far :: MFunctor a b => Ar a -> Ar b
class MCategory c => Monoidal c
tunit :: Monoidal c => Ob c
tob :: Monoidal c => Ob c -> Ob c -> Ob c
tar :: Monoidal c => Ar c -> Ar c -> Ar c
class Monoidal c => StrictMonoidal c
class Monoidal c => WeakMonoidal c
assoc :: WeakMonoidal c => Ob c -> Ob c -> Ob c -> Ar c
lunit :: WeakMonoidal c => Ob c -> Ar c
runit :: WeakMonoidal c => Ob c -> Ar c
class Monoidal c => Braided c
twist :: Braided c => Ob c -> Ob c -> Ar c
class Braided c => Symmetric c
data FinOrd
finOrdAr :: Int -> Int -> [Int] -> Ar FinOrd
data FinCard
finCardAr :: Int -> Int -> [Int] -> Ar FinCard
finPerm :: [Int] -> Ar FinCard
data Braid
t :: Int -> Int -> Ar Braid
t' :: Int -> Int -> Ar Braid
data Vect k
data Cob2
rewrite :: Ar Cob2 -> Ar Cob2
instance Eq (Ob Cob2)
instance Ord (Ob Cob2)
instance Show (Ob Cob2)
instance Eq (Ar Cob2)
instance Ord (Ar Cob2)
instance Show (Ar Cob2)
instance Eq (Ob (Vect k))
instance Ord (Ob (Vect k))
instance Show (Ob (Vect k))
instance Eq (Ar (Vect k))
instance Ord (Ar (Vect k))
instance Show (Ar (Vect k))
instance Eq (Ob Braid)
instance Ord (Ob Braid)
instance Show (Ob Braid)
instance Eq (Ar Braid)
instance Ord (Ar Braid)
instance Show (Ar Braid)
instance Eq (Ob FinCard)
instance Ord (Ob FinCard)
instance Show (Ob FinCard)
instance Eq (Ar FinCard)
instance Ord (Ar FinCard)
instance Show (Ar FinCard)
instance Eq (Ob FinOrd)
instance Ord (Ob FinOrd)
instance Show (Ob FinOrd)
instance Eq (Ar FinOrd)
instance Ord (Ar FinOrd)
instance Show (Ar FinOrd)
instance Monoidal Cob2
instance MCategory Cob2
instance Num k => MCategory (Vect k)
instance MFunctor Braid FinCard
instance Braided Braid
instance Monoidal Braid
instance MCategory Braid
instance MFunctor FinOrd FinCard
instance Monoidal FinCard
instance MCategory FinCard
instance Monoidal FinOrd
instance MCategory FinOrd
-- | A module providing functions to test for primality, and find next and
-- previous primes.
module Math.NumberTheory.Prime
-- | A (lazy) list of the primes
primes :: [Integer]
isTrialDivisionPrime :: Integer -> Bool
isMillerRabinPrime :: (Random a, Integral a) => a -> Bool
-- | Is this number prime? The algorithm consists of using trial division
-- to test for very small factors, followed if necessary by the
-- Miller-Rabin probabilistic test.
isPrime :: Integer -> Bool
notPrime :: Integer -> Bool
-- | Given n, prevPrime n returns the greatest p, p < n, such
-- that p is prime
prevPrime :: Integer -> Integer
-- | Given n, nextPrime n returns the least p, p > n, such that
-- p is prime
nextPrime :: Integer -> Integer
-- | A module defining the type and operations of free k-vector spaces over
-- a basis b (for a field k)
module Math.Algebras.VectorSpace
-- | Given a field type k and a basis type b, Vect k b is the type of the
-- free k-vector space over b. Elements (values) of Vect k b consist of
-- k-linear combinations of elements (values) of b.
--
-- In order for Vect k b to be a vector space, it is necessary that k is
-- a field (that is, an instance of Fractional). In practice, we often
-- relax this condition, and require that k is a ring (that is, an
-- instance of Num). In that case, Vect k b should more correctly be
-- called (the type of) the free k-module over b.
--
-- Most of the code requires that b is an instance of Ord. This is
-- primarily to enable us to simplify to a normal form.
newtype Vect k b
V :: [(b, k)] -> Vect k b
-- | Return the coefficient of the specified basis element in a vector
coeff :: (Num k, Eq b) => b -> Vect k b -> k
-- | Remove the term for a specified basis element from a vector
removeTerm :: (Eq k, Num k, Ord b) => b -> Vect k b -> Vect k b
-- | The zero vector
zerov :: Vect k b
-- | Addition of vectors
add :: (Eq k, Num k, Ord b) => Vect k b -> Vect k b -> Vect k b
-- | Addition of vectors (same as add)
(<+>) :: (Eq k, Num k, Ord b) => Vect k b -> Vect k b -> Vect k b
-- | Sum of a list of vectors
sumv :: (Eq k, Num k, Ord b) => [Vect k b] -> Vect k b
-- | Negation of a vector
negatev :: (Eq k, Num k) => Vect k b -> Vect k b
-- | Subtraction of vectors
(<->) :: (Eq k, Num k, Ord b) => Vect k b -> Vect k b -> Vect k b
-- | Scalar multiplication (on the left)
smultL :: (Eq k, Num k) => k -> Vect k b -> Vect k b
-- | Same as smultL. Mnemonic is "multiply through (from the left)"
(*>) :: (Eq k, Num k) => k -> Vect k b -> Vect k b
-- | Scalar multiplication on the right
smultR :: (Eq k, Num k) => Vect k b -> k -> Vect k b
-- | Same as smultR. Mnemonic is "multiply through (from the right)"
(<*) :: (Eq k, Num k) => Vect k b -> k -> Vect k b
-- | 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 :: (Eq k, Num k, Ord b) => Vect k b -> Vect k b
-- | Given a field k, (Vect k) is a functor, the "free k-vector space"
-- functor.
--
-- In the mathematical sense, this can be regarded as a functor from the
-- category Set (of sets) to the category k-Vect (of k-vector spaces). In
-- Haskell, instead of Set we have Hask, the category of Haskell types.
-- However, for our purposes it is helpful to identify Hask with Set, by
-- identifying a Haskell type with its set of inhabitants.
--
-- The type constructor (Vect k) gives the action of the functor on
-- objects in the category, taking a set (type) to a free k-vector space.
-- fmap gives the action of the functor on arrows in the category, taking
-- a function between sets (types) to a linear map between vector spaces.
--
-- Note that if f is not order-preserving, then (fmap f) is not
-- guaranteed to return results in normal form, so it may be preferable
-- to use (nf . fmap f).
-- | Given a field k, the type constructor (Vect k) is a monad, the "free
-- k-vector space monad".
--
-- In order to understand this, it is probably easiest to think of a free
-- k-vector space as a kind of container, a bit like a list, except that
-- order doesn't matter, and you're allowed arbitrary (even negative or
-- fractional) quantities of the basis elements in the container.
--
-- According to this way of thinking, return is the function that puts a
-- basis element into the vector space (container).
--
-- Given a function f from the basis of one vector space to another
-- vector space (a -> Vect k b), bind (>>=) lifts it to a
-- function (>>= f) from the first vector space to the second (Vect
-- k a -> Vect k b).
--
-- Note that in general (>>= f) applied to a vector will not return
-- a result in normal form, so it is usually preferable to use (linear f)
-- instead.
-- | A linear map between vector spaces A and B can be defined by giving
-- its action on the basis elements of A. The action on all elements of A
-- then follows by linearity.
--
-- 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 :: (Eq k, Num k, Ord b) => (a -> Vect k b) -> Vect k a -> Vect k b
-- | Trivial k is the field k considered as a k-vector space. In maths, we
-- would not normally make a distinction here, 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 an element of the field k to an element of the trivial k-vector
-- space
wrap :: (Eq k, Num k) => k -> Vect k ()
-- | Unwrap an element of the trivial k-vector space to an element of the
-- field k
unwrap :: Num k => Vect k () -> k
-- | Given a finite vector space basis b, Dual b can be used to represent a
-- basis for the dual vector space. The intention is that for a given
-- individual basis element b_i, (Dual b_i) represents the indicator
-- function for b_i, which takes b_i to 1 and all other basis elements to
-- 0.
--
-- (Note that if the basis b is infinite, then Dual b may only represent
-- a sub-basis of the dual vector space.)
newtype Dual b
Dual :: b -> Dual b
instance (Eq k, Eq b) => Eq (Vect k b)
instance (Ord k, Ord b) => Ord (Vect k b)
instance Eq EBasis
instance Ord EBasis
instance Eq b => Eq (Dual b)
instance Ord b => Ord (Dual b)
instance Show basis => Show (Dual basis)
instance Show EBasis
instance Num k => Monad (Vect k)
instance Num k => Applicative (Vect k)
instance Functor (Vect k)
instance (Show k, Eq k, Num k, Show b) => Show (Vect k b)
-- | A module defining direct sum and tensor product of vector spaces
module Math.Algebras.TensorProduct
-- | A type for constructing a basis for the direct sum of vector spaces.
-- The direct sum of Vect k a and Vect k b is Vect k (DSum a b)
type DSum a b = Either a b
-- | Injection of left summand into direct sum
i1 :: Vect k a -> Vect k (DSum a b)
-- | Injection of right summand into direct sum
i2 :: Vect k b -> Vect k (DSum a b)
-- | 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 :: (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
-- | Projection onto left summand from direct sum
p1 :: (Eq k, Num k, Ord a) => Vect k (DSum a b) -> Vect k a
-- | Projection onto right summand from direct sum
p2 :: (Eq k, Num k, Ord b) => Vect k (DSum a b) -> Vect k 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 :: (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)
-- | The direct sum of two vector space elements
dsume :: (Eq k, Num k, Ord a, Ord b) => Vect k a -> Vect k b -> Vect k (DSum a b)
-- | 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 :: (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')
-- | A type for constructing a basis for the tensor product of vector
-- spaces. The tensor product of Vect k a and Vect k b is Vect k (Tensor
-- a b)
type Tensor a b = (a, b)
-- | The tensor product of two vector space elements
te :: Num k => Vect k a -> Vect k b -> Vect k (Tensor a b)
-- | The tensor product of two linear functions
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')
assocL :: Vect k (Tensor a (Tensor b c)) -> Vect k (Tensor (Tensor a b) c)
assocR :: Vect k (Tensor (Tensor a b) c) -> Vect k (Tensor a (Tensor b c))
unitInL :: Vect k a -> Vect k (Tensor () a)
unitOutL :: Vect k (Tensor () a) -> Vect k a
unitInR :: Vect k a -> Vect k (Tensor a ())
unitOutR :: Vect k (Tensor a ()) -> Vect k a
twist :: (Eq k, Num k, Ord a, Ord b) => Vect k (Tensor a b) -> Vect k (Tensor b a)
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))
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))
distrR :: Vect k (Tensor (DSum a b) c) -> Vect k (DSum (Tensor a c) (Tensor b c))
undistrR :: Vect k (DSum (Tensor a c) (Tensor b c)) -> Vect k (Tensor (DSum a b) c)
ev :: (Eq k, Num k, Ord b) => Vect k (Tensor (Dual b) b) -> k
delta :: (Num a1, Eq a) => a -> a -> a1
reify :: (Eq k, Num k, Ord b) => Vect k (Dual b) -> (Vect k b -> k)
-- | A module defining various algebraic structures that can be defined on
-- vector spaces - specifically algebra, coalgebra, bialgebra, Hopf
-- algebra, module, comodule
module Math.Algebras.Structures
-- | Monoid
class Mon m
munit :: Mon m => m
mmult :: Mon m => m -> m -> m
-- | Caution: If we declare an instance Algebra k b, then we are saying
-- that the vector space Vect k b is a k-algebra. In other words, we are
-- saying that b is the basis for a k-algebra. So a more accurate name
-- for this class would have been AlgebraBasis.
class Algebra k b
unit :: Algebra k b => k -> Vect k b
mult :: Algebra k b => Vect k (Tensor b b) -> Vect k b
-- | Sometimes it is more convenient to work with this version of unit.
unit' :: (Eq k, Num k, Algebra k b) => Vect k () -> Vect k b
-- | An instance declaration for Coalgebra k b is saying that the vector
-- space Vect k b is a k-coalgebra.
class Coalgebra k b
counit :: Coalgebra k b => Vect k b -> k
comult :: Coalgebra k b => Vect k b -> Vect k (Tensor b b)
-- | Sometimes it is more convenient to work with this version of counit.
counit' :: (Eq k, Num k, Coalgebra k b) => Vect k b -> Vect k ()
-- | A bialgebra is an algebra which is also a coalgebra, subject to the
-- compatibility conditions that counit and comult must be algebra
-- morphisms (or equivalently, that unit and mult must be coalgebra
-- morphisms)
class (Algebra k b, Coalgebra k b) => Bialgebra k b
class Bialgebra k b => HopfAlgebra k b
antipode :: HopfAlgebra k b => Vect k b -> Vect k b
-- | 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.
-- | 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.
-- | The tensor product of k-algebras can itself be given the structure of
-- a k-algebra
-- | The tensor product of k-coalgebras can itself be given the structure
-- of a k-coalgebra
newtype SetCoalgebra b
SC :: b -> SetCoalgebra b
newtype MonoidCoalgebra m
MC :: m -> MonoidCoalgebra m
class Algebra k a => Module k a m
action :: Module k a m => Vect k (Tensor a m) -> Vect k m
(*.) :: (Module k a m, Num k) => Vect k a -> Vect k m -> Vect k m
class Coalgebra k c => Comodule k c n
coaction :: Comodule k c n => Vect k n -> Vect k (Tensor c n)
-- | A pairing is a non-degenerate bilinear form U x V -> k. We are
-- typically interested in pairings having additional properties. For
-- example:
--
--
-- - A bialgebra pairing is a pairing between bialgebras A and B such
-- that the mult in A is adjoint to the comult in B, and vice versa, and
-- the unit in A is adjoint to the counit in B, and vice versa.
-- - A Hopf pairing is a bialgebra pairing between Hopf algebras A and
-- B such that the antipodes in A and B are adjoint.
--
class HasPairing k u v
pairing :: HasPairing k u v => Vect k (Tensor u v) -> Vect k ()
-- | The pairing function with a more Haskellish type signature
pairing' :: (Num k, HasPairing k u v) => Vect k u -> Vect k v -> k
instance [incoherent] Eq b => Eq (SetCoalgebra b)
instance [incoherent] Ord b => Ord (SetCoalgebra b)
instance [incoherent] Show b => Show (SetCoalgebra b)
instance [incoherent] Eq m => Eq (MonoidCoalgebra m)
instance [incoherent] Ord m => Ord (MonoidCoalgebra m)
instance [incoherent] Show m => Show (MonoidCoalgebra m)
instance [incoherent] (Eq k, Num k, HasPairing k u v, HasPairing k u' v') => HasPairing k (Tensor u u') (Tensor v v')
instance [incoherent] (Eq k, Num k) => HasPairing k () ()
instance [incoherent] (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)
instance [incoherent] (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)
instance [incoherent] (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)
instance [incoherent] Coalgebra k c => Comodule k c c
instance [incoherent] Algebra k a => Module k a a
instance [incoherent] (Eq k, Num k, Ord m, Mon m) => Coalgebra k (MonoidCoalgebra m)
instance [incoherent] (Eq k, Num k) => Coalgebra k (SetCoalgebra b)
instance [incoherent] (Eq k, Num k) => Coalgebra k EBasis
instance [incoherent] (Eq k, Num k, Ord a, Ord b, Coalgebra k a, Coalgebra k b) => Coalgebra k (Tensor a b)
instance [incoherent] (Eq k, Num k, Ord a, Ord b, Algebra k a, Algebra k b) => Algebra k (Tensor a b)
instance [incoherent] (Eq k, Num k, Ord a, Ord b, Coalgebra k a, Coalgebra k b) => Coalgebra k (DSum a b)
instance [incoherent] (Eq k, Num k, Ord a, Ord b, Algebra k a, Algebra k b) => Algebra k (DSum a b)
instance [incoherent] (Eq k, Num k) => Coalgebra k ()
instance [incoherent] (Eq k, Num k) => Algebra k ()
instance [incoherent] (Eq k, Num k, Eq b, Ord b, Show b, Algebra k b) => Num (Vect k b)
module Math.Algebra.Group.StringRewriting
-- | Given a list of rewrite rules of the form (left,right), and a word,
-- rewrite it by repeatedly replacing any left substring in the word by
-- the corresponding right
rewrite :: Eq a => [([a], [a])] -> [a] -> [a]
rewrite1 :: Eq a => ([a], [a]) -> [a] -> Maybe [a]
splitSubstring :: Eq a => [a] -> [a] -> Maybe ([a], [a])
findOverlap :: Eq a => [a] -> [a] -> Maybe ([a], [a], [a])
knuthBendix1 :: Ord a => [([a], [a])] -> [([a], [a])]
ordpair :: Ord a => [a] -> [a] -> Maybe ([a], [a])
shortlex :: Ord a => [a] -> [a] -> Ordering
knuthBendix2 :: Ord a => [([a], [a])] -> [([a], [a])]
merge :: Ord a => [a] -> [a] -> [a]
knuthBendix3 :: Ord a => [([a], [a])] -> [([a], [a])]
-- | Implementation of the Knuth-Bendix algorithm. Given a list of
-- relations, return a confluent rewrite system. The algorithm is not
-- guaranteed to terminate.
knuthBendix :: Ord a => [([a], [a])] -> [([a], [a])]
-- | Given generators and a confluent rewrite system, return (normal forms
-- of) all elements
nfs :: Ord a => ([a], [([a], [a])]) -> [[a]]
-- | Given generators and relations, return (normal forms of) all elements
elts :: Ord a => ([a], [([a], [a])]) -> [[a]]
newtype SGen
S :: Int -> SGen
s_ :: Int -> SGen
s1 :: SGen
s2 :: SGen
s3 :: SGen
_S :: Int -> ([SGen], [([SGen], [t])])
_S' :: Int -> ([SGen], [([SGen], [SGen])])
tri :: Int -> Int -> Int -> ([Char], [([Char], [Char])])
_D :: Int -> Int -> Int -> ([Char], [([Char], [Char])])
instance Eq SGen
instance Ord SGen
instance Show SGen
module Math.Common.ListSet
toListSet :: Ord b => [b] -> [b]
isListSet :: Ord a => [a] -> Bool
union :: Ord a => [a] -> [a] -> [a]
intersect :: Ord a => [a] -> [a] -> [a]
(\\) :: Ord a => [a] -> [a] -> [a]
symDiff :: Ord a => [a] -> [a] -> [a]
disjoint :: Ord a => [a] -> [a] -> Bool
isSubset :: Ord a => [a] -> [a] -> Bool
-- | A module of simple utility functions which are used throughout the
-- rest of the library
module Math.Core.Utils
toSet :: Ord a => [a] -> [a]
sortDesc :: Ord a => [a] -> [a]
insertDesc :: Ord a => a -> [a] -> [a]
-- | The set union of two ascending lists. If both inputs are strictly
-- increasing, then the output is their union and is strictly increasing.
-- The code does not check that the lists are strictly increasing.
setUnionAsc :: Ord a => [a] -> [a] -> [a]
setUnionDesc :: Ord a => [a] -> [a] -> [a]
-- | The (multi-)set intersection of two ascending lists. If both inputs
-- are strictly increasing, then the output is the set intersection and
-- is strictly increasing. If both inputs are weakly increasing, then the
-- output is the multiset intersection (with multiplicity), and is weakly
-- increasing.
intersectAsc :: Ord a => [a] -> [a] -> [a]
-- | The multiset sum of two ascending lists. If xs and ys are ascending,
-- then multisetSumAsc xs ys == sort (xs++ys). The code does not check
-- that the lists are ascending.
multisetSumAsc :: Ord a => [a] -> [a] -> [a]
-- | The multiset sum of two descending lists. If xs and ys are descending,
-- then multisetSumDesc xs ys == sortDesc (xs++ys). The code does not
-- check that the lists are descending.
multisetSumDesc :: Ord a => [a] -> [a] -> [a]
-- | The multiset or set difference between two ascending lists. If xs and
-- ys are ascending, then diffAsc xs ys == xs \ ys, and diffAsc is more
-- efficient. If xs and ys are sets (that is, have no repetitions), then
-- diffAsc xs ys is the set difference. The code does not check that the
-- lists are ascending.
diffAsc :: Ord a => [a] -> [a] -> [a]
-- | The multiset or set difference between two descending lists. If xs and
-- ys are descending, then diffDesc xs ys == xs \ ys, and diffDesc is
-- more efficient. If xs and ys are sets (that is, have no repetitions),
-- then diffDesc xs ys is the set difference. The code does not check
-- that the lists are descending.
diffDesc :: Ord a => [a] -> [a] -> [a]
isSubsetAsc :: Ord a => [a] -> [a] -> Bool
isSubMultisetAsc :: Ord a => [a] -> [a] -> Bool
-- | Is the element in the ascending list?
--
-- With infinite lists, this can fail to terminate. For example, elemAsc
-- 1 [12,34,7/8..] would fail to terminate. However, with a list
-- of Integer, this will always terminate.
elemAsc :: Ord a => a -> [a] -> Bool
-- | Is the element not in the ascending list? (With infinite lists, this
-- can fail to terminate.)
notElemAsc :: Ord a => a -> [a] -> Bool
-- | Return all the ways to "pick one and leave the others" from a list
picks :: [a] -> [(a, [a])]
pairs :: [a] -> [(a, a)]
ordpair :: Ord t => t -> t -> (t, t)
foldcmpl :: (b -> b -> Bool) -> [b] -> Bool
isWeaklyIncreasing :: Ord t => [t] -> Bool
isStrictlyIncreasing :: Ord t => [t] -> Bool
isWeaklyDecreasing :: Ord t => [t] -> Bool
isStrictlyDecreasing :: Ord t => [t] -> Bool
cmpfst :: Ord a => (a, b) -> (a, b1) -> Ordering
eqfst :: Eq a => (a, b) -> (a, b1) -> Bool
fromBase :: Num b => b -> [b] -> b
-- | Given a set xs, represented as an ordered list,
-- powersetdfs xs returns the list of all subsets of xs, in lex
-- order
powersetdfs :: [a] -> [[a]]
-- | Given a set xs, represented as an ordered list,
-- powersetbfs xs returns the list of all subsets of xs, in
-- shortlex order
powersetbfs :: [a] -> [[a]]
-- | Given a positive integer k, and a set xs,
-- represented as a list, combinationsOf k xs returns all
-- k-element subsets of xs. The result will be in lex order, relative to
-- the order of the xs.
combinationsOf :: Int -> [a] -> [[a]]
-- | choose n k is the number of ways of choosing k distinct
-- elements from an n-set
choose :: Integral a => a -> a -> a
-- | The class of finite sets
class FinSet x
elts :: FinSet x => [x]
-- | A class representing algebraic structures having an inverse operation.
-- Note that in some cases not every element has an inverse.
class HasInverses a
inverse :: HasInverses a => a -> a
-- | A trick: x^-1 returns the inverse of x
(^-) :: (Num a, HasInverses a, Integral b) => a -> b -> a
-- | A module for working with directed graphs (digraphs). Some of the
-- functions are specifically for working with directed acyclic graphs
-- (DAGs), that is, directed graphs containing no cycles.
module Math.Combinatorics.Digraph
-- | A digraph is represented as DG vs es, where vs is the list of
-- vertices, and es is the list of edges. Edges are directed: an edge
-- (u,v) means an edge from u to v. A digraph is considered to be in
-- normal form if both es and vs are in ascending order. This is the
-- preferred form, and some functions will only work for digraphs in
-- normal form.
data Digraph v
DG :: [v] -> [(v, v)] -> Digraph v
nf :: Ord v => Digraph v -> Digraph v
vertices :: Digraph t -> [t]
edges :: Digraph t -> [(t, t)]
predecessors :: Eq t => Digraph t -> t -> [t]
successors :: Eq t => Digraph t -> t -> [t]
adjLists :: Ord a => Digraph a -> (Map a [a], Map a [a])
digraphIsos1 :: (Eq a1, Eq a) => Digraph a -> Digraph a1 -> [[(a, a1)]]
digraphIsos2 :: (Ord k1, Ord k) => Digraph k -> Digraph k1 -> [[(k, k1)]]
heightPartitionDAG :: Ord k => Digraph k -> [[k]]
isDAG :: Ord a => Digraph a -> Bool
dagIsos :: (Ord a1, Ord a) => Digraph a -> Digraph a1 -> [[(a, a1)]]
-- | Are the two DAGs isomorphic?
isDagIso :: (Ord a, Ord b) => Digraph a -> Digraph b -> Bool
perms :: [a] -> [[a]]
isoRepDAG1 :: Ord k => Digraph k -> Digraph Int
isoRepDAG2 :: (Ord t1, Ord t, Num t1, Enum t1) => Digraph t -> [(t, t1)]
isoRepDAG3 :: Ord a => Digraph a -> Digraph Int
-- | Given a directed acyclic graph (DAG), return a canonical
-- representative for its isomorphism class. isoRepDAG dag is
-- isomorphic to dag. It follows that if isoRepDAG dagA ==
-- isoRepDAG dagB then dagA is isomorphic to dagB.
-- Conversely, isoRepDAG dag is the minimal element in the
-- isomorphism class, subject to some constraints. It follows that if
-- dagA is isomorphic to dagB, then isoRepDAG dagA
-- == isoRepDAG dagB.
--
-- The algorithm of course is faster on some DAGs than others: roughly
-- speaking, it prefers "tall" DAGs (long chains) to "wide" DAGs (long
-- antichains), and it prefers asymmetric DAGs (ie those with smaller
-- automorphism groups).
isoRepDAG :: Ord a => Digraph a -> Digraph Int
instance Eq v => Eq (Digraph v)
instance Ord v => Ord (Digraph v)
instance Show v => Show (Digraph v)
instance Functor Digraph
-- | A module for finding prime factors.
module Math.NumberTheory.Factor
-- | List the prime factors of n (with multiplicity). For example:
-- >>> pfactors 60 [2,2,3,5]
--
-- This says that 60 = 2 * 2 * 3 * 5
--
-- The algorithm uses trial division to find small factors, followed if
-- necessary by the elliptic curve method to find larger factors. The
-- running time increases with the size of the second largest prime
-- factor of n. It can find 10-digit prime factors in seconds, but can
-- struggle with 20-digit prime factors.
pfactors :: Integer -> [Integer]
-- | List the prime power factors of n. For example: >>> ppfactors
-- 60 [(2,2),(3,1),(5,1)]
--
-- This says that 60 = 2^2 * 3^1 * 5^1
ppfactors :: Integer -> [(Integer, Int)]
-- | Find the prime factors of all numbers up to n. Thus pfactorsTo
-- n is equivalent to [(m, pfactors m) | m <- [1..n]],
-- except that the results are not returned in order. For example:
-- >>> pfactorsTo 10
-- [(8,[2,2,2]),(4,[2,2]),(6,[3,2]),(10,[5,2]),(2,[2]),(9,[3,3]),(3,[3]),(5,[5]),(7,[7]),(1,[])]
--
-- pfactorsTo n is significantly faster than map pfactors
-- [1..n] for larger n.
pfactorsTo :: Integer -> [(Integer, [Integer])]
-- | Find the prime power factors of all numbers up to n. Thus
-- ppfactorsTo n is equivalent to [(m, ppfactors m) | m
-- <- [1..n]], except that the results are not returned in order.
-- For example: >>> ppfactorsTo 10
-- [(8,[(2,3)]),(4,[(2,2)]),(6,[(3,1),(2,1)]),(10,[(5,1),(2,1)]),(2,[(2,1)]),(9,[(3,2)]),(3,[(3,1)]),(5,[(5,1)]),(7,[(7,1)]),(1,[])]
--
-- ppfactorsTo n is significantly faster than map ppfactors
-- [1..n] for larger n.
ppfactorsTo :: Integer -> [(Integer, [(Integer, Int)])]
instance Eq EllipticCurve
instance Show EllipticCurve
instance Eq EllipticCurvePt
instance Show EllipticCurvePt
module Math.Common.IntegerAsType
class IntegerAsType a
value :: IntegerAsType a => a -> Integer
data M a b
M :: a -> b -> M a b
data TMinus1
data TZero
data TOne
data T2
data T3
data T5
data T7
data T11
data T13
data T17
data T19
data T23
data T29
data T31
data T37
data T41
data T43
data T47
data T53
data T59
data T61
data T67
data T71
data T73
data T79
data T83
data T89
data T97
instance IntegerAsType T97
instance IntegerAsType T89
instance IntegerAsType T83
instance IntegerAsType T79
instance IntegerAsType T73
instance IntegerAsType T71
instance IntegerAsType T67
instance IntegerAsType T61
instance IntegerAsType T59
instance IntegerAsType T53
instance IntegerAsType T47
instance IntegerAsType T43
instance IntegerAsType T41
instance IntegerAsType T37
instance IntegerAsType T31
instance IntegerAsType T29
instance IntegerAsType T23
instance IntegerAsType T19
instance IntegerAsType T17
instance IntegerAsType T13
instance IntegerAsType T11
instance IntegerAsType T7
instance IntegerAsType T5
instance IntegerAsType T3
instance IntegerAsType T2
instance IntegerAsType TOne
instance IntegerAsType TZero
instance IntegerAsType TMinus1
instance (IntegerAsType a, IntegerAsType b) => IntegerAsType (M a b)
module Math.Algebra.Field.Base
-- | Q is just the rationals, but with a better show function than the
-- Prelude version
newtype Q
Q :: Rational -> Q
numeratorQ :: Q -> Integer
denominatorQ :: Q -> Integer
extendedEuclid :: Integral t => t -> t -> (t, t, t)
newtype Fp n
Fp :: Integer -> Fp n
class (Eq fq, Fractional fq) => FiniteField fq
eltsFq :: FiniteField fq => fq -> [fq]
basisFq :: FiniteField fq => fq -> [fq]
primitiveElt :: (Num a, Eq a) => [a] -> a
powers :: (Num a, Eq a) => a -> [a]
char :: [a] -> Int
-- | F2 is a type for the finite field with 2 elements
type F2 = Fp T2
-- | f2 lists the elements of F2
f2 :: [F2]
-- | F3 is a type for the finite field with 3 elements
type F3 = Fp T3
-- | f3 lists the elements of F3
f3 :: [F3]
-- | F5 is a type for the finite field with 5 elements
type F5 = Fp T5
-- | f5 lists the elements of F5
f5 :: [F5]
-- | F7 is a type for the finite field with 7 elements
type F7 = Fp T7
-- | f7 lists the elements of F7
f7 :: [F7]
type F11 = Fp T11
f11 :: [F11]
type F13 = Fp T13
f13 :: [F13]
type F17 = Fp T17
f17 :: [F17]
type F19 = Fp T19
f19 :: [F19]
type F23 = Fp T23
f23 :: [F23]
type F29 = Fp T29
f29 :: [F29]
type F31 = Fp T31
f31 :: [F31]
type F37 = Fp T37
f37 :: [F37]
type F41 = Fp T41
f41 :: [F41]
type F43 = Fp T43
f43 :: [F43]
type F47 = Fp T47
f47 :: [F47]
type F53 = Fp T53
f53 :: [F53]
type F59 = Fp T59
f59 :: [F59]
type F61 = Fp T61
f61 :: [F61]
type F67 = Fp T67
f67 :: [F67]
type F71 = Fp T71
f71 :: [F71]
type F73 = Fp T73
f73 :: [F73]
type F79 = Fp T79
f79 :: [F79]
type F83 = Fp T83
f83 :: [F83]
type F89 = Fp T89
f89 :: [F89]
type F97 = Fp T97
f97 :: [F97]
instance Eq Q
instance Ord Q
instance Num Q
instance Fractional Q
instance Eq (Fp n)
instance Ord (Fp n)
instance IntegerAsType p => FinSet (Fp p)
instance IntegerAsType p => FiniteField (Fp p)
instance IntegerAsType n => Fractional (Fp n)
instance IntegerAsType n => Num (Fp n)
instance Show (Fp n)
instance Show Q
module Math.Algebra.Field.Extension
newtype UPoly a
UP :: [a] -> UPoly a
x :: UPoly Integer
showUP :: (Show a, Num a, Eq a) => [Char] -> [a] -> [Char]
toUPoly :: (Num a, Eq a) => [a] -> UPoly a
(<+>) :: (Num a, Eq a) => [a] -> [a] -> [a]
(<*>) :: (Num t, Eq t) => [t] -> [t] -> [t]
convert :: (Num a, Eq a) => UPoly Integer -> UPoly a
deg :: UPoly a -> Int
lt :: UPoly a -> a
monomial :: Num a => a -> Int -> UPoly a
quotRemUP :: (Eq k, Fractional k) => UPoly k -> UPoly k -> (UPoly k, UPoly k)
modUP :: (Fractional k, Eq k) => UPoly k -> UPoly k -> UPoly k
extendedEuclidUP :: (Fractional k, Eq k) => UPoly k -> UPoly k -> (UPoly k, UPoly k, UPoly k)
class PolynomialAsType k poly
pvalue :: PolynomialAsType k poly => (k, poly) -> UPoly k
data ExtensionField k poly
Ext :: (UPoly k) -> ExtensionField k poly
(/>) :: (Fractional t, Eq t) => t -> UPoly t -> UPoly t
embed :: (Num k, Eq k) => UPoly Integer -> ExtensionField k poly
polys :: (Num a1, Num a, Eq a1, Eq a) => a1 -> [a] -> [UPoly a]
data ConwayF4
type F4 = ExtensionField F2 ConwayF4
f4 :: [F4]
a4 :: F4
data ConwayF8
type F8 = ExtensionField F2 ConwayF8
f8 :: [F8]
a8 :: F8
data ConwayF9
type F9 = ExtensionField F3 ConwayF9
f9 :: [F9]
a9 :: F9
data ConwayF16
type F16 = ExtensionField F2 ConwayF16
f16 :: [F16]
a16 :: F16
data ConwayF25
type F25 = ExtensionField F5 ConwayF25
f25 :: [F25]
a25 :: F25
data ConwayF27
type F27 = ExtensionField F3 ConwayF27
f27 :: [F27]
a27 :: F27
data ConwayF32
type F32 = ExtensionField F2 ConwayF32
f32 :: [F32]
a32 :: F32
frobeniusAut :: FiniteField a => a -> a
degree :: [a] -> Int
data Sqrt a
Sqrt :: a -> Sqrt a
type QSqrt2 = ExtensionField Q (Sqrt T2)
sqrt2 :: QSqrt2
type QSqrt3 = ExtensionField Q (Sqrt T3)
sqrt3 :: QSqrt3
type QSqrt5 = ExtensionField Q (Sqrt T5)
sqrt5 :: QSqrt5
type QSqrt7 = ExtensionField Q (Sqrt T7)
sqrt7 :: QSqrt7
type QSqrtMinus1 = ExtensionField Q (Sqrt TMinus1)
i :: QSqrtMinus1
type QSqrtMinus2 = ExtensionField Q (Sqrt (M TMinus1 T2))
sqrtminus2 :: QSqrtMinus2
type QSqrtMinus3 = ExtensionField Q (Sqrt (M TMinus1 T3))
sqrtminus3 :: QSqrtMinus3
type QSqrtMinus5 = ExtensionField Q (Sqrt (M TMinus1 T5))
sqrtminus5 :: QSqrtMinus5
conjugate :: ExtensionField Q (Sqrt d) -> ExtensionField Q (Sqrt d)
instance Eq a => Eq (UPoly a)
instance Ord a => Ord (UPoly a)
instance Eq k => Eq (ExtensionField k poly)
instance Ord k => Ord (ExtensionField k poly)
instance IntegerAsType n => PolynomialAsType Q (Sqrt n)
instance PolynomialAsType F2 ConwayF32
instance PolynomialAsType F3 ConwayF27
instance PolynomialAsType F5 ConwayF25
instance PolynomialAsType F2 ConwayF16
instance PolynomialAsType F3 ConwayF9
instance PolynomialAsType F2 ConwayF8
instance PolynomialAsType F2 ConwayF4
instance (FinSet fp, Eq fp, Num fp, PolynomialAsType fp poly) => FinSet (ExtensionField fp poly)
instance (FiniteField k, PolynomialAsType k poly) => FiniteField (ExtensionField k poly)
instance (Eq k, Fractional k, PolynomialAsType k poly) => Fractional (ExtensionField k poly)
instance (Eq k, Fractional k, PolynomialAsType k poly) => Num (ExtensionField k poly)
instance (Eq k, Show k, Num k) => Show (ExtensionField k poly)
instance (Eq a, Num a) => Num (UPoly a)
instance (Eq a, Show a, Num a) => Show (UPoly a)
-- | A module providing a type for non-commutative polynomials.
module Math.Algebra.NonCommutative.NCPoly
newtype Monomial v
M :: [v] -> Monomial v
divM :: Eq v => Monomial v -> Monomial v -> Maybe (Monomial v, Monomial v)
newtype NPoly r v
NP :: [(Monomial v, r)] -> NPoly r v
cmpTerm :: Ord a => (a, t) -> (a, t1) -> Ordering
mergeTerms :: (Ord a, Num a1, Eq a1) => [(a, a1)] -> [(a, a1)] -> [(a, a1)]
collect :: (Num a1, Eq a1, Eq a) => [(a, a1)] -> [(a, a1)]
data Var
X :: Var
Y :: Var
Z :: Var
-- | Create a non-commutative variable for use in forming non-commutative
-- polynomials. For example, we could define x = var "x", y = var "y".
-- Then x*y /= y*x.
var :: Num k => v -> NPoly k v
x :: NPoly Q Var
y :: NPoly Q Var
z :: NPoly Q Var
lm :: NPoly t t1 -> Monomial t1
lc :: NPoly t t1 -> t
lt :: NPoly r v -> NPoly r v
quotRemNP :: (Show v, Ord v, Fractional r, Eq r) => NPoly r v -> [NPoly r v] -> ([(NPoly r v, NPoly r v)], NPoly r v)
remNP :: (Show v, Ord v, Fractional r, Eq r) => NPoly r v -> [NPoly r v] -> NPoly r v
(%%) :: (Show v, Ord v, Fractional r, Eq r) => NPoly r v -> [NPoly r v] -> NPoly r v
remNP2 :: (Show v, Ord v, Num r, Eq r) => NPoly r v -> [NPoly r v] -> NPoly r v
toMonic :: (Show v, Ord v, Fractional r, Eq r) => NPoly r v -> NPoly r v
inject :: (Show v, Num r, Eq v, Eq r) => r -> NPoly r v
subst :: (Show v1, Show v, Show r, Ord v1, Num r1, Num r, Eq r1, Eq v, Eq r) => [(NPoly r v, NPoly r1 v1)] -> NPoly r1 v -> NPoly r1 v1
class Invertible a
inv :: Invertible a => a -> a
(^-) :: (Invertible a, Num a, Integral b) => a -> b -> a
instance Eq v => Eq (Monomial v)
instance (Eq r, Eq v) => Eq (NPoly r v)
instance Eq Var
instance Ord Var
instance Show Var
instance (Eq k, Fractional k, Ord v, Show v) => Fractional (NPoly k v)
instance (Eq r, Num r, Ord v, Show v) => Num (NPoly r v)
instance (Show r, Eq v, Show v) => Show (NPoly r v)
instance (Ord r, Ord v) => Ord (NPoly r v)
instance (Eq v, Show v) => Num (Monomial v)
instance (Eq v, Show v) => Show (Monomial v)
instance Ord v => Ord (Monomial v)
module Math.Algebra.NonCommutative.GSBasis
findOverlap :: Eq v => Monomial v -> Monomial v -> Maybe (Monomial v, Monomial v, Monomial v)
sPoly :: (Show v, Ord v, Num t, Eq t) => NPoly t v -> NPoly t v -> NPoly t v
gb1 :: (Show v, Ord v, Fractional r, Eq r) => [NPoly r v] -> [NPoly r v]
reduce :: (Show v, Ord v, Ord r, Fractional r) => [NPoly r v] -> [NPoly r v]
gb :: (Show v, Ord v, Ord r, Fractional r) => [NPoly r v] -> [NPoly r v]
gb' :: (Show v, Ord v, Ord r, Fractional r) => [NPoly r v] -> [NPoly r v]
gb2 :: (Show v, Ord v, Fractional r, Eq r) => [NPoly r v] -> [NPoly r v]
gb2' :: (Show v, Ord v, Fractional t, Eq t) => [NPoly t v] -> [(NPoly t v, NPoly t v, NPoly t v, NPoly t v)]
mbasisQA :: (Show v, Ord v, Fractional r, Eq r) => [NPoly r v] -> [NPoly r v] -> [NPoly r v]
-- | A module defining the tensor, symmetric, and exterior algebras. This
-- module has been partially superceded by Math.Algebras.TensorAlgebra,
-- which should be used in preference. This module is likely to be
-- removed at some point.
module Math.Algebra.NonCommutative.TensorAlgebra
data Basis
E :: Int -> Basis
e_ :: Int -> NPoly Q Basis
e1 :: NPoly Q Basis
e2 :: NPoly Q Basis
e3 :: NPoly Q Basis
e4 :: NPoly Q Basis
dim :: NPoly t Basis -> Int
tensorBasis :: Int -> [NPoly Q Basis]
extRelations :: Int -> [NPoly Q Basis]
extnf :: NPoly Q Basis -> NPoly Q Basis
exteriorBasis :: Int -> [NPoly Q Basis]
symRelations :: Int -> [NPoly Q Basis]
symnf :: NPoly Q Basis -> NPoly Q Basis
symmetricBasis :: Int -> [NPoly Q Basis]
weylRelations :: Int -> [NPoly Q Basis]
weylnf :: Int -> NPoly Q Basis -> NPoly Q Basis
weylBasis :: Int -> [NPoly Q Basis]
data WeylGens
X :: Int -> WeylGens
D :: Int -> WeylGens
d_ :: Int -> NPoly Q WeylGens
x_ :: Int -> NPoly Q WeylGens
d1 :: NPoly Q WeylGens
d2 :: NPoly Q WeylGens
d3 :: NPoly Q WeylGens
x1 :: NPoly Q WeylGens
x2 :: NPoly Q WeylGens
x3 :: NPoly Q WeylGens
comm :: Num a => a -> a -> a
delta :: (Num a1, Eq a) => a -> a -> a1
weylRelations' :: Int -> [NPoly Q WeylGens]
weylnf' :: NPoly Q WeylGens -> NPoly Q WeylGens
weylBasis' :: Int -> [NPoly Q WeylGens]
instance Eq Basis
instance Ord Basis
instance Eq WeylGens
instance Ord WeylGens
instance Show WeylGens
instance Show Basis
-- | A module defining the algebra of commutative polynomials over a field
-- k.
--
-- Most users should probably use Math.CommutativeAlgebra.Polynomial
-- instead, which is basically the same thing but more fully-featured.
-- This module will probably be deprecated at some point, but remains for
-- now because it has a simpler implementation which may be more helpful
-- for people wanting to understand the code.
module Math.Algebras.Commutative
data GlexMonomial v
Glex :: Int -> [(v, Int)] -> GlexMonomial v
type GlexPoly k v = Vect k (GlexMonomial v)
-- | glexVar creates a variable in the algebra of commutative polynomials
-- with Glex term ordering. For example, the following code creates
-- variables called x, y and z:
--
--
-- [x,y,z] = map glexVar ["x","y","z"] :: GlexPoly Q String
--
glexVar :: Num k => v -> GlexPoly k v
class Monomial m
var :: Monomial m => v -> Vect Q (m v)
powers :: Monomial m => m v -> [(v, Int)]
-- | 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, Eq k, Num k, Ord b, Show b, Algebra k b) => Vect k (m v) -> (v -> Vect k b) -> Vect k b
lt :: Vect t t1 -> (t1, t)
class DivisionBasis b
dividesB :: DivisionBasis b => b -> b -> Bool
divB :: DivisionBasis b => b -> b -> b
dividesT :: DivisionBasis b => (b, t) -> (b, t1) -> Bool
divT :: (DivisionBasis t, Fractional t1) => (t, t1) -> (t, t1) -> (t, t1)
quotRemMP :: (DivisionBasis b, Algebra k b, Show b, Ord b, Fractional k, Eq k) => Vect k b -> [Vect k b] -> ([Vect k b], Vect k b)
-- | (%%) reduces a polynomial with respect to a list of polynomials.
(%%) :: (Eq k, Fractional k, Ord b, Show b, Algebra k b, DivisionBasis b) => Vect k b -> [Vect k b] -> Vect k b
instance Eq v => Eq (GlexMonomial v)
instance Ord v => DivisionBasis (GlexMonomial v)
instance Monomial GlexMonomial
instance (Eq k, Num k) => Coalgebra k (GlexMonomial v)
instance (Eq k, Num k, Ord v) => Algebra k (GlexMonomial v)
instance Show v => Show (GlexMonomial v)
instance Ord v => Ord (GlexMonomial v)
-- | A module defining the affine plane and its symmetries
module Math.Algebras.AffinePlane
data XY
X :: XY
Y :: XY
x :: GlexPoly Q XY
y :: GlexPoly Q XY
data ABCD
A :: ABCD
B :: ABCD
C :: ABCD
D :: ABCD
a :: Monomial m => Vect Q (m ABCD)
d :: Monomial m => Vect Q (m ABCD)
c :: Monomial m => Vect Q (m ABCD)
b :: Monomial m => Vect Q (m ABCD)
newtype SL2 v
SL2 :: (GlexMonomial v) -> SL2 v
sl2Var :: Num k => v -> Vect k (SL2 v)
instance Eq XY
instance Ord XY
instance Eq ABCD
instance Ord ABCD
instance Eq v => Eq (SL2 v)
instance Ord v => Ord (SL2 v)
instance HopfAlgebra Q (SL2 ABCD)
instance Bialgebra Q (SL2 ABCD)
instance Coalgebra Q (SL2 ABCD)
instance Monomial SL2
instance Algebra Q (SL2 ABCD)
instance Show v => Show (SL2 v)
instance Show ABCD
instance Show XY
module Math.Algebras.LaurentPoly
data LaurentMonomial
LM :: Int -> [(String, Int)] -> LaurentMonomial
type LaurentPoly k = Vect k LaurentMonomial
lvar :: String -> LaurentPoly Q
q :: LaurentPoly Q
q' :: LaurentPoly Q
instance Eq LaurentMonomial
instance Ord LaurentMonomial
instance (Eq k, Fractional k) => Fractional (LaurentPoly k)
instance (Eq k, Num k) => Algebra k LaurentMonomial
instance Mon LaurentMonomial
instance Show LaurentMonomial
module Math.Algebras.Matrix
data Mat2
E2 :: Int -> Int -> Mat2
toMat2 :: (Num k, Eq k) => [[k]] -> Vect k Mat2
toEB2 :: (Num k, Eq k) => [k] -> Vect k EBasis
toEB :: (Num k, Eq k) => [k] -> Vect k EBasis
data Mat2'
E2' :: Int -> Int -> Mat2'
data M3
E3 :: Int -> Int -> M3
instance Eq Mat2
instance Ord Mat2
instance Show Mat2
instance Eq Mat2'
instance Ord Mat2'
instance Show Mat2'
instance Eq M3
instance Ord M3
instance Show M3
instance (Eq k, Num k) => Algebra k M3
instance (Eq k, Num k) => Coalgebra k Mat2'
instance (Eq k, Num k) => Module k Mat2 EBasis
instance (Eq k, Num k) => Algebra k Mat2
-- | A module defining the algebra of non-commutative polynomials over a
-- field k
module Math.Algebras.NonCommutative
data NonComMonomial v
NCM :: Int -> [v] -> NonComMonomial v
class Monomial m
var :: Monomial m => v -> Vect Q (m v)
powers :: (Monomial m, Eq v) => m v -> [(v, Int)]
bind :: (Monomial m, Algebra k b, Show b, Ord b, Num k, Eq v, Eq k) => Vect k (m v) -> (v -> Vect k b) -> Vect k b
type NCPoly v = Vect Q (NonComMonomial v)
class DivisionBasis m
divM :: DivisionBasis m => m -> m -> Maybe (m, m)
ncm :: [v] -> NonComMonomial v
lm :: Vect t t1 -> t1
lc :: Vect t t1 -> t
lt :: Vect k b -> Vect k b
quotRemNP :: (DivisionBasis b, Algebra k b, Show b, Ord b, Fractional k, Eq k) => Vect k b -> [Vect k b] -> ([(Vect k b, Vect k b)], Vect k b)
remNP :: (DivisionBasis b, Algebra k b, Show b, Ord b, Fractional k, Eq k) => Vect k b -> [Vect k b] -> Vect k b
(%%) :: (DivisionBasis b, Algebra k b, Show b, Ord b, Fractional k, Eq k) => Vect k b -> [Vect k b] -> Vect k b
instance Eq v => Eq (NonComMonomial v)
instance Eq v => DivisionBasis (NonComMonomial v)
instance Monomial NonComMonomial
instance (Eq k, Num k, Ord v) => Algebra k (NonComMonomial v)
instance Mon (NonComMonomial v)
instance (Eq v, Show v) => Show (NonComMonomial v)
instance Ord v => Ord (NonComMonomial v)
-- | A module defining the tensor algebra, symmetric algebra, exterior (or
-- alternating) algebra, and tensor coalgebra
module Math.Algebras.TensorAlgebra
-- | A data type representing basis elements of the tensor algebra over a
-- set/type. Elements of the tensor algebra are linear combinations of
-- iterated tensor products of elements of the set/type. If V = Vect k a
-- is the free vector space over a, then the tensor algebra T(V) = Vect k
-- (TensorAlgebra a) is isomorphic to the infinite direct sum:
--
-- T(V) = k ⊕ V ⊕ V⊗V ⊕ V⊗V⊗V ⊕ ...
data TensorAlgebra a
TA :: Int -> [a] -> TensorAlgebra a
-- | Inject an element of the free vector space V = Vect k a into the
-- tensor algebra T(V) = Vect k (TensorAlgebra a)
injectTA :: Num k => Vect k a -> Vect k (TensorAlgebra a)
-- | Inject an element of the set/type A/a into the tensor algebra T(A) =
-- Vect k (TensorAlgebra a).
injectTA' :: (Eq k, Num k) => a -> Vect k (TensorAlgebra a)
-- | Given vector spaces A = Vect k a, B = Vect k b, where B is also an
-- algebra, lift a linear map f: A -> B to an algebra morphism f':
-- T(A) -> B, 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 :: (Eq k, Num k, Ord b, Show b, Algebra k b) => (Vect k a -> Vect k b) -> Vect k (TensorAlgebra a) -> Vect k b
-- | 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' :: (Eq k, Num k, Ord b, Show b, Algebra k b) => (a -> Vect k b) -> Vect k (TensorAlgebra a) -> Vect k b
-- | 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 :: (Eq k, Num k, Ord b, Show b) => (Vect k a -> Vect k b) -> Vect k (TensorAlgebra a) -> Vect k (TensorAlgebra b)
-- | If we compose the free vector space functor Set -> k-Vect with the
-- tensor algebra functor k-Vect -> k-Alg, 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' :: (Eq k, Num k, Ord b, Show b) => (a -> b) -> Vect k (TensorAlgebra a) -> Vect k (TensorAlgebra 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' :: (Eq k, Num k, Ord b, Show b) => Vect k (TensorAlgebra a) -> (a -> Vect k (TensorAlgebra b)) -> Vect k (TensorAlgebra b)
-- | A data type representing basis elements of the symmetric algebra over
-- a set/type. The symmetric algebra is the quotient of the tensor
-- algebra by the ideal generated by all differences of products u⊗v -
-- v⊗u.
data SymmetricAlgebra a
Sym :: Int -> [a] -> SymmetricAlgebra a
-- | Algebra morphism from tensor algebra to symmetric algebra. The kernel
-- of the morphism is the ideal generated by all differences of products
-- u⊗v - v⊗u.
toSym :: (Eq k, Num k, Ord a) => Vect k (TensorAlgebra a) -> Vect k (SymmetricAlgebra a)
injectSym :: Num k => Vect k a -> Vect k (SymmetricAlgebra a)
injectSym' :: Num k => a -> Vect k (SymmetricAlgebra a)
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' :: (Eq k, Num k, Ord b, Show b, Algebra k b) => (a -> Vect k b) -> Vect k (SymmetricAlgebra a) -> Vect k 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' :: (Eq k, Num k, Ord b, Show b) => (a -> b) -> Vect k (SymmetricAlgebra a) -> Vect k (SymmetricAlgebra 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' :: (Eq k, Num k, Ord b, Show b) => Vect k (SymmetricAlgebra a) -> (a -> Vect k (SymmetricAlgebra b)) -> Vect k (SymmetricAlgebra b)
-- | A data type representing basis elements of the exterior algebra over a
-- set/type. The exterior algebra is the quotient of the tensor algebra
-- by the ideal generated by all self-products u⊗u and sums of products
-- u⊗v + v⊗u
data ExteriorAlgebra a
Ext :: Int -> [a] -> ExteriorAlgebra a
-- | Algebra morphism from tensor algebra to exterior algebra. The kernel
-- of the morphism is the ideal generated by all self-products u⊗u and
-- sums of products u⊗v + v⊗u
toExt :: (Eq k, Num k, Ord a) => Vect k (TensorAlgebra a) -> Vect k (ExteriorAlgebra a)
signedSort :: (Ord t1, Num t) => t -> Bool -> [t1] -> [t1] -> (t, [t1])
injectExt :: Num k => Vect k a -> Vect k (ExteriorAlgebra a)
injectExt' :: Num k => a -> Vect k (ExteriorAlgebra a)
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' :: (Eq k, Num k, Ord b, Show b, Algebra k b) => (a -> Vect k b) -> Vect k (ExteriorAlgebra a) -> Vect k 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' :: (Eq k, Num k, Ord b, Show b) => (a -> b) -> Vect k (ExteriorAlgebra a) -> Vect k (ExteriorAlgebra 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' :: (Eq k, Num k, Ord b, Show b) => Vect k (ExteriorAlgebra a) -> (a -> Vect k (ExteriorAlgebra b)) -> Vect k (ExteriorAlgebra b)
data TensorCoalgebra c
TC :: Int -> [c] -> TensorCoalgebra c
projectTC :: (Eq k, Num k, Ord b) => Vect k (TensorCoalgebra b) -> Vect k b
coliftTC :: (Eq k, Num k, Coalgebra k c, Ord d) => (Vect k c -> Vect k d) -> Vect k c -> Vect k (TensorCoalgebra d)
coliftTC' :: (Coalgebra k b, Ord c, Num k, Monad m, Eq k) => Int -> (m b -> Vect k c) -> Vect k b -> Vect k (TensorCoalgebra c)
cobindTC :: (Eq k, Num k, Ord c, Ord d) => (Vect k (TensorCoalgebra c) -> Vect k d) -> Vect k (TensorCoalgebra c) -> Vect k (TensorCoalgebra d)
instance Eq a => Eq (TensorAlgebra a)
instance Ord a => Ord (TensorAlgebra a)
instance Eq a => Eq (SymmetricAlgebra a)
instance Ord a => Ord (SymmetricAlgebra a)
instance Eq a => Eq (ExteriorAlgebra a)
instance Ord a => Ord (ExteriorAlgebra a)
instance Eq c => Eq (TensorCoalgebra c)
instance Ord c => Ord (TensorCoalgebra c)
instance Show c => Show (TensorCoalgebra c)
instance (Eq k, Num k, Ord c) => Coalgebra k (TensorCoalgebra c)
instance (Eq k, Num k, Ord a) => Algebra k (ExteriorAlgebra a)
instance Show a => Show (ExteriorAlgebra a)
instance (Eq k, Num k, Ord a) => Algebra k (SymmetricAlgebra a)
instance Ord a => Mon (SymmetricAlgebra a)
instance Show a => Show (SymmetricAlgebra a)
instance (Eq k, Num k, Ord a) => Algebra k (TensorAlgebra a)
instance Mon (TensorAlgebra a)
instance Show a => Show (TensorAlgebra a)
module Math.Projects.KnotTheory.LaurentMPoly
newtype LaurentMonomial
LM :: (Map String Q) -> LaurentMonomial
degLM :: LaurentMonomial -> Q
denominatorLM :: LaurentMonomial -> LaurentMonomial
lcmLM :: LaurentMonomial -> LaurentMonomial -> LaurentMonomial
divLM :: LaurentMonomial -> LaurentMonomial -> Maybe LaurentMonomial
newtype LaurentMPoly r
LP :: [(LaurentMonomial, r)] -> LaurentMPoly r
cmpTerm :: Ord a => (a, t) -> (a, t1) -> Ordering
mergeTerms :: (Ord a, Num a1, Eq a1) => [(a, a1)] -> [(a, a1)] -> [(a, a1)]
collect :: (Num a1, Eq a1, Eq a) => [(a, a1)] -> [(a, a1)]
lm :: LaurentMPoly t -> LaurentMonomial
lc :: LaurentMPoly t -> t
lt :: LaurentMPoly r -> LaurentMPoly r
quotRemLP :: (Fractional t, Eq t) => LaurentMPoly t -> LaurentMPoly t -> (LaurentMPoly t, LaurentMPoly t)
reduceLP :: (Fractional t, Eq t) => LaurentMPoly t -> LaurentMPoly t -> LaurentMPoly t
var :: Num r => String -> LaurentMPoly r
t :: LaurentMPoly Q
x :: LaurentMPoly Q
y :: LaurentMPoly Q
z :: LaurentMPoly Q
denominatorLP :: Num r => LaurentMPoly t -> LaurentMPoly r
inject :: (Num r, Eq r) => r -> LaurentMPoly r
sqrtvar :: Num r => String -> LaurentMPoly r
subst :: (Show r, Fractional r, Eq r) => [(LaurentMPoly r, LaurentMPoly r)] -> LaurentMPoly r -> LaurentMPoly r
(^^^) :: (Show t, Fractional t, Eq t) => LaurentMPoly t -> Q -> LaurentMPoly t
instance Eq LaurentMonomial
instance Eq r => Eq (LaurentMPoly r)
instance Ord r => Ord (LaurentMPoly r)
instance (Eq r, Fractional r) => Fractional (LaurentMPoly r)
instance (Eq r, Num r) => Num (LaurentMPoly r)
instance Show r => Show (LaurentMPoly r)
instance Fractional LaurentMonomial
instance Num LaurentMonomial
instance Show LaurentMonomial
instance Ord LaurentMonomial
module Math.Projects.KnotTheory.Braid
type LPQ = LaurentMPoly Q
data BraidGens
S :: Int -> BraidGens
s_ :: Int -> NPoly LPQ BraidGens
s1 :: NPoly LPQ BraidGens
s2 :: NPoly LPQ BraidGens
s3 :: NPoly LPQ BraidGens
s4 :: NPoly LPQ BraidGens
writhe :: NPoly t BraidGens -> Int
k3_1 :: NPoly LPQ BraidGens
k4_1 :: NPoly LPQ BraidGens
k5_1 :: NPoly LPQ BraidGens
k7_1 :: NPoly LPQ BraidGens
instance Eq BraidGens
instance Ord BraidGens
instance Invertible (NPoly LPQ BraidGens)
instance Show BraidGens
instance Invertible LPQ
module Math.Projects.KnotTheory.TemperleyLieb
data TemperleyLiebGens
E :: Int -> TemperleyLiebGens
e_ :: Int -> NPoly LPQ TemperleyLiebGens
d :: LaurentMPoly Q
d' :: NPoly LPQ TemperleyLiebGens
e1 :: NPoly LPQ TemperleyLiebGens
e2 :: NPoly LPQ TemperleyLiebGens
e3 :: NPoly LPQ TemperleyLiebGens
e4 :: NPoly LPQ TemperleyLiebGens
tlRelations :: Int -> [NPoly LPQ TemperleyLiebGens]
dimTL :: NPoly t TemperleyLiebGens -> Int
tlnf :: NPoly LPQ TemperleyLiebGens -> NPoly LPQ TemperleyLiebGens
tlBasis :: Int -> [NPoly LPQ TemperleyLiebGens]
tr' :: Int -> Monomial TemperleyLiebGens -> LaurentMPoly Q
tr :: Int -> NPoly (LaurentMPoly Q) TemperleyLiebGens -> LaurentMPoly Q
a :: LaurentMPoly Q
a' :: NPoly LPQ TemperleyLiebGens
fromBraid :: NPoly LPQ BraidGens -> NPoly LPQ TemperleyLiebGens
jones :: Int -> NPoly LPQ BraidGens -> LaurentMPoly Q
instance Eq TemperleyLiebGens
instance Ord TemperleyLiebGens
instance Show TemperleyLiebGens
module Math.Projects.KnotTheory.IwahoriHecke
data IwahoriHeckeGens
T :: Int -> IwahoriHeckeGens
t_ :: Int -> NPoly LPQ IwahoriHeckeGens
t1 :: NPoly LPQ IwahoriHeckeGens
t2 :: NPoly LPQ IwahoriHeckeGens
t3 :: NPoly LPQ IwahoriHeckeGens
t4 :: NPoly LPQ IwahoriHeckeGens
q :: LaurentMPoly Q
z :: LaurentMPoly Q
q' :: NPoly LPQ IwahoriHeckeGens
z' :: NPoly LPQ IwahoriHeckeGens
ihRelations :: Int -> [NPoly LPQ IwahoriHeckeGens]
dimIH :: NPoly t IwahoriHeckeGens -> Int
ihnf :: NPoly LPQ IwahoriHeckeGens -> NPoly LPQ IwahoriHeckeGens
ihBasis :: Int -> [NPoly LPQ IwahoriHeckeGens]
tau' :: Int -> (Monomial IwahoriHeckeGens, LPQ) -> LPQ
tau :: Int -> NPoly LPQ IwahoriHeckeGens -> LPQ
fromBraid :: NPoly LPQ BraidGens -> NPoly LPQ IwahoriHeckeGens
homfly :: Int -> NPoly LPQ BraidGens -> LaurentMPoly Q
i :: LPQ
l :: LPQ
m :: LPQ
homfly' :: Int -> NPoly LPQ BraidGens -> LaurentMPoly Q
homfly'' :: Int -> NPoly LPQ BraidGens -> LaurentMPoly (LaurentMPoly Q)
coeffs :: (Fractional t, Eq t) => LaurentMPoly t -> LaurentMPoly t -> [LaurentMPoly t]
jones' :: Int -> NPoly LPQ BraidGens -> LaurentMPoly Q
instance Eq IwahoriHeckeGens
instance Ord IwahoriHeckeGens
instance Invertible (NPoly LPQ IwahoriHeckeGens)
instance Show IwahoriHeckeGens
module Math.QuantumAlgebra.OrientedTangle
data Oriented
Plus :: Oriented
Minus :: Oriented
data HorizDir
ToL :: HorizDir
ToR :: HorizDir
data OrientedTangle
idV :: a -> a
idV' :: a -> a
evalV :: (EBasis, EBasis) -> Vect (LaurentPoly Q) ()
evalV' :: (EBasis, EBasis) -> Vect (LaurentPoly Q) ()
coevalV :: (Num k, Eq k) => Int -> Vect k (Tensor EBasis EBasis)
coevalV' :: (Num k, Eq k) => Int -> Vect k (Tensor EBasis EBasis)
lambda :: Integral b => b -> LaurentPoly Q
c :: Integral b => b -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
c' :: Integral b => b -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
testcc' :: Integral b => b -> Vect (LaurentPoly Q) (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
mu :: Integral b => b -> EBasis -> Vect (LaurentPoly Q) EBasis
mu' :: Integral b => b -> EBasis -> Vect (LaurentPoly Q) EBasis
capRL :: (Num k, Eq k) => Int -> Vect k (Tensor EBasis EBasis)
capLR :: Int -> Vect (LaurentPoly Q) (EBasis, EBasis)
cupRL :: Int -> (EBasis, EBasis) -> Vect (LaurentPoly Q) ()
cupLR :: Int -> (EBasis, EBasis) -> Vect (LaurentPoly Q) ()
xplus :: Integral b => b -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
xminus :: Integral b => b -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
yplus :: Int -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
yminus :: Int -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
tplus :: Int -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
tminus :: Int -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
zplus :: Int -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
zminus :: Int -> (EBasis, EBasis) -> Vect (LaurentPoly Q) (EBasis, EBasis)
oloop :: Int -> Vect (LaurentPoly Q) ()
otrefoil :: Int -> Vect (LaurentPoly Q) ()
otrefoil' :: Int -> Vect (LaurentPoly Q) ()
instance Eq Oriented
instance Ord Oriented
instance Show Oriented
instance Eq HorizDir
instance Ord HorizDir
instance Show HorizDir
instance Eq (Ob OrientedTangle)
instance Ord (Ob OrientedTangle)
instance Show (Ob OrientedTangle)
instance Eq (Ar OrientedTangle)
instance Ord (Ar OrientedTangle)
instance Show (Ar OrientedTangle)
instance Monoidal OrientedTangle
instance MCategory OrientedTangle
-- | A module defining the quantum plane and its symmetries
module Math.QuantumAlgebra.QuantumPlane
qvar :: Monomial m => v -> Vect (LaurentPoly Q) (m v)
a :: Monomial m => Vect (LaurentPoly Q) (m [Char])
b :: Monomial m => Vect (LaurentPoly Q) (m [Char])
c :: Monomial m => Vect (LaurentPoly Q) (m [Char])
d :: Monomial m => Vect (LaurentPoly Q) (m [Char])
detq :: (Monomial m, Algebra (Vect Q LaurentMonomial) (m [Char]), Show (m [Char]), Ord (m [Char])) => Vect (LaurentPoly Q) (m [Char])
x :: Monomial m => Vect (LaurentPoly Q) (m [Char])
y :: Monomial m => Vect (LaurentPoly Q) (m [Char])
u :: Monomial m => Vect (LaurentPoly Q) (m [Char])
v :: Monomial m => Vect (LaurentPoly Q) (m [Char])
aq20 :: (Monomial m, Algebra (Vect Q LaurentMonomial) (m [Char]), Show (m [Char]), Ord (m [Char])) => [Vect (LaurentPoly Q) (m [Char])]
newtype Aq20 v
Aq20 :: (NonComMonomial v) -> Aq20 v
aq02 :: (Monomial m, Algebra (Vect Q LaurentMonomial) (m [Char]), Show (m [Char]), Ord (m [Char])) => [Vect (LaurentPoly Q) (m [Char])]
newtype Aq02 v
Aq02 :: (NonComMonomial v) -> Aq02 v
m2q :: (Monomial m, Algebra (Vect Q LaurentMonomial) (m [Char]), Show (m [Char]), Ord (m [Char])) => [Vect (LaurentPoly Q) (m [Char])]
newtype M2q v
M2q :: (NonComMonomial v) -> M2q v
sl2q :: (Monomial m, Algebra (Vect Q LaurentMonomial) (m [Char]), Show (m [Char]), Ord (m [Char])) => [Vect (LaurentPoly Q) (m [Char])]
newtype SL2q v
SL2q :: (NonComMonomial v) -> SL2q v
yb :: (Algebra (Vect Q LaurentMonomial) t, Show t, Ord t) => Vect (LaurentPoly Q) (t, t) -> Vect (LaurentPoly Q) (t, t)
instance Eq v => Eq (Aq20 v)
instance Ord v => Ord (Aq20 v)
instance Eq v => Eq (Aq02 v)
instance Ord v => Ord (Aq02 v)
instance Eq v => Eq (M2q v)
instance Ord v => Ord (M2q v)
instance Eq v => Eq (SL2q v)
instance Ord v => Ord (SL2q v)
instance HopfAlgebra (LaurentPoly Q) (SL2q String)
instance Bialgebra (LaurentPoly Q) (SL2q String)
instance Coalgebra (LaurentPoly Q) (SL2q String)
instance Algebra (LaurentPoly Q) (SL2q String)
instance Monomial SL2q
instance (Eq v, Show v) => Show (SL2q v)
instance Comodule (LaurentPoly Q) (M2q String) (Aq20 String)
instance Bialgebra (LaurentPoly Q) (M2q String)
instance Coalgebra (LaurentPoly Q) (M2q String)
instance Algebra (LaurentPoly Q) (M2q String)
instance Monomial M2q
instance (Eq v, Show v) => Show (M2q v)
instance Algebra (LaurentPoly Q) (Aq02 String)
instance Monomial Aq02
instance (Eq v, Show v) => Show (Aq02 v)
instance Algebra (LaurentPoly Q) (Aq20 String)
instance Monomial Aq20
instance (Eq v, Show v) => Show (Aq20 v)
-- | A module defining the category of tangles, and representations into
-- the category of vector spaces (specifically, knot invariants).
module Math.QuantumAlgebra.Tangle
data Tangle
data Oriented
Plus :: Oriented
Minus :: Oriented
type TangleRep b = Vect (LaurentPoly Q) b
cap :: [Oriented] -> TangleRep [Oriented]
cup :: [Oriented] -> TangleRep [Oriented]
over :: [Oriented] -> TangleRep [Oriented]
under :: [Oriented] -> TangleRep [Oriented]
loop :: Vect (LaurentPoly Q) [Oriented]
trefoil :: Vect (LaurentPoly Q) [Oriented]
kauffman :: Ar Tangle -> TangleRep [Oriented] -> TangleRep [Oriented]
loopT :: Ar Tangle
trefoilT :: Ar Tangle
instance Eq Oriented
instance Ord Oriented
instance Show Oriented
instance Eq (Ob Tangle)
instance Ord (Ob Tangle)
instance Show (Ob Tangle)
instance Eq (Ar Tangle)
instance Ord (Ar Tangle)
instance Show (Ar Tangle)
instance Monoidal Tangle
instance MCategory Tangle
instance (Eq k, Num k, Ord a) => Algebra k [a]
instance Mon [a]
-- | A module defining the field Q of rationals and the small finite fields
-- (Galois fields) F2, F3, F4, F5, F7, F8, F9, F11, F13, F16, F17, F19,
-- F23, F25.
--
-- Given a prime power q, Fq is the type representing elements of the
-- field (eg F4), fq is a list of the elements of the field,
-- beginning 0,1,... (eg f4), and for prime power fields, aq is
-- a primitive element, which generates the multiplicative group (eg
-- a4).
--
-- The design philosophy is that fq, the list of elements, represents the
-- field. Thus, many functions elsewhere in the library expect to take fq
-- as an argument, telling them which field to work over.
module Math.Core.Field
-- | Q is just the rationals, but with a better show function than the
-- Prelude version
newtype Q
Q :: Rational -> Q
numeratorQ :: Q -> Integer
denominatorQ :: Q -> Integer
-- | F2 is a type for the finite field with 2 elements
newtype F2
F2 :: Int -> F2
-- | f2 is a list of the elements of F2
f2 :: [F2]
-- | F3 is a type for the finite field with 3 elements
newtype F3
F3 :: Int -> F3
-- | f3 is a list of the elements of F3
f3 :: [F3]
-- | F5 is a type for the finite field with 5 elements
newtype F5
F5 :: Int -> F5
-- | f5 is a list of the elements of F5
f5 :: [F5]
-- | F7 is a type for the finite field with 7 elements
newtype F7
F7 :: Int -> F7
-- | f7 is a list of the elements of F7
f7 :: [F7]
-- | F11 is a type for the finite field with 11 elements
newtype F11
F11 :: Int -> F11
-- | f11 is a list of the elements of F11
f11 :: [F11]
-- | F13 is a type for the finite field with 13 elements
newtype F13
F13 :: Int -> F13
-- | f13 is a list of the elements of F13
f13 :: [F13]
-- | F17 is a type for the finite field with 17 elements
newtype F17
F17 :: Int -> F17
-- | f17 is a list of the elements of F17
f17 :: [F17]
-- | F19 is a type for the finite field with 19 elements
newtype F19
F19 :: Int -> F19
-- | f19 is a list of the elements of F19
f19 :: [F19]
-- | F23 is a type for the finite field with 23 elements
newtype F23
F23 :: Int -> F23
-- | f23 is a list of the elements of F23
f23 :: [F23]
-- | F4 is a type for the finite field with 4 elements. F4 is represented
-- as the extension of F2 by an element a4 satisfying x^2+x+1 = 0
newtype F4
F4 :: Int -> F4
-- | a4 is a primitive element for F4 as an extension over F2. a4 satisfies
-- x^2+x+1 = 0.
a4 :: F4
-- | f4 is a list of the elements of F4
f4 :: [F4]
powers :: (Num a, Eq a) => a -> [a]
-- | F8 is a type for the finite field with 8 elements. F8 is represented
-- as the extension of F2 by an element a8 satisfying x^3+x+1 = 0
newtype F8
F8 :: Int -> F8
-- | a8 is a primitive element for F8 as an extension over F2. a8 satisfies
-- x^3+x+1 = 0.
a8 :: F8
-- | f8 is a list of the elements of F8
f8 :: [F8]
-- | F9 is a type for the finite field with 9 elements. F9 is represented
-- as the extension of F3 by an element a9 satisfying x^2+2x+2 = 0
newtype F9
F9 :: Int -> F9
-- | a9 is a primitive element for F9 as an extension over F3. a9 satisfies
-- x^2+2x+2 = 0.
a9 :: F9
-- | f9 is a list of the elements of F9
f9 :: [F9]
-- | F16 is a type for the finite field with 16 elements. F16 is
-- represented as the extension of F2 by an element a16 satisfying
-- x^4+x+1 = 0
newtype F16
F16 :: Int -> F16
-- | a16 is a primitive element for F16 as an extension over F2. a16
-- satisfies x^4+x+1 = 0.
a16 :: F16
-- | f16 is a list of the elements of F16
f16 :: [F16]
-- | F25 is a type for the finite field with 25 elements. F25 is
-- represented as the extension of F5 by an element a25 satisfying
-- x^2+4x+2 = 0
newtype F25
F25 :: Int -> F25
-- | a25 is a primitive element for F25 as an extension over F5. a25
-- satisfies x^2+4x+2 = 0.
a25 :: F25
-- | f25 is a list of the elements of F25
f25 :: [F25]
instance Eq Q
instance Ord Q
instance Num Q
instance Fractional Q
instance Eq F2
instance Ord F2
instance Eq F3
instance Ord F3
instance Eq F5
instance Ord F5
instance Eq F7
instance Ord F7
instance Eq F11
instance Ord F11
instance Eq F13
instance Ord F13
instance Eq F17
instance Ord F17
instance Eq F19
instance Ord F19
instance Eq F23
instance Ord F23
instance Eq F4
instance Ord F4
instance Eq F8
instance Ord F8
instance Eq F9
instance Ord F9
instance Eq F16
instance Ord F16
instance Eq F25
instance Ord F25
instance FinSet F25
instance Fractional F25
instance Num F25
instance Show F25
instance FinSet F16
instance Fractional F16
instance Num F16
instance Show F16
instance FinSet F9
instance Fractional F9
instance Num F9
instance Show F9
instance FinSet F8
instance Fractional F8
instance Num F8
instance Show F8
instance FinSet F4
instance Fractional F4
instance Num F4
instance Show F4
instance FinSet F23
instance Fractional F23
instance Num F23
instance Show F23
instance FinSet F19
instance Fractional F19
instance Num F19
instance Show F19
instance FinSet F17
instance Fractional F17
instance Num F17
instance Show F17
instance FinSet F13
instance Fractional F13
instance Num F13
instance Show F13
instance FinSet F11
instance Fractional F11
instance Num F11
instance Show F11
instance FinSet F7
instance Fractional F7
instance Num F7
instance Show F7
instance FinSet F5
instance Fractional F5
instance Num F5
instance Show F5
instance FinSet F3
instance Fractional F3
instance Num F3
instance Show F3
instance FinSet F2
instance Fractional F2
instance Num F2
instance Show F2
instance Show Q
-- | A module defining the algebra of commutative polynomials over a field
-- k. Polynomials are represented as the free k-vector space with the
-- monomials as basis.
--
-- A monomial ordering is required to specify how monomials are to be
-- ordered. The Lex, Glex, and Grevlex monomial orders are defined, with
-- the possibility to add others.
--
-- In order to make use of this module, some variables must be defined,
-- for example:
--
--
-- [t,u,v,x,y,z] = map glexvar ["t","u","v","x","y","z"]
--
module Math.CommutativeAlgebra.Polynomial
-- | In order to work with monomials, we need to be able to multiply them
-- and divide them. Multiplication is defined by the Mon (monoid) class.
-- Division is defined in this class. The functions here are primarily
-- intended for internal use only.
class (Eq m, Show m, Mon m) => Monomial m
mdivides :: Monomial m => m -> m -> Bool
mdiv :: Monomial m => m -> m -> m
mgcd :: Monomial m => m -> m -> m
mlcm :: Monomial m => m -> m -> m
mcoprime :: Monomial m => m -> m -> Bool
mdeg :: Monomial m => m -> Int
mproperlydivides :: Monomial m => m -> m -> Bool
-- | We want to be able to construct monomials over any set of variables
-- that we choose. Although we will often use String as the type of our
-- variables, it is useful to define polymorphic types for monomials.
class MonomialConstructor m
mvar :: MonomialConstructor m => v -> m v
mindices :: MonomialConstructor m => m v -> [(v, Int)]
-- | var v creates a variable in the vector space of polynomials.
-- For example, if we want to work in Q[x,y,z], we might define:
--
--
-- [x,y,z] = map var ["x","y","z"] :: [GlexPoly Q String]
--
--
-- Notice that, in general, it is necessary to provide a type annotation
-- so that the compiler knows which field and which term order to use.
var :: (Num k, MonomialConstructor m) => v -> Vect k (m v)
-- | The underlying implementation of monomials in variables of type v.
-- Most often, we will be interested in MonImpl String, with the variable
-- "x" represented by M 1 [("x",1)]. However, other types can be used
-- instead.
--
-- No Ord instance is defined for MonImpl v, so it cannot be used as the
-- basis for a free vector space of polynomials. Instead, several
-- different newtype wrappers are provided, corresponding to different
-- monomial orderings.
data MonImpl v
M :: Int -> [(v, Int)] -> MonImpl v
-- | A type representing monomials with Lex ordering.
--
-- Lex stands for lexicographic ordering. For example, in Lex ordering,
-- monomials up to degree two would be ordered as follows:
-- x^2+xy+xz+x+y^2+yz+y+z^2+z+1.
newtype Lex v
Lex :: (MonImpl v) -> Lex v
-- | A type representing polynomials with Lex term ordering.
type LexPoly k v = Vect k (Lex v)
-- | lexvar v creates a variable in the algebra of commutative
-- polynomials over Q with Lex term ordering. It is provided as a
-- shortcut, to avoid having to provide a type annotation, as with
-- var. For example, the following code creates variables called
-- x, y and z:
--
--
-- [x,y,z] = map lexvar ["x","y","z"]
--
lexvar :: v -> LexPoly Q v
-- | A type representing monomials with Glex ordering.
--
-- Glex stands for graded lexicographic. Thus monomials are ordered first
-- by degree, then by lexicographic order. For example, in Glex ordering,
-- monomials up to degree two would be ordered as follows:
-- x^2+xy+xz+y^2+yz+z^2+x+y+z+1.
newtype Glex v
Glex :: (MonImpl v) -> Glex v
-- | A type representing polynomials with Glex term ordering.
type GlexPoly k v = Vect k (Glex v)
-- | glexvar v creates a variable in the algebra of commutative
-- polynomials over Q with Glex term ordering. It is provided as a
-- shortcut, to avoid having to provide a type annotation, as with
-- var. For example, the following code creates variables called
-- x, y and z:
--
--
-- [x,y,z] = map glexvar ["x","y","z"]
--
glexvar :: v -> GlexPoly Q v
-- | A type representing monomials with Grevlex ordering.
--
-- Grevlex stands for graded reverse lexicographic. Thus monomials are
-- ordered first by degree, then by reverse lexicographic order. For
-- example, in Grevlex ordering, monomials up to degree two would be
-- ordered as follows: x^2+xy+y^2+xz+yz+z^2+x+y+z+1.
--
-- In general, Grevlex leads to the smallest Groebner bases.
newtype Grevlex v
Grevlex :: (MonImpl v) -> Grevlex v
-- | A type representing polynomials with Grevlex term ordering.
type GrevlexPoly k v = Vect k (Grevlex v)
-- | grevlexvar v creates a variable in the algebra of commutative
-- polynomials over Q with Grevlex term ordering. It is provided as a
-- shortcut, to avoid having to provide a type annotation, as with
-- var. For example, the following code creates variables called
-- x, y and z:
--
--
-- [x,y,z] = map grevlexvar ["x","y","z"]
--
grevlexvar :: v -> GrevlexPoly Q v
data Elim2 a b
Elim2 :: !a -> !b -> Elim2 a b
-- | Given (Num k, MonomialConstructor m), then Vect k (m v) is the free
-- commutative algebra over v. As such, it is a monad (in the
-- mathematical sense). The following pseudo-code (not legal Haskell)
-- shows how this would work:
--
--
-- instance (Num k, Monomial m) => Monad (\v -> Vect k (m v)) where
-- return = var
-- (>>=) = bind
--
--
-- bind corresponds to variable substitution, so v `bind` f
-- returns the result of making the substitutions encoded in f into v.
--
-- Note that the type signature is slightly more general than that
-- required by (>>=). For a monad, we would only require:
--
--
-- bind :: (MonomialConstructor m, Num k, Ord (m v), Show (m v), Algebra k (m v)) =>
-- Vect k (m u) -> (u -> Vect k (m v)) -> Vect k (m v)
--
--
-- Instead, the given type signature allows us to substitute in elements
-- of any algebra. This is occasionally useful.
--
-- bind performs variable substitution
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
flipbind :: (MonomialConstructor m, Algebra k b, Show b, Ord b, Num k, Eq k) => (v -> Vect k b) -> Vect k (m v) -> Vect k b
-- | 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 :: (Eq k, Num k, MonomialConstructor m, Eq (m v), Show v) => Vect k (m v) -> [(Vect k (m v), k)] -> k
-- | 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 :: (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)
-- | List the variables used in a polynomial
vars :: (Num k, Ord k, MonomialConstructor m, Ord (m v)) => Vect k (m v) -> [Vect k (m v)]
lt :: Vect t t1 -> (t1, t)
lm :: Vect b c -> c
lc :: Vect c a -> c
deg :: Monomial m => Vect t m -> Int
toMonic :: (Algebra k b, Show b, Ord b, Fractional k, Eq k) => Vect k b -> Vect k b
tdivides :: Monomial m => (m, t) -> (m, t1) -> Bool
tdiv :: (Monomial t, Fractional t1) => (t, t1) -> (t, t1) -> (t, t1)
tgcd :: (Monomial t2, Num t3) => (t2, t) -> (t2, t1) -> (t2, t3)
tmult :: (Mon t, Num t1) => (t, t1) -> (t, t1) -> (t, t1)
(*->) :: (Mon b, Num k) => (b, k) -> Vect k b -> Vect k b
quotRemMP :: (Monomial b, Algebra k b, Ord b, Fractional k, Eq k) => Vect k b -> [Vect k b] -> ([Vect k b], Vect k b)
rewrite :: (Monomial b, Algebra k b, Ord b, Fractional k, Eq k) => Vect k b -> [Vect k b] -> Vect k b
-- | f %% gs is the reduction of a polynomial f with respect to a
-- list of polynomials gs. 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.
(%%) :: (Eq k, Fractional k, Monomial m, Ord m, Algebra k m) => Vect k m -> [Vect k m] -> Vect k m
-- | As a convenience, a partial instance of Fractional is defined for
-- polynomials. 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 Eq v => Eq (MonImpl v)
instance Functor MonImpl
instance Eq v => Eq (Lex v)
instance Functor Lex
instance Ord v => Mon (Lex v)
instance (Ord v, Show v) => Monomial (Lex v)
instance MonomialConstructor Lex
instance Eq v => Eq (Glex v)
instance Functor Glex
instance Ord v => Mon (Glex v)
instance (Ord v, Show v) => Monomial (Glex v)
instance MonomialConstructor Glex
instance Eq v => Eq (Grevlex v)
instance Functor Grevlex
instance Ord v => Mon (Grevlex v)
instance (Ord v, Show v) => Monomial (Grevlex v)
instance MonomialConstructor Grevlex
instance (Eq a, Eq b) => Eq (Elim2 a b)
instance Functor (Elim2 a)
instance (Eq k, Fractional k, Monomial m, Ord m, Algebra k m) => Fractional (Vect k m)
instance (Eq k, Num k, Ord a, Mon a, Ord b, Mon b) => Algebra k (Elim2 a b)
instance (Monomial a, Monomial b) => Monomial (Elim2 a b)
instance (Mon a, Mon b) => Mon (Elim2 a b)
instance (Show a, Show b) => Show (Elim2 a b)
instance (Ord a, Ord b) => Ord (Elim2 a b)
instance (Eq k, Num k, Ord v, Show v) => Algebra k (Grevlex v)
instance Ord v => Ord (Grevlex v)
instance Show v => Show (Grevlex v)
instance (Eq k, Num k, Ord v, Show v) => Algebra k (Glex v)
instance Ord v => Ord (Glex v)
instance Show v => Show (Glex v)
instance (Eq k, Num k, Ord v, Show v) => Algebra k (Lex v)
instance Ord v => Ord (Lex v)
instance Show v => Show (Lex v)
instance MonomialConstructor MonImpl
instance (Ord v, Show v) => Monomial (MonImpl v)
instance Ord v => Mon (MonImpl v)
instance Show v => Show (MonImpl v)
-- | A module providing an efficient implementation of the Buchberger
-- algorithm for calculating the (reduced) Groebner basis for an ideal,
-- together with some straightforward applications.
module Math.CommutativeAlgebra.GroebnerBasis
sPoly :: (Monomial b, Algebra k b, Ord b, Fractional k, Eq k) => Vect k b -> Vect k b -> Vect k b
isGB :: (Monomial m, Algebra k m, Ord m, Fractional k, Eq k) => [Vect k m] -> Bool
gb1 :: (Monomial m, Algebra k m, Ord m, Fractional k, Eq k) => [Vect k m] -> [Vect k m]
pairWith :: (a1 -> a1 -> a) -> [a1] -> [a]
reduce :: (Monomial m, Algebra k m, Ord m, Ord k, Fractional k) => [Vect k m] -> [Vect k m]
gb2 :: (Monomial m, Algebra k m, Ord m, Ord k, Fractional k) => [Vect k m] -> [Vect k m]
(!) :: [a] -> Int -> a
gb2a :: (Monomial m, Algebra k m, Ord m, Ord k, Fractional k) => [Vect k m] -> [Vect k m]
gb3 :: (Monomial m, Algebra k m, Ord m, Ord k, Fractional k) => [Vect k m] -> [Vect k m]
gb4 :: (Monomial m, Algebra k m, Ord m, Ord k, Fractional k) => [Vect k m] -> [Vect k m]
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
-- | Given a list of polynomials over a field, return a Groebner basis for
-- the ideal generated by the polynomials.
gb :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m]
sugar :: (Monomial m2, Monomial m1, Monomial m) => Vect b m1 -> Vect b1 m2 -> m -> Int
cmpNormal :: (Ord t5, Ord t4) => ((t, t4), (t1, t5)) -> ((t2, t4), (t3, t5)) -> Ordering
cmpSug :: (Ord t4, Ord t3, Ord t2, Num t2) => ((t2, t3), (t, t4)) -> ((t2, t3), (t1, t4)) -> Ordering
memberGB :: (Monomial m, Algebra k m, Ord m, Fractional k, Eq k) => Vect k m -> [Vect k m] -> Bool
-- | memberI f gs returns whether f is in the ideal generated by
-- gs
memberI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => Vect k m -> [Vect k m] -> Bool
-- | Given ideals I and J, their sum is defined as I+J = {f+g | f <- I,
-- g <- J}.
--
-- If fs and gs are generators for I and J, then sumI fs gs
-- returns generators for I+J.
--
-- The geometric interpretation is that the variety of the sum is the
-- intersection of the varieties, ie V(I+J) = V(I) intersect V(J)
sumI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m]
-- | Given ideals I and J, their product I.J is the ideal generated by all
-- products {f.g | f <- I, g <- J}.
--
-- If fs and gs are generators for I and J, then productI fs gs
-- returns generators for I.J.
--
-- The geometric interpretation is that the variety of the product is the
-- union of the varieties, ie V(I.J) = V(I) union V(J)
productI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m]
-- | The intersection of ideals I and J is the set of all polynomials which
-- belong to both I and J.
--
-- If fs and gs are generators for I and J, then intersectI fs
-- gs returns generators for the intersection of I and J
--
-- The geometric interpretation is that the variety of the intersection
-- is the union of the varieties, ie V(I intersect J) = V(I) union V(J).
--
-- The reason for prefering the intersection over the product is that the
-- intersection of radical ideals is radical, whereas the product need
-- not be.
intersectI :: (Fractional k, Ord k, Monomial m, Ord m) => [Vect k m] -> [Vect k m] -> [Vect k m]
toElimFst :: (Mon b, Functor f) => f a -> f (Elim2 a b)
toElimSnd :: (Mon a, Functor f) => f b -> f (Elim2 a b)
isElimFst :: (Mon b, Eq b) => Vect b1 (Elim2 b t) -> Bool
fromElimSnd :: Functor f => f (Elim2 t b) -> f b
eliminateFst :: (Monomial t, Monomial b, Ord b1, Ord t, Ord b, Fractional b1) => [Vect b1 (Elim2 t b)] -> [Vect b1 b]
-- | Given ideals I and J, their quotient is defined as I:J = {f | f <-
-- R, f.g is in I for all g in J}.
--
-- If fs and gs are generators for I and J, then quotientI fs gs
-- returns generators for I:J.
--
-- The ideal quotient is the algebraic analogue of the Zariski closure of
-- a difference of varieties. V(I:J) contains the Zariski closure of
-- V(I)-V(J), with equality if k is algebraically closed and I is a
-- radical ideal.
quotientI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m]
quotientP :: (Monomial b, Algebra k b, Ord b, Ord k, Fractional k) => [Vect k b] -> Vect k b -> [Vect k b]
-- | eliminate vs gs returns the elimination ideal obtained from
-- the ideal generated by gs by eliminating the variables vs.
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)]
mbasis :: (Ord t, Num t) => [t] -> [t]
-- | Given variables vs, and a Groebner basis gs, mbasisQA vs gs
-- returns a monomial basis for the quotient algebra k[vs]/<gs>.
-- For example, mbasisQA [x,y] [x^2+y^2-1] returns a monomial
-- basis for k[x,y]/<x^2+y^2-1>. In general, the monomial basis is
-- likely to be infinite.
mbasisQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m]
-- | Given an ideal I, the leading term ideal lt(I) consists of the leading
-- terms of all elements of I. If I is generated by gs, then ltIdeal
-- gs returns generators for lt(I).
ltIdeal :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m]
numMonomials :: Integral a => a -> a -> Integer
-- | Given variables vs, and a homogeneous ideal gs, hilbertFunQA vs
-- gs returns the Hilbert function for the quotient algebra
-- k[vs]/<gs>. Given an integer i, the Hilbert function returns the
-- number of degree i monomials in a basis for k[vs]/<gs>. For a
-- homogeneous ideal, this number is independent of the monomial ordering
-- used (even though the elements of the monomial basis themselves are
-- dependent on the ordering).
--
-- If the ideal I is not homogeneous, then R/I is not graded, and the
-- Hilbert function is not well-defined. Specifically, the number of
-- degree i monomials in a basis is likely to depend on which monomial
-- ordering you use.
hilbertFunQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> Int -> Integer
hilbertSeriesQA1 :: (Monomial m, Algebra k m, Ord m, Ord k, Fractional k) => [Vect k m] -> [Vect k m] -> [Int]
-- | Given variables vs, and a homogeneous ideal gs, hilbertSeriesQA vs
-- gs returns the Hilbert series for the quotient algebra
-- k[vs]/<gs>. The Hilbert series should be interpreted as a formal
-- power series where the coefficient of t^i is the Hilbert function
-- evaluated at i. That is, the i'th element in the series is the number
-- of degree i monomials in a basis for k[vs]/<gs>.
hilbertSeriesQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Integer]
-- | In the case where every variable v occurs in some generator g of the
-- homogeneous ideal (the usual case), then the vs can be inferred from
-- the gs. hilbertSeriesQA' gs returns the Hilbert series for
-- the quotient algebra k[vs]/<gs>.
hilbertSeriesQA' :: (Fractional k, Ord k, MonomialConstructor m, Ord (m v), Monomial (m v), Algebra k (m v)) => [Vect k (m v)] -> [Integer]
-- | For i >> 0, the Hilbert function becomes a polynomial in i,
-- called the Hilbert polynomial.
hilbertPolyQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> GlexPoly Q String
hilbertPolyQA' :: (Fractional k, Ord k, MonomialConstructor m, Ord (m v), Monomial (m v), Algebra k (m v)) => [Vect k (m v)] -> GlexPoly Q String
dim :: (Monomial m, Algebra k m, Ord m, Ord k, Fractional k) => [Vect k m] -> [Vect k m] -> Int
dim' :: (Monomial (m v), MonomialConstructor m, Algebra k (m v), Ord (m v), Ord k, Fractional k) => [Vect k (m v)] -> Int
-- | A module defining the algebra of quaternions over an arbitrary field.
--
-- The quaternions are the algebra defined by the basis {1,i,j,k}, where
-- i^2 = j^2 = k^2 = ijk = -1
module Math.Algebras.Quaternions
data HBasis
One :: HBasis
I :: HBasis
J :: HBasis
K :: HBasis
type Quaternion k = Vect k HBasis
-- | The quaternions have {1,i,j,k} as basis, where i^2 = j^2 = k^2 = ijk =
-- -1.
i :: Num k => Quaternion k
-- | The quaternions have {1,i,j,k} as basis, where i^2 = j^2 = k^2 = ijk =
-- -1.
k :: Num k => Quaternion k
-- | The quaternions have {1,i,j,k} as basis, where i^2 = j^2 = k^2 = ijk =
-- -1.
j :: Num k => Quaternion k
class Algebra k a => HasConjugation k a
conj :: HasConjugation k a => Vect k a -> Vect k a
sqnorm :: HasConjugation k a => Vect k a -> k
-- | If an algebra has a conjugation operation, then it has multiplicative
-- inverses, via 1/x = conj x / sqnorm x
-- | The scalar part of the quaternion w+xi+yj+zk is w. Also called the
-- real part.
scalarPart :: Num k => Quaternion k -> k
-- | The vector part of the quaternion w+xi+yj+zk is xi+yj+zk. Also called
-- the pure part.
vectorPart :: (Eq k, Num k) => Quaternion k -> Quaternion k
(<.>) :: (Num k, Eq k) => Vect k HBasis -> Quaternion k -> k
(^-) :: (Num a, Fractional a1, Eq a) => a1 -> a -> a1
refl :: (HasConjugation k a, Show a, Ord a, Num k, Eq k) => Vect k a -> Vect k a -> Vect k a
asMatrix :: (Num t, Eq t) => (Vect t HBasis -> Quaternion t) -> [Vect t HBasis] -> [[t]]
reprSO3' :: Fractional a => a -> a -> a
-- | Given a non-zero quaternion q in H, the map x -> q^-1 * x * q
-- defines an action on the 3-dimensional vector space of pure
-- quaternions X (ie linear combinations of i,j,k). It turns out that
-- this action is a rotation of X, and this is a surjective group
-- homomorphism from H* onto SO3. If we restrict q to the group of unit
-- quaternions (those of norm 1), then this homomorphism is 2-to-1 (since
-- q and -q give the same rotation). 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 :: (Eq k, Fractional k) => Quaternion k -> [[k]]
reprSO4' :: Fractional a => (a, a) -> a -> a
-- | Given a pair of unit quaternions (l,r), the map x -> l^-1 * x * r
-- defines an action on the 4-dimensional space of quaternions. It turns
-- out that this action is a rotation, and this is a surjective group
-- homomorphism onto SO4. The homomorphism is 2-to-1 (since (l,r) and
-- (-l,-r) give the same map). This shows that the multiplicative group
-- of pairs of unit quaternions (with pointwise multiplication) is
-- isomorphic to Spin4, the double cover of SO4.
--
-- reprSO4 (l,r) returns the 4*4 matrix representing this map.
reprSO4 :: (Eq k, Fractional k) => (Quaternion k, Quaternion k) -> [[k]]
reprSO4d :: (Fractional k, Eq k) => Vect k (DSum HBasis HBasis) -> [[k]]
one' :: Num k => Vect k (Dual HBasis)
k' :: Num k => Vect k (Dual HBasis)
j' :: Num k => Vect k (Dual HBasis)
i' :: Num k => Vect k (Dual HBasis)
instance Eq HBasis
instance Ord HBasis
instance (Eq k, Num k) => Coalgebra k (Dual HBasis)
instance (Eq k, Num k) => HasConjugation k HBasis
instance (Eq k, Fractional k, Ord a, Show a, HasConjugation k a) => Fractional (Vect k a)
instance (Eq k, Num k) => Algebra k HBasis
instance Show HBasis
-- | A module providing elementary operations involving scalars, vectors,
-- and matrices over a ring or field. Vectors are represented as [a],
-- matrices as [[a]]. (No distinction is made between row and column
-- vectors.) It is the caller's responsibility to ensure that the lists
-- have the correct number of elements.
--
-- The mnemonic for many of the arithmetic operations is that the number
-- of angle brackets on each side indicates the dimension of the argument
-- on that side. For example, v <*>> m is multiplication of a
-- vector on the left by a matrix on the right.
module Math.Algebra.LinearAlgebra
-- | u <+> v returns the sum u+v of vectors
(<+>) :: Num a => [a] -> [a] -> [a]
-- | u <-> v returns the difference u-v of vectors
(<->) :: Num a => [a] -> [a] -> [a]
-- | k *> v returns the product k*v of the scalar k and the vector v
(*>) :: Num a => a -> [a] -> [a]
-- | u <.> v returns the dot product of vectors (also called inner or
-- scalar product)
(<.>) :: Num a => [a] -> [a] -> a
-- | u <*> v returns the tensor product of vectors (also called outer
-- or matrix product)
(<*>) :: Num a => [a] -> [a] -> [[a]]
-- | a <<+>> b returns the sum a+b of matrices
(<<+>>) :: Num a => [[a]] -> [[a]] -> [[a]]
-- | a <<->> b returns the difference a-b of matrices
(<<->>) :: Num a => [[a]] -> [[a]] -> [[a]]
-- | a <<*>> b returns the product a*b of matrices
(<<*>>) :: Num a => [[a]] -> [[a]] -> [[a]]
-- | k *>> m returns the product k*m of the scalar k and the matrix m
(*>>) :: Num a => a -> [[a]] -> [[a]]
-- | m <<*> v is multiplication of a vector by a matrix on the
-- left
(<<*>) :: Num a => [[a]] -> [a] -> [a]
-- | v <*>> m is multiplication of a vector by a matrix on the
-- right
(<*>>) :: Num a => [a] -> [[a]] -> [a]
fMatrix :: (Num t1, Enum t1) => t1 -> (t1 -> t1 -> t) -> [[t]]
fMatrix' :: (Num t1, Enum t1) => t1 -> (t1 -> t1 -> t) -> [[t]]
idMx :: Num a => Int -> [[a]]
-- | iMx n is the n*n identity matrix
iMx :: Num t => Int -> [[t]]
-- | jMx n is the n*n matrix of all 1s
jMx :: Num t => Int -> [[t]]
-- | zMx n is the n*n matrix of all 0s
zMx :: Num t => Int -> [[t]]
-- | The inverse of a matrix (over a field), if it exists
inverse :: (Eq a, Fractional a) => [[a]] -> Maybe [[a]]
inverse1 :: (Fractional a, Eq a) => [[a]] -> [[a]]
inverse2 :: (Num t, Eq t) => [[t]] -> [[t]]
(!) :: [a] -> Int -> a
rowEchelonForm :: (Fractional a, Eq a) => [[a]] -> [[a]]
reducedRowEchelonForm :: (Eq a, Fractional a) => [[a]] -> [[a]]
solveLinearSystem :: (Fractional a, Eq a) => [[a]] -> [a] -> Maybe [a]
isZero :: (Num a, Eq a) => [a] -> Bool
inSpanRE :: (Num a, Eq a) => [[a]] -> [a] -> Bool
rank :: (Fractional a, Eq a) => [[a]] -> Int
kernel :: (Ord a, Fractional a) => [[a]] -> [[a]]
kernelRRE :: (Ord a, Num a) => [[a]] -> [[a]]
-- | The determinant of a matrix (over a field)
det :: (Eq a, Fractional a) => [[a]] -> a
-- | A module for doing arithmetic in permutation groups.
--
-- Group elements are represented as permutations of underlying sets, and
-- are entered and displayed using a Haskell-friendly version of cycle
-- notation. For example, the permutation (1 2 3)(4 5) would be entered
-- as p [[1,2,3],[4,5]], and displayed as [[1,2,3],[4,5]].
-- Permutations can be defined over arbitrary underlying sets (types),
-- not just the integers.
--
-- If g and h are group elements, then the expressions
-- g*h and g^-1 calculate product and inverse
-- respectively.
module Math.Algebra.Group.PermutationGroup
rotateL :: [a] -> [a]
-- | A type for permutations, considered as functions or actions which can
-- be performed on an underlying set.
newtype Permutation a
P :: (Map a a) -> Permutation a
fmapP :: Ord a => (t -> a) -> Permutation t -> Permutation a
-- | Construct a permutation from a list of cycles. For example, p
-- [[1,2,3],[4,5]] returns the permutation that sends 1 to 2, 2 to
-- 3, 3 to 1, 4 to 5, 5 to 4.
p :: Ord a => [[a]] -> Permutation a
fromPairs :: Ord a => [(a, a)] -> Permutation a
fromPairs' :: Ord a => [(a, a)] -> Permutation a
toPairs :: Permutation a -> [(a, a)]
fromList :: Ord a => [a] -> Permutation a
supp :: Permutation a -> [a]
-- | x .^ g returns the image of a vertex or point x under the action of
-- the permutation g. For example, 1 .^ p [[1,2,3]] returns 2.
-- The dot is meant to be a mnemonic for point or vertex.
(.^) :: Ord a => a -> Permutation a -> a
-- | b -^ g returns the image of an edge or block b under the action of the
-- permutation g. For example, [1,2] -^ p [[1,4],[2,3]] returns
-- [3,4]. The dash is meant to be a mnemonic for edge or line or block.
(-^) :: Ord a => [a] -> Permutation a -> [a]
fromCycles :: Ord a => [[a]] -> Permutation a
toCycles :: Ord a => Permutation a -> [[a]]
cycleOf :: Ord a => Permutation a -> a -> [a]
parity :: Ord a => Permutation a -> Int
sign :: (Ord a1, Num a) => Permutation a1 -> a
orderElt :: Ord a => Permutation a -> Int
-- | The Num instance is what enables us to write g*h for the
-- product of group elements and 1 for the group identity.
-- Unfortunately we can't of course give sensible definitions for the
-- other functions declared in the Num typeclass.
-- | The HasInverses instance is what enables us to write g^-1 for
-- the inverse of a group element.
-- | g ~^ h returns the conjugate of g by h, that is, h^-1*g*h. The tilde
-- is meant to a mnemonic, because conjugacy is an equivalence relation.
(~^) :: Ord a => Permutation a -> Permutation a -> Permutation a
comm :: (HasInverses a, Num a) => a -> a -> a
closureS :: Ord a => [a] -> [a -> a] -> Set a
closure :: Ord a => [a] -> [a -> a] -> [a]
orbit :: Ord a => (a -> t -> a) -> a -> [t] -> [a]
-- | x .^^ gs returns the orbit of the point or vertex x under the action
-- of the gs
(.^^) :: Ord a => a -> [Permutation a] -> [a]
orbitP :: Ord a => [Permutation a] -> a -> [a]
orbitV :: Ord a => [Permutation a] -> a -> [a]
-- | b -^^ gs returns the orbit of the block or edge b under the action of
-- the gs
(-^^) :: Ord a => [a] -> [Permutation a] -> [[a]]
orbitB :: Ord a => [Permutation a] -> [a] -> [[a]]
orbitE :: Ord a => [Permutation a] -> [a] -> [[a]]
action :: Ord a => [a] -> (a -> a) -> Permutation a
orbits :: Ord a => [Permutation a] -> [[a]]
-- | _C n returns generators for Cn, the cyclic group of order n
_C :: Integral a => a -> [Permutation a]
_D :: Integral a => a -> [Permutation a]
_D2 :: Integral a => a -> [Permutation a]
-- | _S n returns generators for Sn, the symmetric group on [1..n]
_S :: Integral a => a -> [Permutation a]
-- | _A n returns generators for An, the alternating group on [1..n]
_A :: Integral a => a -> [Permutation a]
-- | Given generators for groups H and K, acting on sets A and B
-- respectively, return generators for the direct product H*K, acting on
-- the disjoint union A+B (= Either A B)
dp :: (Ord a, Ord b) => [Permutation a] -> [Permutation b] -> [Permutation (Either a b)]
wr :: (Ord t1, Ord t) => [Permutation t] -> [Permutation t1] -> [Permutation (t, t1)]
toSn :: (Ord a, Ord k, Num a, Enum a) => [Permutation k] -> [Permutation a]
fromDigits :: (Ord a, Num a) => Permutation [a] -> Permutation a
fromDigits' :: Num a => [a] -> a
fromBinary :: (Ord a, Num a) => Permutation [a] -> Permutation a
fromBinary' :: Num a => [a] -> a
-- | Given generators for a group, return a (sorted) list of all elements
-- of the group. Implemented using a naive closure algorithm, so only
-- suitable for small groups (|G| < 10000)
elts :: (Num a, Ord a) => [a] -> [a]
eltsS :: (Ord a, Num a) => [a] -> Set a
-- | Given generators for a group, return the order of the group (the
-- number of elements). Implemented using a naive closure algorithm, so
-- only suitable for small groups (|G| < 10000)
order :: (Num a, Ord a) => [a] -> Int
isMember :: (Ord a, Num a) => [a] -> a -> Bool
minsupp :: Permutation c -> c
orderTGS :: (Ord a, Num a1) => [Permutation a] -> a1
eltsTGS :: Ord a => [Permutation a] -> [Permutation a]
tgsFromSgs :: Ord a => [Permutation a] -> [Permutation a]
-- | Given a strong generating set, return the order of the group it
-- generates. Note that the SGS is assumed to be relative to the natural
-- order of the points on which the group acts.
orderSGS :: Ord a => [Permutation a] -> Integer
-- | Given a base and strong generating set, return the order of the group
-- it generates.
orderBSGS :: Ord a => ([a], [Permutation a]) -> Integer
gens :: (Ord a, Num a) => [a] -> [a]
(~^^) :: Ord a => Permutation a -> [Permutation a] -> [Permutation a]
conjClass :: Ord a => [Permutation a] -> Permutation a -> [Permutation a]
-- | conjClassReps gs returns conjugacy class representatives and sizes for
-- the group generated by gs. This implementation is only suitable for
-- use with small groups (|G| < 10000).
conjClassReps :: (Ord a, Show a) => [Permutation a] -> [(Permutation a, Int)]
reduceGens :: (Ord a, Num a) => [a] -> [a]
isSubgp :: (Ord a, Num a) => [a] -> [a] -> Bool
-- | Return the subgroups of a group. Only suitable for use on small groups
-- (eg < 100 elts)
subgps :: (Ord a, Show a) => [Permutation a] -> [[Permutation a]]
isMinimal :: Ord a => Permutation a -> Bool
centralizer :: (Ord t, Num t) => [t] -> [t] -> [t]
centre :: (Ord t, Num t) => [t] -> [t]
normalizer :: Ord a => [Permutation a] -> [Permutation a] -> [Permutation a]
stabilizer :: Ord a => [Permutation a] -> a -> [Permutation a]
ptStab :: Ord a => [Permutation a] -> [a] -> [Permutation a]
setStab :: Ord a => [Permutation a] -> [a] -> [Permutation a]
normalClosure :: Ord a => [Permutation a] -> [Permutation a] -> [Permutation a]
commutatorGp :: Ord a => [Permutation a] -> [Permutation a] -> [Permutation a]
derivedSubgp :: Ord a => [Permutation a] -> [Permutation a]
(-*-) :: (Ord b, Num b) => [b] -> [b] -> [b]
(-*) :: (Ord a, Num a) => [a] -> a -> [a]
(*-) :: (Ord a, Num a) => a -> [a] -> [a]
-- | isNormal gs ks returns True if <ks> is normal in <gs>.
-- Note, it is caller's responsibility to ensure that <ks> is a
-- subgroup of <gs> (ie that each k is in <gs>).
isNormal :: (Ord a, Show a) => [Permutation a] -> [Permutation a] -> Bool
-- | Return the normal subgroups of a group. Only suitable for use on small
-- groups (eg < 100 elts)
normalSubgps :: (Ord a, Show a) => [Permutation a] -> [[Permutation a]]
isSimple :: (Show a, Ord a) => [Permutation a] -> Bool
cosets :: (Ord t, Num t) => [t] -> [t] -> [[t]]
-- | quotientGp gs ks returns <gs> / <ks>
quotientGp :: (Ord a, Show a) => [Permutation a] -> [Permutation a] -> [Permutation Int]
-- | Synonym for quotientGp
(//) :: (Ord a, Show a) => [Permutation a] -> [Permutation a] -> [Permutation Int]
(~~^) :: Ord a => [Permutation a] -> Permutation a -> [Permutation a]
conjugateSubgps :: Ord a => [Permutation a] -> [Permutation a] -> [[Permutation a]]
subgpAction :: (Ord a1, Ord a, Num a1, Enum a1) => [Permutation a] -> [Permutation a] -> [Permutation a1]
rrpr :: (Ord a, Num a) => [a] -> a -> Permutation a
rrpr' :: (Ord a, Num a) => [a] -> a -> Permutation a
permutationMatrix :: (Ord a, Num t) => [a] -> Permutation a -> [[t]]
instance Eq a => Eq (Permutation a)
instance Ord a => Ord (Permutation a)
instance Ord a => HasInverses (Permutation a)
instance Ord a => Num (Permutation a)
instance (Ord a, Show a) => Show (Permutation a)
module Math.Algebra.Group.SchreierSims
cosetRepsGx :: Ord k => [Permutation k] -> k -> Map k (Permutation k)
schreierGeneratorsGx :: Ord k => (k, Map k (Permutation k)) -> [Permutation k] -> [Permutation k]
sift :: Ord k => [(k, Map k (Permutation k))] -> Permutation k -> Maybe (Permutation k)
findBase :: Ord a => [Permutation a] -> a
-- | Given generators for a permutation group, return a strong generating
-- set. The result is calculated using Schreier-Sims algorithm, and is
-- relative to the base implied by the Ord instance
sgs :: (Ord a, Show a) => [Permutation a] -> [Permutation a]
bsgs :: Ord k => [Permutation k] -> [(k, Map k (Permutation k))]
bsgs' :: Ord k => [k] -> [Permutation k] -> [(k, Map k (Permutation k))]
newLevel :: Ord a => [a] -> [Permutation a] -> ([a], ((a, Map a (Permutation a)), [Permutation a]))
newLevel' :: Ord t => t -> [Permutation t] -> ((t, Map t (Permutation t)), [Permutation t])
ss :: Ord k => [k] -> [Permutation k] -> [((k, Map k (Permutation k)), [Permutation k])]
ss' :: Ord k => [k] -> [((k, Map k (Permutation k)), [Permutation k])] -> [((k, Map k (Permutation k)), [Permutation k])] -> [((k, Map k (Permutation k)), [Permutation k])]
isMemberBSGS :: Ord k => [(k, Map k (Permutation k))] -> Permutation k -> Bool
eltsBSGS :: Num b => [(a, Map k b)] -> [b]
cartProd :: [[a]] -> [[a]]
orderBSGS :: [(a1, Map k a)] -> Integer
-- | Given generators for a group, determine whether a permutation is a
-- member of the group, using Schreier-Sims algorithm
isMember :: (Ord t, Show t) => [Permutation t] -> Permutation t -> Bool
-- | Given generators for a group, return a (sorted) list of all elements
-- of the group, using Schreier-Sims algorithm
elts :: (Ord t, Show t) => [Permutation t] -> [Permutation t]
-- | Given generators for a group, return the order of the group (the
-- number of elements), using Schreier-Sims algorithm
order :: (Ord t, Show t) => [Permutation t] -> Integer
isSubgp :: Ord k => [Permutation k] -> [Permutation k] -> Bool
isNormal :: Ord k => [Permutation k] -> [Permutation k] -> Bool
index :: (Show t1, Show t, Ord t1, Ord t) => [Permutation t] -> [Permutation t1] -> Integer
reduceGens :: Ord k => [Permutation k] -> [Permutation k]
reduceGensBSGS :: Ord k => [Permutation k] -> ([Permutation k], [(k, Map k (Permutation k))])
normalClosure :: Ord k => [Permutation k] -> [Permutation k] -> [Permutation k]
commutatorGp :: Ord k => [Permutation k] -> [Permutation k] -> [Permutation k]
derivedSubgp :: Ord k => [Permutation k] -> [Permutation k]
module Math.Algebra.Group.RandomSchreierSims
testProdRepl :: IO ()
initProdRepl :: (Ord a, Show a) => [Permutation a] -> IO (Int, IOArray Int (Permutation a))
nextProdRepl :: (Ord a, Show a) => (Int, IOArray Int (Permutation a)) -> IO (Maybe (Permutation a))
updateArray :: (HasInverses a, MArray a1 a m, Ix i, Num i, Num a, Integral t) => a1 i a -> i -> i -> t -> m (Maybe a)
-- | Given generators for a permutation group, return a strong generating
-- set. The result is calculated using random Schreier-Sims algorithm, so
-- has a small (<10^-6) chance of being incomplete. The sgs is
-- relative to the base implied by the Ord instance.
sgs :: (Ord a, Show a) => [Permutation a] -> [Permutation a]
rss :: (Show k, Ord k) => [Permutation k] -> [((k, Map k (Permutation k)), [Permutation k])]
rss' :: (Show k, Ord k, Num a, Eq a) => (Int, IOArray Int (Permutation k)) -> [((k, Map k (Permutation k)), [Permutation k])] -> a -> IO [((k, Map k (Permutation k)), [Permutation k])]
initLevels :: (Ord k, Num a) => [Permutation k] -> [((k, Map k a), [t])]
updateLevels :: Ord k => [((k, Map k (Permutation k)), [Permutation k])] -> Maybe (Permutation k) -> (Bool, [((k, Map k (Permutation k)), [Permutation k])])
updateLevels' :: Ord k => [((k, Map k (Permutation k)), [Permutation k])] -> [((k, Map k (Permutation k)), [Permutation k])] -> Permutation k -> k -> [((k, Map k (Permutation k)), [Permutation k])]
baseTransversalsSGS :: Ord k => [Permutation k] -> [(k, Map k (Permutation k))]
-- | Given a strong generating set gs, isMemberSGS gs is a membership test
-- for the group
isMemberSGS :: (Ord a, Show a) => [Permutation a] -> Permutation a -> Bool
module Math.Algebra.Group.Subquotients
isLeft :: Either t t1 -> Bool
isRight :: Either t t1 -> Bool
unRight :: Ord a => Permutation (Either t a) -> Permutation a
restrictLeft :: Ord a => Permutation (Either a t) -> Permutation a
ptStab :: (Show a, Ord a) => [Permutation a] -> [a] -> [Permutation a]
isTransitive :: Ord t => [Permutation t] -> Bool
-- | Given a group gs and a transitive constituent ys, return the kernel
-- and image of the transitive constituent homomorphism. That is, suppose
-- that gs acts on a set xs, and ys is a subset of xs on which gs acts
-- transitively. Then the transitive constituent homomorphism is the
-- restriction of the action of gs to an action on the ys.
transitiveConstituentHomomorphism :: (Ord a, Show a) => [Permutation a] -> [a] -> ([Permutation a], [Permutation a])
transitiveConstituentHomomorphism' :: (Show t, Ord t) => [Permutation t] -> [t] -> ([Permutation t], [Permutation t])
minimalBlock :: Ord a => [Permutation a] -> [a] -> [[a]]
-- | Given a transitive group gs, find all non-trivial block systems. That
-- is, if gs act on xs, find all the ways that the xs can be divided into
-- blocks, such that the gs also have a permutation action on the blocks
blockSystems :: Ord t => [Permutation t] -> [[[t]]]
-- | A more efficient version of blockSystems, if we have an sgs
blockSystemsSGS :: Ord a => [Permutation a] -> [[[a]]]
-- | A permutation group is primitive if it has no non-trivial block
-- systems
isPrimitive :: Ord t => [Permutation t] -> Bool
isPrimitiveSGS :: Ord a => [Permutation a] -> Bool
-- | Given a transitive group gs, and a block system for gs, return the
-- kernel and image of the block homomorphism (the homomorphism onto the
-- action of gs on the blocks)
blockHomomorphism :: (Ord t, Show t) => [Permutation t] -> [[t]] -> ([Permutation t], [Permutation [t]])
blockHomomorphism' :: (Show t, Ord t) => [Permutation t] -> [[t]] -> ([Permutation t], [Permutation [t]])
normalClosure :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [Permutation a]
intersectionNormalClosure :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [Permutation a]
centralizerSymTrans :: (Show a, Ord a) => [Permutation a] -> [Permutation a]
-- | A module defining a polymorphic data type for (simple, undirected)
-- graphs, together with constructions of some common families of graphs,
-- new from old constructions, and calculation of simple properties of
-- graphs.
module Math.Combinatorics.Graph
set :: Ord b => [b] -> [b]
powerset :: [t] -> [[t]]
-- | Datatype for graphs, represented as a list of vertices and a list of
-- edges. For most purposes, graphs are required to be in normal form. A
-- graph G vs es is in normal form if (i) vs is in ascending order
-- without duplicates, (ii) es is in ascending order without duplicates,
-- (iii) each e in es is a 2-element list [x,y], x<y
data Graph a
G :: [a] -> [[a]] -> Graph a
-- | Convert a graph to normal form. The input is assumed to be a valid
-- graph apart from order
nf :: Ord a => Graph a -> Graph a
isSetSystem :: Ord a => [a] -> [[a]] -> Bool
isGraph :: Ord a => [a] -> [[a]] -> Bool
-- | Safe constructor for graph from lists of vertices and edges. graph
-- (vs,es) checks that vs and es are valid before returning the graph.
graph :: Ord t => ([t], [[t]]) -> Graph t
toGraph :: Ord a => ([a], [[a]]) -> Graph a
vertices :: Graph t -> [t]
edges :: Graph t -> [[t]]
incidenceMatrix :: (Num t, Eq a) => Graph a -> [[t]]
fromIncidenceMatrix :: (Ord t, Num t, Num a, Eq a, Enum t) => [[a]] -> Graph t
adjacencyMatrix :: (Ord a, Num t) => Graph a -> [[t]]
fromAdjacencyMatrix :: (Num b, Eq b) => [[b]] -> Graph Int
-- | The null graph on n vertices is the graph with no edges
nullGraph :: Integral t => t -> Graph t
-- | The null graph, with no vertices or edges
nullGraph' :: Graph Int
-- | c n is the cyclic graph on n vertices
c :: Integral t => t -> Graph t
-- | k n is the complete graph on n vertices
k :: Integral t => t -> Graph t
-- | kb m n is the complete bipartite graph on m and n vertices
kb :: Integral t => t -> t -> Graph t
-- | kb' m n is the complete bipartite graph on m left and n right vertices
kb' :: Integral t => t -> t -> Graph (Either t t)
-- | q k is the graph of the k-cube
q :: Integral t => Int -> Graph t
q' :: Integral t => Int -> Graph [t]
tetrahedron :: Graph Integer
cube :: Graph Integer
octahedron :: Graph Integer
dodecahedron :: Graph Integer
icosahedron :: Graph Integer
prism :: Int -> Graph (Int, Int)
to1n :: (Ord t, Ord a, Num t, Enum t) => Graph a -> Graph t
-- | Given a graph with vertices which are lists of small integers, eg
-- [1,2,3], return a graph with vertices which are the numbers obtained
-- by interpreting these as digits, eg 123. The caller is responsible for
-- ensuring that this makes sense (eg that the small integers are all
-- < 10)
fromDigits :: Integral a => Graph [a] -> Graph a
-- | Given a graph with vertices which are lists of 0s and 1s, return a
-- graph with vertices which are the numbers obtained by interpreting
-- these as binary digits. For example, [1,1,0] -> 6.
fromBinary :: Integral a => Graph [a] -> Graph a
petersen :: Graph [Integer]
complement :: Ord t => Graph t -> Graph t
-- | The restriction of a graph to a subset of the vertices
restriction :: Eq a => Graph a -> [a] -> Graph a
inducedSubgraph :: Eq a => Graph a -> [a] -> Graph a
lineGraph :: (Ord a, Ord t, Num t, Enum t) => Graph a -> Graph t
lineGraph' :: Ord a => Graph a -> Graph [a]
cartProd :: (Ord t1, Ord t) => Graph t -> Graph t1 -> Graph (t, t1)
order :: Graph a -> Int
size :: Graph t -> Int
valency :: Eq a => Graph a -> a -> Int
valencies :: Eq a => Graph a -> [(Int, Int)]
valencyPartition :: Eq b => Graph b -> [[b]]
regularParam :: Eq a => Graph a -> Maybe Int
-- | A graph is regular if all vertices have the same valency (degree)
isRegular :: Eq t => Graph t -> Bool
-- | A 3-regular graph is called a cubic graph
isCubic :: Eq t => Graph t -> Bool
nbrs :: Eq a => Graph a -> a -> [a]
findPaths :: Eq a => Graph a -> a -> a -> [[a]]
-- | Within a graph G, the distance d(u,v) between vertices u, v is length
-- of the shortest path from u to v
distance :: Eq a => Graph a -> a -> a -> Int
-- | The diameter of a graph is maximum distance between two distinct
-- vertices
diameter :: Ord t => Graph t -> Int
findCycles :: Eq a => Graph a -> a -> [[a]]
-- | The girth of a graph is the size of the smallest cycle that it
-- contains. Note: If the graph contains no cycles, we return -1,
-- representing infinity.
girth :: Eq t => Graph t -> Int
distancePartition :: Ord a => Graph a -> a -> [[a]]
distancePartitionS :: Ord a => [a] -> Set [a] -> a -> [[a]]
component :: Ord a => Graph a -> a -> [a]
-- | Is the graph connected?
isConnected :: Ord t => Graph t -> Bool
components :: Ord a => Graph a -> [[a]]
j :: Int -> Int -> Int -> Graph [Int]
-- | kneser n k returns the kneser graph KG n,k - whose vertices are the
-- k-element subsets of [1..n], with edges between disjoint subsets
kneser :: Int -> Int -> Graph [Int]
johnson :: Int -> Int -> Graph [Int]
bipartiteKneser :: Int -> Int -> Graph (Either [Int] [Int])
desargues1 :: Graph (Either [Int] [Int])
gp :: Integral a => a -> a -> Graph (Either a a)
petersen2 :: Graph (Either Integer Integer)
prism' :: Integral a => a -> Graph (Either a a)
durer :: Graph (Either Integer Integer)
mobiusKantor :: Graph (Either Integer Integer)
dodecahedron2 :: Graph (Either Integer Integer)
desargues2 :: Graph (Either Integer Integer)
instance Eq a => Eq (Graph a)
instance Ord a => Ord (Graph a)
instance Show a => Show (Graph a)
instance Functor Graph
module Math.Algebra.Group.CayleyGraph
data Digraph a
DG :: [a] -> [(a, a)] -> Digraph a
cayleyDigraphP :: (Ord a, Num a) => [a] -> Digraph a
-- | The Cayley graph (undirected) on the generators (and their inverses),
-- for a group given as permutations
cayleyGraphP :: (Ord a, Show a) => [Permutation a] -> Graph (Permutation a)
cayleyDigraphS :: Ord a => ([a], [([a], [a])]) -> Digraph [a]
-- | The Cayley graph (undirected) on the generators (and their inverses),
-- for a group given as generators and relations
cayleyGraphS :: Ord a => ([a], [([a], [a])]) -> Graph [a]
fromTranspositions :: [SGen] -> Permutation Int
fromTrans :: [SGen] -> [Int]
bubblesort :: Ord a => [a] -> [a]
toTrans :: Ord t => [t] -> [SGen]
toTranspositions :: (Ord t, Num t, Enum t) => Permutation t -> [SGen]
inversions :: (Ord t, Num t, Enum t) => Permutation t -> [(t, t)]
instance Eq a => Eq (Digraph a)
instance Ord a => Ord (Digraph a)
instance Show a => Show (Digraph a)
module Math.Combinatorics.GraphAuts
-- | A graph is vertex-transitive if its automorphism group acts
-- transitively on the vertices. Thus, given any two distinct vertices,
-- there is an automorphism mapping one to the other.
isVertexTransitive :: Ord t => Graph t -> Bool
-- | A graph is edge-transitive if its automorphism group acts transitively
-- on the edges. Thus, given any two distinct edges, there is an
-- automorphism mapping one to the other.
isEdgeTransitive :: Ord t => Graph t -> Bool
-- | A graph is arc-transitive (or flag-transitive) if its automorphism
-- group acts transitively on arcs. (An arc is an ordered pair of
-- adjacent vertices.)
isArcTransitive :: Ord t => Graph t -> Bool
is2ArcTransitive :: Ord t => Graph t -> Bool
is3ArcTransitive :: Ord t => Graph t -> Bool
is4ArcTransitive :: Ord t => Graph t -> Bool
-- | A graph is n-arc-transitive if its automorphism group is transitive on
-- n-arcs. (An n-arc is an ordered sequence (v0,...,vn) of adjacent
-- vertices, with crossings allowed but not doubling back.)
isnArcTransitive :: Ord t => Int -> Graph t -> Bool
-- | A graph is distance transitive if given any two ordered pairs of
-- vertices (u,u') and (v,v') with d(u,u') == d(v,v'), there is an
-- automorphism of the graph that takes (u,u') to (v,v')
isDistanceTransitive :: Ord t => Graph t -> Bool
-- | Given a graph g, graphAuts g returns a strong generating set
-- for the automorphism group of g.
graphAuts :: Ord a => Graph a -> [Permutation a]
-- | Given the incidence graph of an incidence structure between points and
-- blocks (for example, a set system), incidenceAuts g returns a
-- strong generating set for the automorphism group of the incidence
-- structure. The generators are represented as permutations of the
-- points. The incidence graph should be represented with the points on
-- the left and the blocks on the right.
incidenceAuts :: (Ord p, Ord b) => Graph (Either p b) -> [Permutation p]
graphAuts7 :: Ord a => Graph a -> ([a], [Permutation a])
graphAuts8 :: Ord a => Graph a -> ([a], [Permutation a])
incidenceAuts2 :: (Ord b, Ord a) => Graph (Either a b) -> ([Either a b], [Permutation (Either a b)])
-- | Is the permutation an automorphism of the graph?
isGraphAut :: Ord t => Graph t -> Permutation t -> Bool
-- | Is the permutation an automorphism of the incidence structure
-- represented by the graph? (Note that an incidence graph colours points
-- as Left, blocks as Right, and a permutation that swaps points and
-- blocks, even if it is an automorphism of the graph, does not represent
-- an automorphism of the incidence structure. Instead, a point-block
-- crossover is called a duality.)
isIncidenceAut :: (Ord p, Ord b) => Graph (Either p b) -> Permutation (Either p b) -> Bool
graphIsos :: (Ord t1, Ord t) => Graph t -> Graph t1 -> [[(t, t1)]]
incidenceIsos :: (Ord t3, Ord t2, Ord t1, Ord t) => Graph (Either t2 t) -> Graph (Either t3 t1) -> [[(t2, t3)]]
-- | Are the two graphs isomorphic?
isGraphIso :: (Ord a, Ord b) => Graph a -> Graph b -> Bool
-- | Are the two incidence structures represented by these incidence graphs
-- isomorphic?
isIncidenceIso :: (Ord p1, Ord b1, Ord p2, Ord b2) => Graph (Either p1 b1) -> Graph (Either p2 b2) -> Bool
instance Eq a => Eq (SearchTree a)
instance Ord a => Ord (SearchTree a)
instance Show a => Show (SearchTree a)
instance Functor SearchTree
module Math.Projects.Rubik
f :: Permutation Integer
b :: Permutation Integer
l :: Permutation Integer
r :: Permutation Integer
u :: Permutation Integer
d :: Permutation Integer
rubikCube :: [Permutation Integer]
cornerFaces :: [Integer]
kerCornerFaces :: [Permutation Integer]
kerEdgeFaces :: [Permutation Integer]
cornerBlocks :: [[Integer]]
edgeBlocks :: [[Integer]]
kerCornerBlocks :: [Permutation Integer]
kerEdgeBlocks :: [Permutation Integer]
_U :: Permutation Integer
_u :: Permutation Integer
_d :: Permutation Integer
_D :: Permutation Integer
bf :: Permutation Integer
_R :: Permutation Integer
_r :: Permutation Integer
_l :: Permutation Integer
_L :: Permutation Integer
ud :: Permutation Integer
_B :: Permutation Integer
_b :: Permutation Integer
_f :: Permutation Integer
_F :: Permutation Integer
-- | A module for doing arithmetic in the group algebra.
--
-- Group elements are represented as permutations of the integers, and
-- are entered and displayed using a Haskell-friendly version of cycle
-- notation. For example, the permutation (1 2 3)(4 5) would be entered
-- as p [[1,2,3],[4,5]], and displayed as [[1,2,3],[4,5]].
--
-- Given a field K and group G, the group algebra KG is the free K-vector
-- space over the elements of G. Elements of the group algebra consist of
-- arbitrary K-linear combinations of elements of G. For example, p
-- [[1,2,3]] + 2 * p [[1,2],[3,4]]
module Math.Algebras.GroupAlgebra
type GroupAlgebra k = Vect k (Permutation Int)
-- | Construct a permutation, as an element of the group algebra, from a
-- list of cycles. For example, p [[1,2],[3,4,5]] constructs the
-- permutation (1 2)(3 4 5), which is displayed as [[1,2],[3,4,5]].
p :: [[Int]] -> GroupAlgebra Q
instance Eq a => Eq (X a)
instance Ord a => Ord (X a)
instance Show a => Show (X a)
instance HasInverses (GroupAlgebra Q)
instance (Eq k, Num k) => Module k (Permutation Int) [Int]
instance (Eq k, Num k) => Module k (Permutation Int) Int
instance (Eq k, Num k) => HopfAlgebra k (Permutation Int)
instance (Eq k, Num k) => Bialgebra k (Permutation Int)
instance (Eq k, Num k) => Coalgebra k (Permutation Int)
instance (Eq k, Num k) => Algebra k (Permutation Int)
-- | Constructions of the finite geometries AG(n,Fq) and PG(n,Fq), their
-- points, lines and flats, together with the incidence graphs between
-- points and lines.
module Math.Combinatorics.FiniteGeometry
-- | ptsAG n fq returns the points of the affine geometry AG(n,Fq), where
-- fq are the elements of Fq
ptsAG :: Int -> [a] -> [[a]]
-- | ptsPG n fq returns the points of the projective geometry PG(n,Fq),
-- where fq are the elements of Fq
ptsPG :: Num a => Int -> [a] -> [[a]]
pnf :: (Fractional a, Eq a) => [a] -> [a]
ispnf :: (Num t, Eq t) => [t] -> Bool
-- | Given a list of points in AG(n,Fq), return their closure, the smallest
-- flat containing them
closureAG :: (Num a, Ord a, FinSet a) => [[a]] -> [[a]]
lineAG :: (FinSet a, Ord a, Num a) => [[a]] -> [[a]]
-- | Given a set of points in PG(n,Fq), return their closure, the smallest
-- flat containing them
closurePG :: (Num a, Ord a, FinSet a) => [[a]] -> [[a]]
linePG :: (FinSet t, Ord t, Num t) => [[t]] -> [[t]]
qtorial :: (Integral b, Integral a) => b -> a -> a
qnomial :: (Integral b, Integral a) => b -> b -> a -> a
numFlatsPG :: (Integral b, Integral a) => b -> a -> b -> a
numFlatsAG :: (Integral b, Integral a) => b -> a -> b -> a
qtorials :: Integral a => a -> [a]
qnomials :: Num d => d -> [[d]]
data ZeroOneStar
Zero :: ZeroOneStar
One :: ZeroOneStar
Star :: ZeroOneStar
rrefs :: Int -> Int -> [[[ZeroOneStar]]]
-- | flatsPG n fq k returns the k-flats in PG(n,Fq), where fq are
-- the elements of Fq. The returned flats are represented as matrices in
-- reduced row echelon form, the rows of which are the points that
-- generate the flat. The full set of points in the flat can be recovered
-- by calling closurePG
flatsPG :: (Eq a, Num 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 :: (Eq a, Num a) => Int -> [a] -> Int -> [[[a]]]
-- | The lines (1-flats) in PG(n,fq)
linesPG :: (Eq a, Num a) => Int -> [a] -> [[[a]]]
-- | The lines (1-flats) in AG(n,fq)
linesAG :: (Eq a, Num a) => Int -> [a] -> [[[a]]]
linesAG1 :: (FinSet a, Ord a, Num a) => Int -> [a] -> [[[a]]]
linesAG2 :: (FinSet a, Ord a, Num a) => Int -> [a] -> [[[a]]]
-- | Incidence graph of PG(n,fq), considered as an incidence structure
-- between points and lines
incidenceGraphPG :: (Num a, Ord a, FinSet a) => Int -> [a] -> Graph (Either [a] [[a]])
-- | Incidence graph of AG(n,fq), considered as an incidence structure
-- between points and lines
incidenceGraphAG :: (Num a, Ord a, FinSet a) => Int -> [a] -> Graph (Either [a] [[a]])
orderGL :: (Num a, Integral b) => b -> a -> a
orderAff :: (Num a, Integral b) => b -> a -> a
orderPGL :: (Integral b, Integral a) => b -> a -> a
heawood :: Graph Integer
instance Eq ZeroOneStar
instance Show ZeroOneStar
-- | A module defining the (non-associative) algebra of octonions over an
-- arbitrary field.
--
-- The octonions are the algebra defined by the basis
-- {1,i0,i1,i2,i3,i4,i5,i6}, where each i_n * i_n = -1, and i_n+1 * i_n+2
-- = i_n+4 (where the indices are modulo 7).
module Math.Algebras.Octonions
data OBasis
O :: Int -> OBasis
type Octonion k = Vect k OBasis
i0 :: Octonion Q
i6 :: Octonion Q
i5 :: Octonion Q
i4 :: Octonion Q
i3 :: Octonion Q
i2 :: Octonion Q
i1 :: Octonion Q
i_ :: Num k => Int -> Octonion k
instance Eq OBasis
instance Ord OBasis
instance (Eq k, Num k) => HasConjugation k OBasis
instance (Eq k, Num k) => Algebra k OBasis
instance Show OBasis
-- | A module for constructing and working with combinatorial designs.
--
-- Given integers t < k < v and lambda > 0, a t-design or
-- t-(v,k,lambda) design is an incidence structure of points X and blocks
-- B, where X is a set of v points, B is a collection of k-subsets of X,
-- with the property that any t points are contained in exactly lambda
-- blocks. If lambda = 1 and t >= 2, then a t-design is also called a
-- Steiner system S(t,k,v).
--
-- Many designs are highly symmetric structures, having large
-- automorphism groups. In particular, the Mathieu groups, which were the
-- first discovered sporadic finite simple groups, turn up as the
-- automorphism groups of the Witt designs.
module Math.Combinatorics.Design
isSubset :: Eq a => [a] -> [a] -> Bool
data Design a
D :: [a] -> [[a]] -> Design a
design :: Ord a => ([a], [[a]]) -> Design a
toDesign :: Ord a => ([a], [[a]]) -> Design a
isValid :: Ord a => Design a -> Bool
points :: Design t -> [t]
blocks :: Design t -> [[t]]
noRepeatedBlocks :: Ord t => Design t -> Bool
tDesignParams :: Eq a => Int -> Design a -> Maybe (Int, Int, Int)
findvk :: Design a -> Maybe (Int, Int)
findlambda :: Eq a => Int -> Design a -> Maybe Int
designParams :: Eq a => Design a -> Maybe (Int, (Int, Int, Int))
isStructure :: Eq a => Int -> Design a -> Bool
isDesign :: Ord a => Int -> Design a -> Bool
is2Design :: Ord a => Design a -> Bool
isSquare :: Ord a => Design a -> Bool
-- | The incidence matrix of a design, with rows indexed by blocks and
-- columns by points. (Note that in the literature, the opposite
-- convention is sometimes used instead.)
incidenceMatrix :: Eq t => Design t -> [[Int]]
subsetDesign :: (Ord a, Num a, Enum a) => a -> Int -> Design a
pairDesign :: Integral a => a -> Design a
-- | The affine plane AG(2,Fq), a 2-(q^2,q,1) design or Steiner system
-- S(2,q,q^2).
ag2 :: (FiniteField k, Ord k) => [k] -> Design [k]
-- | The projective plane PG(2,Fq), a square 2-(q^2+q+1,q+1,1) design or
-- Steiner system S(2,q+1,q^2+q+1). For example, pg2 f2 is the
-- Fano plane, a Steiner triple system S(2,3,7).
pg2 :: (FiniteField k, Ord k) => [k] -> Design [k]
flatsDesignPG :: (FinSet a, Ord a, Num a) => Int -> [a] -> Int -> Design [a]
pg :: (FinSet a, Ord a, Num a) => Int -> [a] -> Design [a]
flatsDesignAG :: (FinSet a, Ord a, Num a) => Int -> [a] -> Int -> Design [a]
ag :: (FinSet a, Ord a, Num a) => Int -> [a] -> Design [a]
to1n :: (Ord a, Num a1, Enum a1) => Design a -> Design a1
paleyDesign :: (Ord a, Num a) => [a] -> Design a
fanoPlane :: Design F7
-- | The dual of a design
dual :: Ord t => Design t -> Design [t]
derivedDesign :: Ord t => Design t -> t -> Design t
pointResidual :: Ord t => Design t -> t -> Design t
complementaryDesign :: Ord a => Design a -> Design a
blockResidual :: Ord t => Design t -> [t] -> Design t
isDesignAut :: Ord a => Design a -> Permutation a -> Bool
-- | The incidence graph of a design
incidenceGraph :: Ord a => Design a -> Graph (Either a [a])
-- | Find a strong generating set for the automorphism group of a design
designAuts :: Ord t => Design t -> [Permutation t]
designAuts1 :: Ord a => Design a -> [Permutation a]
alphaL2_23 :: Permutation Integer
betaL2_23 :: Permutation Integer
gammaL2_23 :: Permutation Integer
l2_23 :: [Permutation Integer]
deltaM24 :: Permutation Integer
-- | Generators for the Mathieu group M24, a finite simple group of order
-- 244823040
m24 :: [Permutation Integer]
-- | A strong generating set for the Mathieu group M24, a finite simple
-- group of order 244823040
m24sgs :: [Permutation Integer]
-- | A strong generating set for the Mathieu group M23, a finite simple
-- group of order 10200960
m23sgs :: [Permutation Integer]
-- | A strong generating set for the Mathieu group M22, a finite simple
-- group of order 443520
m22sgs :: [Permutation Integer]
octad :: [Integer]
-- | The Steiner system S(5,8,24), with 759 blocks, whose automorphism
-- group is M24
s_5_8_24 :: Design Integer
-- | The Steiner system S(4,7,23), with 253 blocks, whose automorphism
-- group is M23
s_4_7_23 :: Design Integer
-- | The Steiner system S(3,6,22), with 77 blocks, whose automorphism group
-- is M22
s_3_6_22 :: Design Integer
s_5_8_24' :: Design Integer
alphaL2_11 :: Permutation Integer
betaL2_11 :: Permutation Integer
gammaL2_11 :: Permutation Integer
l2_11 :: [Permutation Integer]
deltaM12 :: Permutation Integer
hexad :: [Integer]
-- | The Steiner system S(5,6,12), with 132 blocks, whose automorphism
-- group is M12
s_5_6_12 :: Design Integer
-- | The Steiner system S(4,5,11), with 66 blocks, whose automorphism group
-- is M11
s_4_5_11 :: Design Integer
-- | Generators for the Mathieu group M12, a finite simple group of order
-- 95040
m12 :: [Permutation Integer]
-- | A strong generating set for the Mathieu group M12, a finite simple
-- group of order 95040
m12sgs :: [Permutation Integer]
-- | A strong generating set for the Mathieu group M11, a finite simple
-- group of order 7920
m11sgs :: [Permutation Integer]
instance Eq a => Eq (Design a)
instance Ord a => Ord (Design a)
instance Show a => Show (Design a)
-- | A module defining a type for hypergraphs.
module Math.Combinatorics.Hypergraph
data Hypergraph a
H :: [a] -> [[a]] -> Hypergraph a
hypergraph :: Ord a => [a] -> [[a]] -> Hypergraph a
toHypergraph :: Ord a => [a] -> [[a]] -> Hypergraph a
-- | Is this hypergraph uniform - meaning that all blocks are of the same
-- size
isUniform :: Ord a => Hypergraph a -> Bool
same :: Eq a => [a] -> Bool
fromGraph :: Graph a -> Hypergraph a
fromDesign :: Ord a => Design a -> Hypergraph a
incidenceGraph :: Ord a => Hypergraph a -> Graph (Either a [a])
incidenceMatrix :: (Num t, Eq a) => Hypergraph a -> [[t]]
fromIncidenceMatrix :: (Ord a1, Num a1, Num a, Eq a, Enum a1) => [[a]] -> Hypergraph a1
isPartialLinearSpace :: Ord a => Hypergraph a -> Bool
-- | Is this hypergraph a projective plane - meaning that any two lines
-- meet in a unique point, and any two points lie on a unique line
isProjectivePlane :: Ord a => Hypergraph a -> Bool
-- | Is this hypergraph a projective plane with a triangle. This is a weak
-- non-degeneracy condition, which eliminates all points on the same
-- line, or all lines through the same point.
isProjectivePlaneTri :: Ord a => Hypergraph a -> Bool
-- | Is this hypergraph a projective plane with a quadrangle. This is a
-- stronger non-degeneracy condition.
isProjectivePlaneQuad :: Ord a => Hypergraph a -> Bool
isGeneralizedQuadrangle :: Ord a => Hypergraph a -> Bool
grid :: (Ord t1, Ord t, Num t1, Num t, Enum t1, Enum t) => t -> t1 -> Hypergraph (t, t1)
dualGrid :: Integral a => a -> a -> Hypergraph a
isGenQuadrangle' :: Ord a => Hypergraph a -> Bool
-- | Is this hypergraph a (projective) configuration.
isConfiguration :: Ord a => Hypergraph a -> Bool
fanoPlane :: Hypergraph Integer
-- | The Heawood graph is the incidence graph of the Fano plane
heawoodGraph :: Graph (Either Integer [Integer])
desarguesConfiguration :: Hypergraph [Integer]
desarguesGraph :: Graph (Either [Integer] [[Integer]])
pappusConfiguration :: Hypergraph Integer
pappusGraph :: Graph (Either Integer [Integer])
coxeterGraph :: Graph [Integer]
duads :: [[Integer]]
synthemes :: [[[Integer]]]
-- | The Tutte-Coxeter graph, also called the Tutte 8-cage
tutteCoxeterGraph :: Graph (Either [Integer] [[Integer]])
intersectionGraph :: Ord a => Hypergraph a -> Graph [a]
instance Eq a => Eq (Hypergraph a)
instance Ord a => Ord (Hypergraph a)
instance Show a => Show (Hypergraph a)
module Math.Combinatorics.Poset
-- | A poset is represented as a pair (set,po), where set is the underlying
-- set of the poset, and po is the partial order relation
newtype Poset t
Poset :: ([t], t -> t -> Bool) -> Poset t
implies :: Bool -> Bool -> Bool
isReflexive :: ([t], t -> t -> Bool) -> Bool
isAntisymmetric :: Eq a => ([a], a -> a -> Bool) -> Bool
isTransitive :: ([t], t -> t -> Bool) -> Bool
isPoset :: Eq t => ([t], t -> t -> Bool) -> Bool
poset :: Eq t => ([t], t -> t -> Bool) -> Poset t
intervals :: Poset t -> [(t, t)]
interval :: Poset t -> (t, t) -> [t]
-- | A chain is a poset in which every pair of elements is comparable (ie
-- either x <= y or y <= x). It is therefore a linear or total
-- order. chainN n is the poset consisting of the numbers [1..n] ordered
-- by (<=)
chainN :: Int -> Poset Int
-- | An antichain is a poset in which distinct elements are incomparable.
-- antichainN n is the poset consisting of [1..n], with x <= y only
-- when x == y.
antichainN :: Int -> Poset Int
divides :: Integral a => a -> a -> Bool
divisors :: Integral a => a -> [a]
-- | posetD n is the lattice of (positive) divisors of n
posetD :: Int -> Poset Int
powerset :: [t] -> [[t]]
-- | posetB n is the lattice of subsets of [1..n] ordered by inclusion
posetB :: Int -> Poset [Int]
partitions :: [t] -> [[[t]]]
isRefinement :: Ord a => [[a]] -> [[a]] -> Bool
-- | posetP n is the lattice of set partitions of [1..n], ordered by
-- refinement
posetP :: Int -> Poset [[Int]]
intervalPartitions :: (Num a, Eq a) => [a] -> [[[a]]]
isInterval :: (Num a, Eq a) => [a] -> Bool
intervalPartitions2 :: [t] -> [[[t]]]
integerPartitions :: (Ord t, Num t) => t -> [[t]]
isIPRefinement :: (Ord a, Num a) => [a] -> [a] -> Bool
-- | posetIP n is the poset of integer partitions of n, ordered by
-- refinement
posetIP :: Int -> Poset [Int]
subspaces :: (Num a, Eq a) => [a] -> Int -> [[[a]]]
isSubspace :: (Num a, Eq a) => [[a]] -> [[a]] -> Bool
-- | 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. Example usage: posetL 2 f3
posetL :: (Eq fq, Num fq) => Int -> [fq] -> Poset [[fq]]
-- | The subposet of a poset satisfying a predicate
subposet :: Poset a -> (a -> Bool) -> Poset a
-- | The direct sum of two posets
dsum :: Poset a -> Poset b -> Poset (Either a b)
-- | The direct product of two posets
dprod :: Poset a -> Poset b -> Poset (a, b)
-- | The dual of a poset
dual :: Poset a -> Poset a
-- | Given a poset (X,<=), we say that y covers x, written x -< y, if
-- x < y and there is no z in X with x < z < y. The Hasse
-- digraph of a poset is the digraph whose vertices are the elements of
-- the poset, with an edge between every pair (x,y) with x -< y. The
-- Hasse digraph can be represented diagrammatically as a Hasse diagram,
-- by drawing x below y whenever x -< y.
hasseDigraph :: Eq a => Poset a -> Digraph a
-- | Given a DAG (directed acyclic graph), return the poset consisting of
-- the vertices of the DAG, ordered by reachability. This can be used to
-- recover a poset from its Hasse digraph.
reachabilityPoset :: Ord a => Digraph a -> Poset a
isOrderPreserving :: (a -> b) -> Poset a -> Poset b -> Bool
orderIsos01 :: Poset a -> Poset a1 -> [[(a, a1)]]
-- | Are the two posets order-isomorphic?
isOrderIso :: (Ord a, Ord b) => Poset a -> Poset b -> Bool
-- | Find all order isomorphisms between two posets
orderIsos :: (Ord a, Ord b) => Poset a -> Poset b -> [[(a, b)]]
orderAuts1 :: Ord b => Poset b -> [[(b, b)]]
-- | A linear extension of a poset is a linear ordering of the elements
-- which extends the partial order. Equivalently, it is an ordering
-- [x1..xn] of the underlying set, such that if xi <= xj then i <=
-- j.
isLinext :: Poset t -> [t] -> Bool
-- | Linear extensions of a poset
linexts :: Poset a -> [[a]]
instance Show t => Show (Poset t)
instance Eq t => Eq (Poset t)
-- | A module defining the following Combinatorial Hopf Algebras, together
-- with coalgebra or Hopf algebra morphisms between them:
--
--
-- - Sh, the Shuffle Hopf algebra
-- - SSym, the Malvenuto-Reutnenauer Hopf algebra of permutations
-- - YSym, the (dual of the) Loday-Ronco Hopf algebra of binary
-- trees
-- - QSym, the Hopf algebra of quasi-symmetric functions (having a
-- basis indexed by compositions)
-- - Sym, the Hopf algebra of symmetric functions (having a basis
-- indexed by integer partitions)
-- - NSym, the Hopf algebra of non-commutative symmetric functions
--
module Math.Combinatorics.CombinatorialHopfAlgebra
-- | A basis for the shuffle algebra. As a vector space, the shuffle
-- algebra is identical to the tensor algebra. However, we consider a
-- different algebra structure, based on the shuffle product. Together
-- with the deconcatenation coproduct, this leads to a Hopf algebra
-- structure.
newtype Shuffle a
Sh :: [a] -> Shuffle a
-- | Construct a basis element of the shuffle algebra
sh :: [a] -> Vect Q (Shuffle a)
shuffles :: [a] -> [a] -> [[a]]
deconcatenations :: [a] -> [([a], [a])]
-- | The fundamental basis for the Malvenuto-Reutenauer Hopf algebra of
-- permutations, SSym.
newtype SSymF
SSymF :: [Int] -> SSymF
-- | Construct a fundamental basis element in SSym. The list of ints must
-- be a permutation of [1..n], eg [1,2], [3,4,2,1].
ssymF :: [Int] -> Vect Q SSymF
shiftedConcat :: SSymF -> SSymF -> SSymF
prop_Associative :: Eq t => (t -> t -> t) -> (t, t, t) -> Bool
flatten :: (Ord a, Num t, Enum t) => [a] -> [t]
-- | A pairing showing that SSym is self-adjoint
-- | An alternative "monomial" basis for the Malvenuto-Reutenauer Hopf
-- algebra of permutations, SSym. This basis is related to the
-- fundamental basis by Mobius inversion in the poset of permutations
-- with the weak order.
newtype SSymM
SSymM :: [Int] -> SSymM
-- | Construct a monomial basis element in SSym. The list of ints must be a
-- permutation of [1..n], eg [1,2], [3,4,2,1].
ssymM :: [Int] -> Vect Q SSymM
inversions :: (Ord a, Num t, Enum t) => [a] -> [(t, t)]
weakOrder :: (Ord a1, Ord a) => [a] -> [a1] -> Bool
mu :: (Num s, Eq a) => ([a], a -> a -> Bool) -> a -> a -> s
-- | Convert an element of SSym represented in the monomial basis to the
-- fundamental basis
ssymMtoF :: (Eq k, Num k) => Vect k SSymM -> Vect k SSymF
-- | Convert an element of SSym represented in the fundamental basis to the
-- monomial basis
ssymFtoM :: (Eq k, Num k) => Vect k SSymF -> Vect k SSymM
-- | The isomorphism from SSym to its dual that takes a permutation in the
-- fundamental basis to its inverse in the dual basis
ssymFtoDual :: (Eq k, Num k) => Vect k SSymF -> Vect k (Dual SSymF)
-- | A type for (rooted) planar binary trees. The basis elements of the
-- Loday-Ronco Hopf algebra are indexed by these.
--
-- Although the trees are labelled, we're really only interested in the
-- shapes of the trees, and hence in the type PBT (). The Algebra,
-- Coalgebra and HopfAlgebra instances all ignore the labels. However, it
-- is convenient to allow labels, as they can be useful for seeing what
-- is going on, and they also make it possible to define various ways to
-- create trees from lists of labels.
data PBT a
T :: (PBT a) -> a -> (PBT a) -> PBT a
E :: PBT a
-- | The fundamental basis for (the dual of) the Loday-Ronco Hopf algebra
-- of binary trees, YSym.
newtype YSymF a
YSymF :: (PBT a) -> YSymF a
-- | Construct the element of YSym in the fundamental basis indexed by the
-- given tree
ysymF :: PBT a -> Vect Q (YSymF a)
nodecount :: Num a => PBT t -> a
leafcount :: Num a => PBT t -> a
prefix :: PBT t -> [t]
shapeSignature :: Num t => PBT t1 -> [t]
nodeCountTree :: Num a => PBT t -> PBT a
leafCountTree :: Num a => PBT t -> PBT a
lrCountTree :: Num a => PBT t -> PBT (a, a)
shape :: PBT a -> PBT ()
numbered :: Num a => PBT t -> PBT a
splits :: PBT a -> [(PBT a, PBT a)]
multisplits :: (Num a, Eq a) => a -> PBT a1 -> [[PBT a1]]
graft :: [PBT a] -> PBT a -> PBT a
-- | An alternative "monomial" basis for (the dual of) the Loday-Ronco Hopf
-- algebra of binary trees, YSym.
newtype YSymM
YSymM :: (PBT ()) -> YSymM
-- | Construct the element of YSym in the monomial basis indexed by the
-- given tree
ysymM :: PBT () -> Vect Q YSymM
-- | List all trees with the given number of nodes
trees :: Int -> [PBT ()]
-- | The covering relation for the Tamari partial order on binary trees
tamariCovers :: PBT a -> [PBT a]
-- | The up-set of a binary tree in the Tamari partial order
tamariUpSet :: Ord a => PBT a -> [PBT a]
-- | The Tamari partial order on binary trees. This is only defined between
-- trees of the same size (number of nodes). The result between trees of
-- different sizes is undefined (we don't check).
tamariOrder :: PBT a -> PBT a -> Bool
-- | Convert an element of YSym represented in the monomial basis to the
-- fundamental basis
ysymMtoF :: (Eq k, Num k) => Vect k YSymM -> Vect k (YSymF ())
-- | Convert an element of YSym represented in the fundamental basis to the
-- monomial basis
ysymFtoM :: (Eq k, Num k) => Vect k (YSymF ()) -> Vect k YSymM
-- | List the compositions of an integer n. For example, the compositions
-- of 4 are [[1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1],[4]]
compositions :: Int -> [[Int]]
quasiShuffles :: [Int] -> [Int] -> [[Int]]
-- | A type for the monomial basis for the quasi-symmetric functions,
-- indexed by compositions.
newtype QSymM
QSymM :: [Int] -> QSymM
-- | Construct the element of QSym in the monomial basis indexed by the
-- given composition
qsymM :: [Int] -> Vect Q QSymM
coarsenings :: Num a => [a] -> [[a]]
refinements :: [Int] -> [[Int]]
-- | A type for the fundamental basis for the quasi-symmetric functions,
-- indexed by compositions.
newtype QSymF
QSymF :: [Int] -> QSymF
-- | Construct the element of QSym in the fundamental basis indexed by the
-- given composition
qsymF :: [Int] -> Vect Q QSymF
-- | Convert an element of QSym represented in the monomial basis to the
-- fundamental basis
qsymMtoF :: (Eq k, Num k) => Vect k QSymM -> Vect k QSymF
-- | Convert an element of QSym represented in the fundamental basis to the
-- monomial basis
qsymFtoM :: (Eq k, Num k) => Vect k QSymF -> Vect k QSymM
-- | qsymPoly n is is the quasi-symmetric polynomial in n
-- variables for the indices is. (This corresponds to the monomial basis
-- for QSym.) For example, qsymPoly 3 [2,1] == x1^2*x2+x1^2*x3+x2^2*x3.
qsymPoly :: Int -> [Int] -> GlexPoly Q String
-- | A type for the monomial basis for Sym, the Hopf algebra of symmetric
-- functions, indexed by integer partitions
newtype SymM
SymM :: [Int] -> SymM
-- | Construct the element of Sym in the monomial basis indexed by the
-- given integer partition
symM :: [Int] -> Vect Q SymM
compositionsFromPartition :: Eq a => [a] -> [[a]]
symMult :: [Int] -> [Int] -> [[Int]]
-- | The elementary basis for Sym, the Hopf algebra of symmetric functions.
-- Defined informally as > symE [n] = symM (replicate n 1) > symE
-- lambda = product [symE [p] | p <- lambda]
newtype SymE
SymE :: [Int] -> SymE
symE :: [Int] -> Vect Q SymE
-- | Convert from the elementary to the monomial basis of Sym
symEtoM :: (Eq k, Num k) => Vect k SymE -> Vect k SymM
-- | The complete basis for Sym, the Hopf algebra of symmetric functions.
-- Defined informally as > symH [n] = sum [symM lambda | lambda <-
-- integerPartitions n] -- == all monomials of weight n > symH lambda
-- = product [symH [p] | p <- lambda]
newtype SymH
SymH :: [Int] -> SymH
symH :: [Int] -> Vect Q SymH
-- | Convert from the complete to the monomial basis of Sym
symHtoM :: (Eq k, Num k) => Vect k SymH -> Vect k SymM
-- | A basis for NSym, the Hopf algebra of non-commutative symmetric
-- functions, indexed by compositions
newtype NSym
NSym :: [Int] -> NSym
nsym :: [Int] -> Vect Q NSym
descendingTree :: Ord t => [t] -> PBT t
-- | Given a permutation p of [1..n], we can construct a tree (the
-- descending tree of p) as follows:
--
--
-- - Split the permutation as p = ls ++ [n] ++ rs
-- - Place n at the root of the tree, and recursively place the
-- descending trees of ls and rs as the left and right children of the
-- root
-- - To bottom out the recursion, the descending tree of the empty
-- permutation is of course the empty tree
--
--
-- This map between bases SSymF -> YSymF turns out to induce a
-- morphism of Hopf algebras.
descendingTreeMap :: (Eq k, Num k) => Vect k SSymF -> Vect k (YSymF ())
minPerm :: Num t => PBT t1 -> [t]
maxPerm :: Num t => PBT t1 -> [t]
leftLeafComposition :: PBT t -> [Int]
leftLeafComposition' :: YSymF t -> QSymF
-- | A Hopf algebra morphism from YSymF to QSymF
leftLeafCompositionMap :: (Eq k, Num k) => Vect k (YSymF a) -> Vect k QSymF
descents :: Ord b => [b] -> [Int]
descentComposition :: (Ord a, Num t) => [a] -> [t]
-- | Given a permutation of [1..n], its descents are those positions where
-- the next number is less than the previous number. For example, the
-- permutation [2,3,5,1,6,4] has descents from 5 to 1 and from 6 to 4.
-- The descents can be regarded as cutting the permutation sequence into
-- segments - 235-16-4 - and by counting the lengths of the segments, we
-- get a composition 3+2+1. This map between bases SSymF -> QSymF
-- turns out to induce a morphism of Hopf algebras.
descentMap :: (Eq k, Num k) => Vect k SSymF -> Vect k QSymF
underComposition :: QSymF -> SSymF
under :: PBT a -> PBT a -> PBT a
isUnderIrreducible :: PBT t -> Bool
underDecomposition :: PBT a -> [PBT a]
ysymmToSh :: Functor f => f YSymM -> f (Shuffle (PBT ()))
-- | The injection of Sym into QSym (defined over the monomial basis)
symToQSymM :: (Eq k, Num k) => Vect k SymM -> Vect k QSymM
-- | A surjection of NSym onto Sym (defined over the complete basis)
nsymToSymH :: (Eq k, Num k) => Vect k NSym -> Vect k SymH
nsymToSSym :: (Num k, Eq k) => Vect k NSym -> Vect k SSymF
-- | A duality pairing between the complete and monomial bases of Sym,
-- showing that Sym is self-dual.
-- | A duality pairing between NSym and QSymM (monomial basis), showing
-- that NSym and QSym are dual.
instance Eq a => Eq (Shuffle a)
instance Ord a => Ord (Shuffle a)
instance Show a => Show (Shuffle a)
instance Eq SSymF
instance Eq SSymM
instance Eq a => Eq (PBT a)
instance Show a => Show (PBT a)
instance Functor PBT
instance Eq a => Eq (YSymF a)
instance Ord a => Ord (YSymF a)
instance Functor YSymF
instance Eq YSymM
instance Ord YSymM
instance Eq QSymM
instance Eq QSymF
instance Eq SymM
instance Show SymM
instance Eq SymE
instance Ord SymE
instance Show SymE
instance Eq SymH
instance Ord SymH
instance Show SymH
instance Eq NSym
instance Ord NSym
instance Show NSym
instance (Eq k, Num k) => HasPairing k NSym QSymM
instance (Eq k, Num k) => HasPairing k SymH SymM
instance (Eq k, Num k) => HopfAlgebra k NSym
instance (Eq k, Num k) => Bialgebra k NSym
instance (Eq k, Num k) => Coalgebra k NSym
instance (Eq k, Num k) => Algebra k NSym
instance (Eq k, Num k) => Bialgebra k SymH
instance (Eq k, Num k) => Coalgebra k SymH
instance (Eq k, Num k) => Algebra k SymH
instance (Eq k, Num k) => Bialgebra k SymE
instance (Eq k, Num k) => Coalgebra k SymE
instance (Eq k, Num k) => Algebra k SymE
instance (Eq k, Num k) => HopfAlgebra k SymM
instance (Eq k, Num k) => Bialgebra k SymM
instance (Eq k, Num k) => Coalgebra k SymM
instance (Eq k, Num k) => Algebra k SymM
instance Ord SymM
instance (Eq k, Num k) => HopfAlgebra k QSymF
instance (Eq k, Num k) => Bialgebra k QSymF
instance (Eq k, Num k) => Coalgebra k QSymF
instance (Eq k, Num k) => Algebra k QSymF
instance Show QSymF
instance Ord QSymF
instance (Eq k, Num k) => HopfAlgebra k QSymM
instance (Eq k, Num k) => Bialgebra k QSymM
instance (Eq k, Num k) => Coalgebra k QSymM
instance (Eq k, Num k) => Algebra k QSymM
instance Show QSymM
instance Ord QSymM
instance (Eq k, Num k) => HopfAlgebra k YSymM
instance (Eq k, Num k) => Bialgebra k YSymM
instance (Eq k, Num k) => Coalgebra k YSymM
instance (Eq k, Num k) => Algebra k YSymM
instance Show YSymM
instance (Eq k, Num k, Ord a) => HopfAlgebra k (YSymF a)
instance (Eq k, Num k, Ord a) => Bialgebra k (YSymF a)
instance (Eq k, Num k, Ord a) => Algebra k (YSymF a)
instance (Eq k, Num k, Ord a) => Coalgebra k (YSymF a)
instance Show a => Show (YSymF a)
instance Ord a => Ord (PBT a)
instance (Eq k, Num k) => HasPairing k SSymF (Dual SSymF)
instance (Eq k, Num k) => HopfAlgebra k (Dual SSymF)
instance (Eq k, Num k) => Bialgebra k (Dual SSymF)
instance (Eq k, Num k) => Coalgebra k (Dual SSymF)
instance (Eq k, Num k) => Algebra k (Dual SSymF)
instance (Eq k, Num k) => HopfAlgebra k SSymM
instance (Eq k, Num k) => Bialgebra k SSymM
instance (Eq k, Num k) => Coalgebra k SSymM
instance (Eq k, Num k) => Algebra k SSymM
instance Show SSymM
instance Ord SSymM
instance (Eq k, Num k) => HasPairing k SSymF SSymF
instance HasInverses SSymF
instance (Eq k, Num k) => HopfAlgebra k SSymF
instance (Eq k, Num k) => Bialgebra k SSymF
instance (Eq k, Num k) => Coalgebra k SSymF
instance (Eq k, Num k) => Algebra k SSymF
instance Show SSymF
instance Ord SSymF
instance (Eq k, Num k, Ord a) => HopfAlgebra k (Shuffle a)
instance (Eq k, Num k, Ord a) => Bialgebra k (Shuffle a)
instance (Eq k, Num k, Ord a) => Coalgebra k (Shuffle a)
instance (Eq k, Num k, Ord a) => Algebra k (Shuffle a)
module Math.Combinatorics.IncidenceAlgebra
-- | A type to represent an interval in a poset. The (closed) interval
-- [x,y] is the set {z | x <= z <= y} within the poset. Note that
-- the "empty interval" is not an interval - that is, the interval [x,y]
-- is only defined for x <= y. The (closed) intervals within a poset
-- form a basis for the incidence algebra as a k-vector space.
data Interval a
Iv :: (Poset a) -> (a, a) -> Interval a
ivPoset :: Interval t -> Poset t
intervalIsos :: (Ord b, Ord a) => Interval a -> Interval b -> [[(a, b)]]
isIntervalIso :: (Ord b, Ord a) => Interval a -> Interval b -> Bool
intervalIsoMap :: Ord b => Poset b -> Map (Interval b) (Maybe (Interval b))
-- | List representatives of the order isomorphism classes of intervals in
-- a poset
intervalIsoClasses :: Ord a => Poset a -> [Interval a]
-- | The incidence algebra of a poset is the free k-vector space having as
-- its basis the set of intervals in the poset, 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 ].
-- | The unit of the incidence algebra of a poset
unitIA :: (Eq k, Num k, Ord a) => Poset a -> Vect k (Interval a)
basisIA :: Num k => Poset a -> [Vect k (Interval a)]
-- | The zeta function of a poset
zetaIA :: (Eq k, Num k, Ord a) => Poset a -> Vect k (Interval a)
muIA1 :: (Show a, Ord a, Num k, Eq k) => Poset a -> Vect k (Interval a)
-- | The Mobius function of a poset
muIA :: (Eq k, Num k, Ord a) => Poset a -> Vect k (Interval a)
invIA1 :: (Ord t, Fractional a, Eq a) => Vect a (Interval t) -> Vect a (Interval t)
-- | 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 :: (Eq k, Fractional k, Ord a) => Vect k (Interval a) -> Maybe (Vect k (Interval a))
-- | A function (ie element of the incidence algebra) that counts the total
-- number of chains in each interval
numChainsIA :: (Ord a, Show a) => Poset a -> Vect Q (Interval a)
etaIA :: (Ord a, Num k, Eq k) => Poset a -> Vect k (Interval a)
-- | A function (ie element of the incidence algebra) that counts the
-- number of maximal chains in each interval
numMaximalChainsIA :: (Ord a, Show a) => Poset a -> Vect Q (Interval a)
muC :: (Num k, Eq k) => Int -> Vect k (Interval Int)
muB :: (Num k, Eq k) => Int -> Vect k (Interval [Int])
muL :: (Ord a, Num a) => Int -> [a] -> Vect Int (Interval [[a]])
-- | toIsoClasses is the linear map from the incidence Hopf
-- algebra of a poset to itself, in which each interval is mapped to (the
-- minimal representative of) its isomorphism class. Thus the result can
-- be considered as a linear combination of isomorphism classes of
-- intervals, 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 :: (Eq k, Num k, Ord a) => Vect k (Interval a) -> Vect k (Interval a)
-- | 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' :: (Eq k, Num k, Ord a) => Poset a -> Vect k (Interval a) -> Vect k (Interval a)
instance (Eq k, Num k, Ord a) => Coalgebra k (Interval a)
instance (Eq k, Fractional k, Ord a, Show a) => HasInverses (Vect k (Interval a))
instance (Eq k, Num k, Ord a) => Algebra k (Interval a)
instance Show a => Show (Interval a)
instance Ord a => Ord (Interval a)
instance Eq a => Eq (Interval a)
-- | A module defining various strongly regular graphs, including the
-- Clebsch, Hoffman-Singleton, Higman-Sims, and McLaughlin graphs.
--
-- A strongly regular graph with parameters (n,k,lambda,mu) is a (simple)
-- graph with n vertices, in which the number of common neighbours of x
-- and y is k, lambda or mu according as whether x and y are equal,
-- adjacent, or non-adjacent. (In particular, it is a k-regular graph.)
--
-- Strongly regular graphs are highly symmetric, and have large
-- automorphism groups.
module Math.Combinatorics.StronglyRegularGraph
srgParams :: Ord a => Graph a -> Maybe (Int, Int, Int, Int)
isSRG :: Ord a => Graph a -> Bool
t' :: (Ord a, Ord t, Num a, Num t, Enum a, Enum t) => a -> Graph t
t :: (Ord a, Num a, Enum a) => a -> Graph [a]
l2' :: (Ord a, Ord t, Num a, Num t, Enum a, Enum t) => a -> Graph t
l2 :: (Ord a, Num a, Enum a) => a -> Graph (a, a)
paleyGraph :: (Ord t, Num t) => [t] -> Graph t
clebsch' :: Graph Integer
clebsch :: Graph [Integer]
clebsch2 :: Graph DesignVertex
triples :: [[Integer]]
heptads :: [[[Integer]]]
(+^) :: Ord a => [[a]] -> Permutation a -> [[a]]
(+^^) :: Ord a => [[a]] -> [Permutation a] -> [[[a]]]
hoffmanSingleton' :: Graph Integer
hoffmanSingleton :: Graph (Either [[Integer]] [Integer])
inducedA7 :: Permutation Integer -> Permutation (Either [[Integer]] [Integer])
hsA7 :: [Permutation Integer]
gewirtz' :: Graph Integer
gewirtz :: Graph [Integer]
data DesignVertex
C :: DesignVertex
P :: Integer -> DesignVertex
B :: [Integer] -> DesignVertex
higmanSimsGraph' :: Graph Integer
higmanSimsGraph :: Graph DesignVertex
inducedM22 :: Permutation Integer -> Permutation DesignVertex
higmanSimsM22 :: [Permutation Integer]
_HS2 :: [Permutation DesignVertex]
_HS :: [Permutation DesignVertex]
sp2 :: Int -> Graph [F2]
sp :: Int -> Graph [F2]
switch :: Ord t => Graph t -> [t] -> Graph t
schlafli' :: Graph Integer
schlafli :: Graph Integer
mcLaughlin' :: Graph Integer
mcLaughlin :: Graph DesignVertex
_McL2 :: [Permutation DesignVertex]
_McL :: [Permutation DesignVertex]
instance Eq DesignVertex
instance Ord DesignVertex
instance Show DesignVertex
module Math.Combinatorics.LatinSquares
findLatinSqs :: Eq a => [a] -> [[[a]]]
isLatinSq :: Ord a => [[a]] -> Bool
isOneOfEach :: Ord a => [a] -> Bool
incidenceGraphLS :: Ord a => [[a]] -> Graph (Int, Int, a)
incidenceGraphLS' :: Eq a => [[a]] -> Graph (Int, Int)
-- | Are the two latin squares orthogonal?
isOrthogonal :: (Ord a, Ord b) => [[a]] -> [[b]] -> Bool
findMOLS :: (Ord b, Num a, Eq a) => a -> [[[b]]] -> [[[[b]]]]
-- | Are the latin squares mutually orthogonal (ie each pair is
-- orthogonal)?
isMOLS :: Ord a => [[[a]]] -> Bool
-- | MOLS from a projective plane
fromProjectivePlane :: (Ord k, Num k) => Design [k] -> [[[Int]]]
isOA :: Ord b => (Int, Int) -> [[b]] -> Bool
fromLS :: [[Int]] -> [[Int]]
fromMOLS :: [[[Int]]] -> [[Int]]
graphOA :: Ord b => [[b]] -> Graph [b]
srgParamsOA :: Num t => (t, t) -> Maybe (t, t, t, t)
-- | A module providing functions to construct and investigate (small,
-- finite) matroids.
module Math.Combinatorics.Matroid
implies :: Bool -> Bool -> Bool
exists :: [a] -> Bool
unique :: [t] -> t
shortlex :: Ord a => [a] -> [a] -> Ordering
isShortlex :: Ord a => [[a]] -> Bool
toShortlex :: Ord a => [[a]] -> [[a]]
isClutter :: Ord a => [[a]] -> Bool
deletions :: [a] -> [[a]]
closedUnderSubsets :: Ord a => [[a]] -> Bool
-- | The data structure that we use to store the bases of the matroid
data TrieSet a
TS :: [(a, TrieSet a)] -> TrieSet a
tsshow :: Show a => TrieSet a -> [Char]
tsempty :: TrieSet a
tsinsert :: Ord a => [a] -> TrieSet a -> TrieSet a
tsmember :: Eq a => [a] -> TrieSet a -> Bool
tssubmember :: Ord a => [a] -> TrieSet a -> Bool
tstolist :: TrieSet t -> [[t]]
tsfromlist :: Ord a => [[a]] -> TrieSet a
-- | A datatype to represent a matroid. M es bs is the matroid
-- whose elements are es, and whose bases are bs. The
-- normal form is for the es to be in order, for each of the
-- bs individually to be in order. (So the TrieSet should have
-- the property that any path from the root to a leaf is strictly
-- increasing).
data Matroid a
M :: [a] -> (TrieSet a) -> Matroid a
-- | Return the elements over which the matroid is defined.
elements :: Matroid t -> [t]
-- | Return all the independent sets of a matroid, in shortlex order.
indeps :: Ord a => Matroid a -> [[a]]
isIndependent :: Ord a => Matroid a -> [a] -> Bool
isDependent :: Ord a => Matroid a -> [a] -> Bool
-- | Are these the independent sets of a matroid? (The sets must
-- individually be ordered.)
isMatroidIndeps :: Ord a => [[a]] -> Bool
-- | Construct a matroid from its elements and its independent sets.
fromIndeps :: Ord a => [a] -> [[a]] -> Matroid a
fromIndeps1 :: Ord a => [a] -> [[a]] -> Matroid a
-- | 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 :: (Eq k, Fractional k) => [[k]] -> Matroid Int
-- | 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' :: (Eq k, Fractional k) => [[k]] -> Matroid Int
-- | Given the edges of an undirected graph, number the edges [1..], and
-- construct the matroid whose independent sets correspond to those sets
-- of edges which contain no cycle. The bases therefore correspond to
-- maximal forests within the graph. The edge set is allowed to contain
-- loops or parallel edges.
cycleMatroid :: Ord a => [[a]] -> Matroid Int
cycleMatroid' :: Ord a => [[a]] -> Matroid [a]
-- | Given a matroid over an arbitrary type, relabel to obtain a matroid
-- over the integers.
to1n :: Ord a => Matroid a -> Matroid Int
incidenceGraphB :: Ord a => Matroid a -> Graph (Either a [a])
incidenceGraphC :: Ord a => Matroid a -> Graph (Either a [a])
incidenceGraphH :: Ord a => Matroid a -> Graph (Either a [a])
matroidIsos :: (Ord t3, Ord t2) => Matroid t2 -> Matroid t3 -> [[(t2, t3)]]
-- | Are the two matroids isomorphic?
isMatroidIso :: (Ord a, Ord b) => Matroid a -> Matroid b -> Bool
-- | Return the automorphisms of the matroid.
matroidAuts :: Ord a => Matroid a -> [Permutation a]
-- | A circuit in a matroid is a minimal dependent set.
isCircuit :: Ord a => Matroid a -> [a] -> Bool
-- | Return all circuits for the given matroid, in shortlex order.
circuits :: Ord a => Matroid a -> [[a]]
-- | Are the given sets the circuits of some matroid?
isMatroidCircuits :: Ord a => [[a]] -> Bool
-- | Reconstruct a matroid from its elements and circuits.
fromCircuits :: Ord a => [a] -> [[a]] -> Matroid a
-- | An element e in a matroid M is a loop if {e} is a circuit of M.
isLoop :: Ord a => Matroid a -> a -> Bool
-- | Elements f and g in a matroid M are parallel if {f,g} is a circuit of
-- M.
isParallel :: Ord a => Matroid a -> a -> a -> Bool
-- | A matroid is simple if it has no loops or parallel elements
isSimple :: Ord a => Matroid a -> Bool
-- | A base or basis in a matroid is a maximal independent set.
isBase :: Ord a => Matroid a -> [a] -> Bool
-- | Return all bases for the given matroid
bases :: Ord a => Matroid a -> [[a]]
-- | Are the given sets the bases of some matroid?
isMatroidBases :: Ord a => [[a]] -> Bool
-- | Reconstruct a matroid from its elements and bases.
fromBases :: Ord a => [a] -> [[a]] -> Matroid a
-- | Given a matroid m, a basis b, and an element e, fundamentalCircuit
-- m b e returns the unique circuit contained in b union {e}, which
-- is called the fundamental circuit of e with respect to b.
fundamentalCircuit :: Ord a => Matroid a -> [a] -> a -> [a]
uniformMatroid :: Int -> Int -> Matroid Int
-- | The uniform matroid U m n is the matroid whose independent sets are
-- all subsets of [1..n] with m or fewer elements.
u :: Int -> Int -> Matroid Int
restriction1 :: Ord a => Matroid a -> [a] -> Matroid a
-- | The restriction of a matroid to a subset of its elements
restriction :: Ord a => Matroid a -> [a] -> Matroid a
-- | Given a matroid m, rankfun m is the rank function on subsets
-- of its element set
rankfun :: Ord a => Matroid a -> [a] -> Int
-- | The rank of a matroid is the cardinality of a basis
rank :: Ord a => Matroid a -> Int
-- | Reconstruct a matroid from its elements and rank function
fromRankfun :: Ord a => [a] -> ([a] -> Int) -> Matroid a
-- | Given a matroid m, closure m is the closure operator on
-- subsets of its element set
closure :: Ord a => Matroid a -> [a] -> [a]
-- | Reconstruct a matroid from its elements and closure operator
fromClosure :: Ord a => [a] -> ([a] -> [a]) -> Matroid a
-- | A flat in a matroid is a closed set, that is a set which is equal to
-- its own closure
isFlat :: Ord a => Matroid a -> [a] -> Bool
flats1 :: Ord a => Matroid a -> [[a]]
coveringFlats :: Ord t => Matroid t -> [t] -> [[t]]
minimalFlat :: Ord a => Matroid a -> [a]
-- | The flats of a matroid are its closed sets. They form a lattice under
-- inclusion.
flats :: Ord a => Matroid a -> [[a]]
-- | Reconstruct a matroid from its flats. (The flats must be given in
-- shortlex order.)
fromFlats :: Ord a => [[a]] -> Matroid a
fromFlats' :: Ord a => [[a]] -> Matroid a
-- | A subset of the elements in a matroid is spanning if its closure is
-- all the elements
isSpanning :: Ord a => Matroid a -> [a] -> Bool
-- | A hyperplane is a flat whose rank is one less than that of the matroid
isHyperplane :: Ord a => Matroid a -> [a] -> Bool
hyperplanes1 :: Ord a => Matroid a -> [[a]]
hyperplanes :: Ord a => Matroid a -> [[a]]
isMatroidHyperplanes :: Ord a => [a] -> [[a]] -> Bool
fromHyperplanes1 :: Ord a => [a] -> [[a]] -> Matroid a
-- | Reconstruct a matroid from its elements and hyperplanes
fromHyperplanes :: Ord a => [a] -> [[a]] -> Matroid a
-- | Given a list of points in k^n, number the points [1..], and construct
-- the matroid whose independent sets correspond to those sets of points
-- which are affinely independent.
--
-- 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 :: (Eq k, Fractional k) => [[k]] -> Matroid Int
-- | fromGeoRep returns a matroid from a geometric representation
-- consisting of dependent flats of various ranks. Given lists of
-- dependent rank 0 flats (loops), rank 1 flats (points), rank 2 flats
-- (lines) and rank 3 flats (planes), fromGeoRep loops points lines
-- planes returns the matroid having these as dependent flats. Note
-- that if all the elements lie in the same plane, then this should still
-- be listed as an argument.
fromGeoRep :: Ord a => [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
minimal :: Ord a => [[a]] -> [[a]]
-- | A simple matroid has no loops or parallel elements, hence its
-- geometric representation has no loops or dependent points.
-- simpleFromGeoRep lines planes returns the simple matroid
-- having these dependent flats.
simpleFromGeoRep :: Ord a => [[a]] -> [[a]] -> Matroid a
isSimpleGeoRep :: Ord a => [[a]] -> [[a]] -> Bool
isCircuitHyperplane :: Ord a => Matroid a -> [a] -> Bool
-- | List the circuit-hyperplanes of a matroid.
circuitHyperplanes :: Ord a => Matroid a -> [[a]]
-- | Given a matroid m, and a set of elements b which is both a circuit and
-- a hyperplane in m, then relaxation m b is the matroid which
-- is obtained by adding b as a new basis. This corresponds to removing b
-- from the geometric representation of m.
relaxation :: Ord a => Matroid a -> [a] -> Matroid a
ex161 :: Num t => [[t]]
transversalGraph :: (Num b1, Enum b1) => [[a]] -> [(Either a b, Either a1 b1)]
partialMatchings :: Ord a => [(a, a)] -> [[(a, a)]]
-- | Given a set of elements es, and a sequence as = [a1,...,am] of subsets
-- of es, return the matroid whose independent sets are the partial
-- transversals of the as.
transversalMatroid :: Ord a => [a] -> [[a]] -> Matroid a
-- | The dual matroid
dual :: Ord a => Matroid a -> Matroid a
isCoindependent :: Ord a => Matroid a -> [a] -> Bool
isCobase :: Ord a => Matroid a -> [a] -> Bool
isCocircuit :: Ord a => Matroid a -> [a] -> Bool
cocircuits :: Ord a => Matroid a -> [[a]]
isColoop :: Ord a => Matroid a -> a -> Bool
isCoparallel :: Ord a => Matroid a -> a -> a -> Bool
deletion :: Ord a => Matroid a -> [a] -> Matroid a
(\\\) :: Ord a => Matroid a -> [a] -> Matroid a
contraction :: Ord a => Matroid a -> [a] -> Matroid a
(///) :: Ord a => Matroid a -> [a] -> Matroid a
-- | A matroid is (2-)connected if, for every pair of distinct elements,
-- there is a circuit containing both
isConnected :: Ord a => Matroid a -> Bool
component :: Ord a => Matroid a -> a -> [a]
-- | The direct sum of two matroids
dsum :: (Ord a, Ord b) => Matroid a -> Matroid b -> Matroid (Either a b)
-- | matroidPG n fq returns the projective geometry PG(n,Fq),
-- where fq is a list of the elements of Fq
matroidPG :: (Eq a, Fractional a) => Int -> [a] -> Matroid Int
-- | matroidAG n fq returns the affine geometry AG(n,Fq), where fq
-- is a list of the elements of Fq
matroidAG :: (Eq a, Fractional a) => Int -> [a] -> Matroid Int
-- | Given a matroid m, the fundamental-circuit incidence matrix relative
-- to a base b has rows indexed by the elements of b, and columns indexed
-- by the elements not in b. The bi, ej entry is 1 if bi is in the
-- fundamental circuit of ej relative to b, and 0 otherwise.
fundamentalCircuitIncidenceMatrix :: (Ord a, Num k) => Matroid a -> [a] -> [[k]]
fundamentalCircuitIncidenceMatrix' :: (Ord a, Num t) => Matroid a -> [a] -> [[t]]
fcim :: (Ord a, Num k) => Matroid a -> [a] -> [[k]]
fcim' :: (Ord a, Num t) => Matroid a -> [a] -> [[t]]
markNonInitialRCs :: (Num a, Eq a) => [[a]] -> [[ZeroOneStar]]
substStars :: Num a => [[ZeroOneStar]] -> [a] -> [[[a]]]
starSubstitutionsV :: Num a => [a] -> [ZeroOneStar] -> [[a]]
representations1 :: (Ord a1, Ord a, Fractional a1) => [a1] -> Matroid a -> [[[a1]]]
fcig :: Ord t => Matroid t -> [t] -> [[t]]
markedfcim :: Ord a => Matroid a -> [a] -> [[ZeroOneStar]]
representations2 :: (Ord a1, Ord a, Fractional a1) => [a1] -> Matroid a -> [[[a1]]]
-- | Find representations of the matroid m over fq. Specifically, this
-- function will find one representative of each projective equivalence
-- class of representation.
representations :: (Eq fq, Fractional fq, Ord a) => [fq] -> Matroid a -> [[[fq]]]
-- | Is the matroid representable over Fq? For example, to find out whether
-- a matroid m is binary, evaluate isRepresentable f2 m.
isRepresentable :: (Eq fq, Fractional fq, Ord a) => [fq] -> Matroid a -> Bool
-- | A binary matroid is a matroid which is representable over F2
isBinary :: Ord a => Matroid a -> Bool
-- | A ternary matroid is a matroid which is representable over F3
isTernary :: Ord a => Matroid a -> Bool
data LMR a b
L :: a -> LMR a b
Mid :: LMR a b
R :: b -> LMR a b
seriesConnection :: (Ord a1, Ord a) => (Matroid a, a) -> (Matroid a1, a1) -> Matroid (LMR a a1)
parallelConnection :: (Ord a1, Ord a) => (Matroid a, a) -> (Matroid a1, a1) -> Matroid (LMR a a1)
twoSum :: (Ord a1, Ord a) => (Matroid a, a) -> (Matroid a1, a1) -> Matroid (LMR a a1)
matroidUnion :: Ord a => Matroid a -> Matroid a -> Matroid a
-- | The Fano plane F7 = PG(2,F2)
f7 :: Matroid Int
-- | F7-, the relaxation of the Fano plane by removal of a line
f7m :: Matroid Int
-- | The Pappus configuration from projective geometry
pappus :: Matroid Int
-- | Relaxation of the Pappus configuration by removal of a line
nonPappus :: Matroid Int
-- | The Desargues configuration
desargues :: Matroid Int
vamosMatroid1 :: (Ord a, Num a, Enum a) => Matroid a
vamosMatroid :: (Ord a, Num a) => Matroid a
-- | The Vamos matroid V8. It is not representable over any field.
v8 :: Matroid Int
-- | P8 is a minor-minimal matroid that is not representable over F4, F8,
-- F16, ... . It is Fq-representable if and only if q is not a power of
-- 2.
p8 :: Matroid Int
p8' :: (Ord a, Num a) => Matroid a
-- | P8- is a relaxation of P8. It is Fq-representable if and only if q
-- >= 4.
p8m :: Matroid Int
-- | P8-- is a relaxation of P8-. It is a minor-minimal matroid that is not
-- representable over F4. It is Fq-representable if and only if q >=
-- 5.
p8mm :: Matroid Int
wheelGraph :: (Num a, Enum a) => a -> Graph a
mw4 :: Matroid Int
w4' :: Matroid Int
w4 :: (Ord a, Num a) => Matroid a
isBinary2 :: Ord a => Matroid a -> Bool
x :: GlexPoly Integer String
rankPoly1 :: Ord a => Matroid a -> GlexPoly Integer String
-- | Given a matroid m over elements es, the rank polynomial is a
-- polynomial r(x,y), which is essentially a generating function for the
-- subsets of es, enumerated by size and rank. It is efficiently
-- calculated using deletion and contraction.
--
-- It has the property that r(0,0) is the number of bases in m, r(1,0) is
-- the number of independent sets, r(0,1) is the number of spanning sets.
-- It can also be used to derive the chromatic polynomial of a graph, the
-- weight enumerator of a linear code, and more.
rankPoly :: Ord a => Matroid a -> GlexPoly Integer String
numBases :: Ord a => Matroid a -> Integer
numIndeps :: Ord a => Matroid a -> Integer
numSpanning :: Ord a => Matroid a -> Integer
indepCounts :: Ord a => Matroid a -> [Int]
whitney2nd :: Ord a => Matroid a -> [Int]
whitney1st :: Ord a => Matroid a -> [Int]
instance Eq a => Eq (TrieSet a)
instance Ord a => Ord (TrieSet a)
instance Functor TrieSet
instance Eq a => Eq (Matroid a)
instance Show a => Show (Matroid a)
instance Functor Matroid
instance (Eq a, Eq b) => Eq (LMR a b)
instance (Ord a, Ord b) => Ord (LMR a b)
instance (Show a, Show b) => Show (LMR a b)
instance Show a => Show (TrieSet a)
-- | A module for arithmetic in quadratic number fields. A quadratic number
-- field is a field of the form Q(sqrt d), where d is a square-free
-- integer. For example, we can perform the following calculation in
-- Q(sqrt 2):
--
--
-- (1 + sqrt 2) / (2 + sqrt 2)
--
--
-- It is also possible to mix different square roots in the same
-- calculation. For example:
--
--
-- (1 + sqrt 2) * (1 + sqrt 3)
--
--
-- Square roots of negative numbers are also permitted. For example:
--
--
-- i * sqrt(-3)
--
module Math.NumberTheory.QuadraticField
-- | A basis for quadratic number fields Q(sqrt d), where d is a
-- square-free integer.
data QNFBasis
One :: QNFBasis
Sqrt :: Integer -> QNFBasis
-- | The type for elements of quadratic number fields
type QNF = Vect Q QNFBasis
-- | Although this has the same name as the Prelude.sqrt function, it
-- should be thought of as more like a constructor for creating elements
-- of quadratic fields.
--
-- Note that for d positive, sqrt d means the positive square root, and
-- sqrt (-d) should be interpreted as the square root with positive
-- imaginary part, that is i * sqrt d. This has the consequence that for
-- example, sqrt (-2) * sqrt (-3) = - sqrt 6.
sqrt :: Integer -> QNF
sqrt2 :: QNF
sqrt3 :: QNF
sqrt5 :: QNF
sqrt6 :: QNF
sqrt7 :: QNF
i :: QNF
newtype XVar
X :: Int -> XVar
instance [overlap ok] Eq QNFBasis
instance [overlap ok] Ord QNFBasis
instance [overlap ok] Eq XVar
instance [overlap ok] Ord XVar
instance [overlap ok] Show XVar
instance [overlap ok] Fractional QNF
instance [overlap ok] (Eq k, Num k) => Algebra k QNFBasis
instance [overlap ok] Show QNFBasis
module Math.Projects.RootSystem
data Type
A :: Type
B :: Type
C :: Type
D :: Type
E :: Type
F :: Type
G :: Type
basisElt :: Int -> Int -> [Q]
simpleSystem :: Type -> Int -> [[Q]]
w :: Fractional a => [a] -> [a] -> [a]
closure :: (Ord a, Fractional a) => [[a]] -> [[a]]
weylPerms :: Type -> Int -> [Permutation [Q]]
weylMatrices :: Type -> Int -> [[[Q]]]
wMx :: [Q] -> [[Q]]
cartanMatrix :: Type -> Int -> [[Q]]
setDiag :: a -> [[a]] -> [[a]]
dynkinFromCartan :: Num a => [[a]] -> [[a]]
dynkinDiagram :: Type -> Int -> [[Q]]
coxeterFromDynkin :: (Num a1, Num a, Eq a1) => [[a1]] -> [[a]]
coxeterMatrix :: Num a => Type -> Int -> [[a]]
fromCoxeterMatrix :: [[Int]] -> ([SGen], [([SGen], [t])])
fromCoxeterMatrix2 :: [[Int]] -> ([SGen], [([SGen], [SGen])])
coxeterPresentation :: Type -> Int -> ([SGen], [([SGen], [t])])
eltsCoxeter :: Type -> Int -> [[SGen]]
poincarePoly :: Type -> Int -> [Int]
elemMx :: Int -> Int -> Int -> [[Q]]
lieMult :: Num a => a -> a -> a
(+|+) :: [[a]] -> [[a]] -> [[a]]
(+-+) :: [a] -> [a] -> [a]
form :: Num a => Type -> Int -> [[a]]
rootSystem :: Type -> Int -> [[Q]]
numRoots :: (Num a, Eq a) => Type -> a -> a
orderWeyl :: Integral a => Type -> a -> Integer
factorial :: Integral a => a -> Integer
module Math.Projects.ChevalleyGroup.Classical
numPtsAG :: (Num a, Integral b) => b -> a -> a
numPtsPG :: (Integral b, Integral a) => b -> a -> a
-- | The special linear group SL(n,Fq), generated by elementary
-- transvections, returned as matrices
sl :: FiniteField k => Int -> [k] -> [[[k]]]
elemTransvection :: (Num t1, Num t, Eq t1, Enum t1) => t1 -> (t1, t1) -> t -> [[t]]
-- | The projective special linear group PSL(n,Fq) == A(n,Fq) ==
-- SL(n,Fq)/Z, returned as permutations of the points of PG(n-1,Fq). This
-- is a finite simple group provided n>2 or q>3.
l :: (FiniteField k, Ord k) => Int -> [k] -> [Permutation [k]]
orderL :: Integral a => a -> a -> a
-- | The symplectic group Sp(2n,Fq), returned as matrices
sp2 :: FiniteField k => Int -> [k] -> [[[k]]]
-- | The projective symplectic group PSp(2n,Fq) == Cn(Fq) == Sp(2n,Fq)/Z,
-- returned as permutations of the points of PG(2n-1,Fq). This is a
-- finite simple group for n>1, except for PSp(4,F2).
s2 :: (FiniteField k, Ord k) => Int -> [k] -> [Permutation [k]]
s :: (FiniteField k, Ord k) => Int -> [k] -> [Permutation [k]]
orderS2 :: (Integral b, Integral a) => b -> a -> a
orderS :: (Integral b, Integral a) => b -> a -> a
omegaeven :: FiniteField t1 => Int -> t -> [[[t1]]]
d :: (FiniteField a, Ord a) => Int -> [a] -> [Permutation [a]]
omegaodd :: FiniteField t => Int -> [a] -> [[[t]]]
b :: (FiniteField a, Ord a) => Int -> [a] -> [Permutation [a]]
o :: (FiniteField a, Ord a) => Int -> [a] -> [Permutation [a]]
module Math.Projects.MiniquaternionGeometry
data F9
F9 :: F3 -> F3 -> F9
e :: F9
f9 :: [F9]
w :: F9
conj :: F9 -> F9
norm :: F9 -> F3
data J9
J9 :: F9 -> J9
squaresF9 :: [F9]
i :: J9
j :: J9
k :: J9
j9 :: [J9]
autJ9 :: J9 -> Permutation J9
autA :: Permutation J9
autB :: Permutation J9
autC :: Permutation J9
autsJ9 :: [Permutation J9]
conj' :: J9 -> J9
isAut :: (Num a, Num t, Eq a) => [t] -> (t -> a) -> Bool
isReal :: (Num a, Eq a) => a -> Bool
isComplex :: J9 -> Bool
ptsPG2 :: Num t => [t] -> [[t]]
orthogonalLinesPG2 :: (Ord a, Num a) => [[a]] -> [[[a]]]
rightLinesPG2 :: Num t => [t] -> [[[t]]]
leftLinesPG2 :: Num t => [t] -> [[[t]]]
phi :: Design [F9]
phi' :: Design [F9]
collineationsPhi :: [Permutation [F9]]
liftToGraph :: Ord a => Design a -> Permutation a -> Permutation (Either a [a])
omega0 :: Design [J9]
omega :: Design [J9]
omega2 :: Design [J9]
collineationsOmega :: [Permutation [J9]]
omegaD :: Design [J9]
omegaD1 :: Design Integer
omegaD2 :: Design [J9]
(<*) :: Num b => [b] -> b -> [b]
psi :: Design [J9]
psi2 :: Design [J9]
collineationsPsi :: [Permutation [J9]]
order :: Design a -> Int
isProjectivePlane :: Eq a => Design a -> Bool
collinear :: Eq a => Design a -> [a] -> Bool
isQuadrangle :: Eq a => Design a -> [a] -> Bool
concurrent :: Eq a => Design a -> [[a]] -> Bool
isQuadrilateral :: Eq a => Design a -> [[a]] -> Bool
isOval :: Eq a => Design a -> [a] -> Bool
findOvals1 :: Eq a => Design a -> [[a]]
findQuadrangles :: Eq a => Design a -> [[a]]
findOvals :: Ord a => Design a -> [[a]]
instance Eq F9
instance Ord F9
instance Eq J9
instance Ord J9
instance FiniteField J9
instance Fractional J9
instance Num J9
instance Show J9
instance FiniteField F9
instance Fractional F9
instance Num F9
instance Show F9
module Math.Projects.ChevalleyGroup.Exceptional
newtype Octonion k
O :: [(Int, k)] -> Octonion k
i0 :: Octonion Q
i6 :: Octonion Q
i5 :: Octonion Q
i4 :: Octonion Q
i3 :: Octonion Q
i2 :: Octonion Q
i1 :: Octonion Q
fromList :: (Num k, Eq k) => [k] -> Octonion k
toList :: Num a => Octonion a -> [a]
expose :: Octonion t -> [(Int, t)]
nf :: (Ord t1, Ord t, Num t1) => [(t, t1)] -> [(t, t1)]
m :: (Num t, Integral a) => (a, t) -> (a, t) -> (a, t)
conj :: Num k => Octonion k -> Octonion k
sqnorm :: Num a => Octonion a -> a
isOrthogonal :: (Num a, Eq a) => Octonion a -> Octonion a -> Bool
antiCommutes :: (Num a, Eq a) => a -> a -> Bool
octonions :: (Num k, Eq k) => [k] -> [Octonion k]
isUnit :: (Num a, Eq a) => Octonion a -> Bool
unitImagOctonions :: (Num a, Eq a) => [a] -> [Octonion a]
autFrom :: (Ord t, Num t) => Octonion t -> Octonion t -> Octonion t -> [[t]]
(%^) :: (Num k, Eq k) => Octonion k -> [[k]] -> Octonion k
alpha3 :: [[F3]]
beta3 :: [[F3]]
gamma3s :: [Octonion F3]
gamma3 :: [[F3]]
alpha3' :: Permutation (Octonion F3)
beta3' :: Permutation (Octonion F3)
gamma3' :: Permutation (Octonion F3)
-- | Generators for G2(3), a finite simple group of order 4245696, as a
-- permutation group on the 702 unit imaginary octonions over F3
g2_3 :: [Permutation (Octonion F3)]
alpha4 :: [[F4]]
beta4 :: [[F4]]
gamma4s :: [Octonion F4]
gamma4 :: [[F4]]
alpha4' :: Permutation (Octonion F4)
beta4' :: Permutation (Octonion F4)
gamma4' :: Permutation (Octonion F4)
instance Eq k => Eq (Octonion k)
instance Ord k => Ord (Octonion k)
instance (Ord k, Num k, Fractional k) => Fractional (Octonion k)
instance (Ord k, Num k) => Num (Octonion k)
instance Show k => Show (Octonion k)