-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Groebner basis computation for Operads.
--
-- This is an implementation of the operadic Buchberger algorithm from
-- Vladimir Dotsenko & Anton Khoroshkin: Groebner bases for operads
-- (arXiv:0812.4069).
--
-- In writing this package, invaluable help has been given by Vladimir
-- Dotsenko and Eric Hoffbeck.
--
-- The user is recommended to run this from within the GHC interpreter
-- for exploration, and to write small Haskell scripts for batch
-- processing. We hope herewithin to give enough of an overview of the
-- available functionality to help the user figure out how to use the
-- software package.
--
-- A declaration of a new variable is done in a Haskell script by a
-- statement on the form
--
--
-- var = value
--
--
-- and in the interpreter by a statement on the form
--
--
-- let var = value
--
--
-- Using these, the following instructions should help get you started. I
-- will be writing the instructions aiming for use in the interpreter,
-- for quick starts.
--
-- It is possible to force types by following a declaration by :: and the
-- type signature you'll which. This enables you, for instance, to pick a
-- ground ring without having to set coefficients explicitly - see the
-- examples below.
--
-- Note that the Buchberger algorithm in its current shape expects at
-- least a division ring as scalar ring.
--
-- The expected workflow for a normal user is as follows.
--
--
-- - write the generators of the operadic ideal using corolla
-- and leaf to construct buildingblocks and nsCompose,
-- shuffleCompose and symmetricCompose to assemble them
-- into trees. The trees, subsequently, may be assembled into tree
-- polynomials by
--
--
--
-- - picking an ordering. The orderings available are PathPerm,
-- RPathPerm, PathRPerm, RPathRPerm,
-- PermPath, RPermPath, PermRPath and
-- RPermRPath, distinguished by reversal of order for either the
-- path comparison or the permutation comparison, as well as by whether
-- path or permutation comparison takes precedence.
-- - assembling trees and coefficients into an element of the free
-- operad, using + for addition of operadic elements and
-- .*. for scalar multiplication.
--
--
-- Useful functions for doing this includes, furthermore:
--
--
-- - oet takes a tree and an ordering and gives
-- an operad element. You will have to specify the relevant type for this
-- to work -- but we provide the extra type FreeOperad that only
-- asks for a LabelType to cover most common uses:
--
--
--
-- oet tree :: OperadElement LabelType ScalarType TreeOrdering
--
--
--
-- - oek takes a tree, an ordering and a
-- coefficient and gives an operad element
--
--
--
-- oek tree PathPerm (3::Rational)
--
--
-- Example:
--
--
-- let t1 = nsCompose 1 (corolla a [2,1]) (corolla b [1,2])
--
-- let b = corolla l [1,2]
--
-- let lb1 = shuffleCompose 1 [1,2,3] b b
--
-- let lb2 = shuffleCompose 1 [1,3,2] b b
--
-- let lb3 = shuffleCompose 2 [1,2,3] b b
--
-- let lo1 = oet lb1 :: FreeOperad Char
--
-- let lo2 = oet lb2 :: FreeOperad Char
--
-- let lo3 = oet lb3 :: FreeOperad Char
--
--
-- Note that while the Haskell compiler in general is very skilled at
-- guessing types of objects, the system guessing will give up if the
-- type is not well defined. There are several different monomial orders
-- allowed, and they are encoded in the type system -- hence the need to
-- annotate the instantiation of elements in the free operad with
-- appropriate types.
--
--
-- - assemble all generators into a list. Lists are formed by enclosing
-- the elements, separated by commas, in square brackets. Lists must have
-- identical type on all its elements - hence, for instance, you cannot
-- have operadic elements with different monomial orderings in the same
-- list.
--
--
-- Example:
--
--
-- let lgb = [lo1 - lo2 - lo3, 2.*.lo1 + 3.*. lo3]
--
--
--
-- - run the algorithm on your basis and wait for it to finish. The
-- entry point to the Buchberger algorithm is, not surprisingly,
-- operadicBuchberger.
--
--
-- Example:
--
--
-- let grobner = operadicBuchberger lgb
--
--
-- The output of operadicBuchberger, if it finishes, is a finite
-- Gröbner basis for the ideal spanned by the original generators. If
-- this is quadratic then the operad presented by this ideal is Koszul -
-- this may be tested with something like:
--
--
-- all (==2) $ concatMap operationDegrees grobner
--
--
-- If you wish to inspect elements yourself, the recommended way to do it
-- is by using the pP function, which outputs most of the
-- interesting elements in a human-readable format. For objects that
-- don't work with pP, just writing the variable name on its own will
-- print it in some format.
--
-- The difference here is related to the ability to save computational
-- states to disk. There are two different functions that will represent
-- a tree or an element of an operad as a String: show and
-- pp. Using the former guarantees (with the same version of the
-- source code) that the data can be read back into the system and reused
-- later one; whereas using pp will build a human readable string.
@package Operads
@version 1.0
module Math.Operad
-- | This yields user interface functions for human readable printing of
-- objects. The idea is to use Show instances for marshalling of
-- data, and PPrint for user interaction.
class PPrint a
pp :: (PPrint a) => a -> String
pP :: (PPrint a) => a -> IO ()
type MonomialMap a t n = Map a t n
-- | The type carrying operadic elements. An element in an operad is an
-- associative array with keys being labeled trees and values being their
-- coefficients.
newtype (Ord a, Show a, TreeOrdering t) => OperadElement a n t
OE :: (MonomialMap a t n) -> OperadElement a n t
-- | Extracting the internal structure of the an element of the free
-- operad.
extractMap :: (Ord a, Show a, TreeOrdering t) => OperadElement a n t -> MonomialMap a t n
-- | Scalar multiplication in the operad.
(.*.) :: (Ord a, Show a, Eq n, Show n, Num n, TreeOrdering t) => n -> OperadElement a n t -> OperadElement a n t
-- | Apply a function to each monomial tree in the operad element.
mapMonomials :: (Show a, Ord a, Show b, Ord b, Num n, TreeOrdering s, TreeOrdering t) => (OrderedTree a s -> OrderedTree b t) -> OperadElement a n s -> OperadElement b n t
-- | Fold a function over all monomial trees in an operad element,
-- collating the results in a list.
foldMonomials :: (Show a, Ord a, Num n, TreeOrdering t) => ((OrderedTree a t, n) -> [b] -> [b]) -> OperadElement a n t -> [b]
-- | Given a list of (tree,coefficient)-pairs, reconstruct the
-- corresponding operad element.
fromList :: (TreeOrdering t, Show a, Ord a, Num n) => [(OrderedTree a t, n)] -> OperadElement a n t
-- | Given an operad element, extract a list of (tree, coefficient) pairs.
toList :: (TreeOrdering t, Show a, Ord a) => OperadElement a n t -> [(OrderedTree a t, n)]
-- | Construct an element in the free operad from its internal structure.
-- Use this instead of the constructor.
oe :: (Ord a, Show a, TreeOrdering t, Num n) => [(OrderedTree a t, n)] -> OperadElement a n t
-- | Construct a monomial in the free operad from a tree and a tree
-- ordering. It's coefficient will be 1.
oet :: (Ord a, Show a, TreeOrdering t, Num n) => DecoratedTree a -> OperadElement a n t
-- | Construct a monomial in the free operad from a tree, a tree ordering
-- and a coefficient.
oek :: (Ord a, Show a, TreeOrdering t, Num n) => DecoratedTree a -> n -> OperadElement a n t
-- | Return the zero of the corresponding operad, with type appropriate to
-- the given element. Can be given an appropriately casted undefined to
-- construct a zero.
zero :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t
-- | Check whether an element is equal to 0.
isZero :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Bool
-- | Extract the leading term of an operad element as an operad element.
leadingOTerm :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> OperadElement a n t
-- | Extract the leading term of an operad element.
leadingTerm :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> (OrderedTree a t, n)
-- | Extract the ordered tree for the leading term of an operad element.
leadingOMonomial :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> OrderedTree a t
-- | Extract the tree for the leading term of an operad element.
leadingMonomial :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> DecoratedTree a
-- | Extract the leading coefficient of an operad element.
leadingCoefficient :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> n
-- | Extract all occurring monomial trees from an operad element.
getTrees :: (TreeOrdering t, Show a, Ord a) => OperadElement a n t -> [OrderedTree a t]
-- | The fundamental tree data type used. Leaves carry labels - most often
-- integral - and these are expected to control, e.g., composition points
-- in shuffle operad compositions. The vertices carry labels, used for
-- the ordering on trees and to distinguish different basis corollas of
-- the same arity.
data (Ord a, Show a) => PreDecoratedTree a b
DTLeaf :: !b -> PreDecoratedTree a b
DTVertex :: !a -> ![PreDecoratedTree a b] -> PreDecoratedTree a b
vertexType :: PreDecoratedTree a b -> !a
subTrees :: PreDecoratedTree a b -> ![PreDecoratedTree a b]
-- | The arity of a corolla
vertexArity :: (Ord a, Show a) => PreDecoratedTree a b -> Int
-- | Apply a function f to all the internal vertex labels of a
-- PreDecoratedTree.
vertexMap :: (Ord a, Show a, Ord b, Show b) => (a -> b) -> PreDecoratedTree a c -> PreDecoratedTree b c
-- | If a tree has trees as labels for its leaves, we can replace the
-- leaves with the roots of those label trees. Thus we may glue together
-- trees, as required by the compositions.
glueTrees :: (Ord a, Show a) => PreDecoratedTree a (PreDecoratedTree a b) -> PreDecoratedTree a b
-- | This is the fundamental datatype of the whole project. Monomials in a
-- free operad are decorated trees, and we build a type for decorated
-- trees here. We require our trees to have Int labels, limiting us to at
-- most 2 147 483 647 leaf labels.
type DecoratedTree a = PreDecoratedTree a Int
-- | Monomial orderings on the free operad requires us to choose an
-- ordering for the trees. These are parametrized by types implementing
-- the type class TreeOrdering, and this is a data type for a tree
-- carrying its comparison type. We call these ordered trees.
data (Ord a, Show a, TreeOrdering t) => OrderedTree a t
OT :: (DecoratedTree a) -> t -> OrderedTree a t
-- | Building an ordered tree with PathLex ordering from a
-- decorated tree.
ot :: (Ord a, Show a, TreeOrdering t) => DecoratedTree a -> OrderedTree a t
-- | Extracting the underlying tree from an ordered tree.
dt :: (Ord a, Show a, TreeOrdering t) => OrderedTree a t -> DecoratedTree a
-- | The type class that parametrizes types implementing tree orderings.
class (Eq t, Show t) => TreeOrdering t
treeCompare :: (TreeOrdering t, Ord a, Show a) => t -> DecoratedTree a -> DecoratedTree a -> Ordering
comparePathSequence :: (TreeOrdering t, Ord a, Show a) => t -> DecoratedTree a -> ([[a]], Shuffle) -> DecoratedTree a -> ([[a]], Shuffle) -> Ordering
ordering :: (TreeOrdering t) => t
-- | Finding the path sequences. cf. Dotsenko-Khoroshkin.
pathSequence :: (Ord a, Show a) => DecoratedTree a -> ([[a]], Shuffle)
-- | Reordering the path sequences to mirror the actual leaf ordering.
orderedPathSequence :: (Ord a, Show a) => DecoratedTree a -> ([[a]], Shuffle)
-- | Changes direction of an ordering.
reverseOrder :: Ordering -> Ordering
-- | Using the path sequence, the leaf orders and order reversal, we can
-- get 8 different orderings from one paradigm. These are given by
-- PathPerm, RPathPerm, PathRPerm, RPathRPerm
-- for the variations giving (possibly reversed) path sequence comparison
-- precedence over (possibly reversed) leaf permutations; additionally,
-- there are PermPath, RPermPath, PermRPath and
-- RPermRPath for the variations with the opposite precedence.
data PathPerm
PathPerm :: PathPerm
data RPathPerm
RPathPerm :: RPathPerm
data PathRPerm
PathRPerm :: PathRPerm
data RPathRPerm
RPathRPerm :: RPathRPerm
data PermPath
PermPath :: PermPath
data PermRPath
PermRPath :: PermRPath
data RPermPath
RPermPath :: RPermPath
data RPermRPath
RPermRPath :: RPermRPath
-- | Build a single corolla in a decorated tree. Takes a list for labels
-- for the leaves, and derives the arity of the corolla from those. This,
-- and the composition functions, form the preferred method to construct
-- trees.
corolla :: (Ord a, Show a) => a -> [Int] -> DecoratedTree a
-- | Build a single leaf.
leaf :: (Ord a, Show a) => Int -> DecoratedTree a
-- | Check whether a given root is a leaf.
isLeaf :: (Ord a, Show a) => DecoratedTree a -> Bool
-- | Check whether a given root is a corolla.
isCorolla :: (Ord a, Show a) => DecoratedTree a -> Bool
-- | Change the leaves of a tree to take their values from a given list.
relabelLeaves :: (Ord a, Show a) => DecoratedTree a -> [b] -> PreDecoratedTree a b
-- | Find the permutation the leaf labeling ordains for inputs.
leafOrder :: (Ord a, Show a) => DecoratedTree a -> [Int]
-- | Find the minimal leaf covering any given vertex.
minimalLeaf :: (Ord a, Show a, Ord b) => PreDecoratedTree a b -> b
-- | Compute the number of leaves of the entire tree covering a given
-- vertex.
nLeaves :: (Ord a, Show a) => DecoratedTree a -> Int
-- | arityDegree is one less than nLeaves.
arityDegree :: (Ord a, Show a) => DecoratedTree a -> Int
-- | A shuffle is a special kind of sequence of integers.
type Shuffle = [Int]
-- | We need to recognize sorted sequences of integers.
isSorted :: (Ord a, Show a) => [a] -> Bool
-- | This tests whether a given sequence of integers really is a shuffle.
isShuffle :: Shuffle -> Bool
-- | This tests whether a given sequence of integers is an (i,j)-shuffle
isShuffleIJ :: Shuffle -> Int -> Int -> Bool
-- | This tests whether a given sequence of integers is admissible for a
-- specific composition operation.
isShuffleIPQ :: Shuffle -> Int -> Int -> Bool
-- | This applies the resulting permutation from a shuffle to a set of
-- elements
applyPerm :: (Show a) => Shuffle -> [a] -> [a]
-- | Apply the permutation inversely to applyPerm.
invApplyPerm :: Shuffle -> [a] -> [a]
-- | Generate all subsets of length k from a given list.
kSubsets :: Int -> [Int] -> [[Int]]
-- | Applies f only at the nth place in a list.
applyAt :: (a -> a) -> Int -> [a] -> [a]
-- | Picks out the last nonzero entry in a list.
lastNonzero :: (Num a) => [a] -> Int
-- | Generates shuffle permutations by filling buckets.
allShPerm :: Int -> [Int] -> [[[Int]]]
-- | Generates all shuffles from Sh_i(p,q).
allShuffles :: Int -> Int -> Int -> [Shuffle]
-- | The number of internal vertices of a tree.
operationDegree :: (Ord a, Show a) => DecoratedTree a -> Int
-- | A list of operation degrees occurring in the terms of the operad
-- element
operationDegrees :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> [Int]
-- | The maximal operation degree of an operadic element
maxOperationDegree :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Int
-- | Check that an element of a free operad is homogenous
isHomogenous :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Bool
-- | Composition in the shuffle operad
shuffleCompose :: (Ord a, Show a) => Int -> Shuffle -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a
-- | Composition in the non-symmetric operad. We compose s o_i t.
nsCompose :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a
-- | Composition in the symmetric operad
symmetricCompose :: (Ord a, Show a) => Int -> Shuffle -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a
-- | Non-symmetric composition in the g(s;t1,...,tk) style.
nsComposeAll :: (Ord a, Show a) => DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a
-- | Verification for a shuffle used for the g(s;t1,..,tk) style
-- composition in the shuffle operad.
checkShuffleAll :: Shuffle -> [Int] -> Bool
-- | Sanity check for permutations.
isPermutation :: Shuffle -> Bool
-- | Shuffle composition in the g(s;t1,...,tk) style.
shuffleComposeAll :: (Ord a, Show a) => Shuffle -> DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a
-- | Symmetric composition in the g(s;t1,...,tk) style.
symmetricComposeAll :: (Ord a, Show a) => Shuffle -> DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a
-- | Data type to move the results of finding an embedding point for a
-- subtree in a larger tree around. The tree is guaranteed to have
-- exactly one corolla tagged Nothing, the subtrees on top of that
-- corolla sorted by minimal covering leaf in the original setting, and
-- the shuffle carried around is guaranteed to restore the original leaf
-- labels before the search.
type Embedding a = DecoratedTree (Maybe a)
-- | Returns True if there is a subtree of t isomorphic to
-- s, respecting leaf orders.
divides :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Bool
-- | Returns True if there is a subtree of t isomorphic to
-- s, respecting leaf orders, and not located at the root.
dividesHigh :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Bool
-- | Returns True if there is a rooted subtree of t isomorphic to
-- s, respecting leaf orders.
dividesRooted :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Bool
-- | Finds all ways to embed s into t respecting leaf orders.
findAllEmbeddings :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [Embedding a]
-- | Helper function for findRootedEmbedding.
findUnsortedRootedEmbedding :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Maybe (Embedding a)
-- | Finds all ways to embed s into t, respecting leaf orders and mapping
-- the root of s to the root of t.
findRootedEmbedding :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Maybe (Embedding a)
-- | Checks a tree for planarity.
planarTree :: (Ord a, Show a) => DecoratedTree a -> Bool
-- | Returns True if s and t divide u, with different embeddings and t
-- sharing root with u.
dividesDifferent :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> DecoratedTree a -> Bool
-- | Interchanges Left to Right and Right to
-- Left for types Either a a
flipEither :: Either a a -> Either a a
-- | Projects the type Either a a onto the type a in the
-- obvious manner.
stripEither :: Either a a -> a
-- | Applies flipEither to the root vertex label of a tree.
flipEitherRoot :: (Ord a, Show a) => PreDecoratedTree (Either a a) b -> PreDecoratedTree (Either a a) b
-- | Projects vertex labels and applies leaf labels to a tree with internal
-- labeling in Either a a.
fuseTree :: (Ord a, Show a) => DecoratedTree (Either a a) -> [Int] -> DecoratedTree (Either a a)
-- | Strips the Either layer from internal vertex labels
stripTree :: (Ord a, Show a) => DecoratedTree (Either a a) -> DecoratedTree a
-- | Acquires lists for resorting leaf labels according to the algorithm
-- found for constructing small common multiples with minimal work.
leafOrders :: (Ord a, Show a, Ord b, Show b) => DecoratedTree a -> DecoratedTree b -> [(Int, Int)]
-- | Locates the first vertex tagged with a Right constructor in a
-- tree labeled with Either a b.
findFirstRight :: (Ord a, Show a, Ord b, Show b) => DecoratedTree (Either a b) -> Maybe (DecoratedTree (Either a b))
-- | Equivalent to listToMaybe . reverse
maybeLast :: [a] -> Maybe a
-- | Recursive algorithm to figure out correct leaf labels for a
-- reconstructed small common multiple of two trees.
leafLabels :: (Ord a, Show a) => DecoratedTree a -> [Int] -> [Int] -> [[Int]]
-- | Finds rooted small common multiples of two trees.
findRootedSCM :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Maybe (DecoratedTree a)
-- | Finds structural small common multiples, disregarding leaf labels
-- completely.
findNonSymmetricSCM :: (Ord a, Show a) => Int -> DecoratedTree (Either a a) -> DecoratedTree (Either a a) -> [DecoratedTree (Either a a)]
-- | Finds small common multiples of two trees bounding internal operation
-- degree.
findBoundedSCM :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> [DecoratedTree (Either a a)]
-- | Finds all small common multiples of two trees.
findAllSCM :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [DecoratedTree (Either a a)]
-- | Finds all small common multiples of two trees, bounding the internal
-- operation degree.
findAllBoundedSCM :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> [DecoratedTree (Either a a)]
-- | Constructs embeddings for s and t in
-- SCM(s,t) and returns these.
scmToEmbedding :: (Ord a, Show a) => DecoratedTree (Either a a) -> DecoratedTree a -> DecoratedTree a -> (Embedding a, Embedding a)
-- | Relabels a tree in the right order, but with entries from [1..]
rePackLabels :: (Ord a, Show a, Ord b) => PreDecoratedTree a b -> DecoratedTree a
-- | Removes vertex type encapsulations.
fromJustTree :: (Ord a, Show a) => DecoratedTree (Maybe a) -> Maybe (DecoratedTree a)
-- | Adds vertex type encapsulations.
toJustTree :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree (Maybe a)
-- | Verifies that two integer sequences correspond to the same total
-- ordering of the entries.
equivalentOrders :: [Int] -> [Int] -> Bool
-- | Returns True if any of the vertices in the given tree has been tagged.
subTreeHasNothing :: (Ord a, Show a) => DecoratedTree (Maybe a) -> Bool
-- | The function that mimics resubstitution of a new tree into the hole
-- left by finding embedding, called m_alpha,beta in Dotsenko-Khoroshkin.
-- This version only attempts to resubstitute the tree at the root,
-- bailing out if not possible.
reconstructNode :: (Ord a, Show a) => DecoratedTree a -> Embedding a -> Maybe (DecoratedTree a)
-- | The function that mimics resubstitution of a new tree into the hole
-- left by finding embedding, called m_alpha,beta in Dotsenko-Khoroshkin.
-- This version recurses down in the tree in order to find exactly one
-- hole, and substitute the tree sub into it.
reconstructTree :: (Ord a, Show a) => DecoratedTree a -> Embedding a -> Maybe (DecoratedTree a)
-- | Applies the reconstruction map represented by em to all trees in the
-- operad element op. Any operad element that fails the reconstruction
-- (by having the wrong total arity, for instance) will be silently
-- dropped. We recommend you apply this function only to homogenous
-- operad elements, but will not make that check.
applyReconstruction :: (Ord a, Show a, TreeOrdering t, Num n) => Embedding a -> OperadElement a n t -> OperadElement a n t
-- | Finds all S polynomials for a given list of operad elements.
findAllSPolynomials :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
-- | Finds all S polynomials for which the operationdegree stays bounded.
findInitialSPolynomials :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
-- | Finds all S polynomials for a given pair of operad elements, keeping a
-- bound on operation degree.
findSPolynomials :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> OperadElement a n t -> OperadElement a n t -> [OperadElement a n t]
-- | Non-symmetric version of findInitialSPolynomials.
findNSInitialSPolynomials :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
-- | Non-symmetric version of findSPolynomials.
findNSSPolynomials :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> OperadElement a n t -> OperadElement a n t -> [OperadElement a n t]
-- | Reduce g with respect to f and the embedding em: lt f -> lt g.
reduceOE :: (Ord a, Show a, TreeOrdering t, Fractional n) => Embedding a -> OperadElement a n t -> OperadElement a n t -> OperadElement a n t
-- | Reduce the leading monomial of op with respect to
-- gb.
reduceInitial :: (Ord a, Show a, TreeOrdering t, Fractional n) => OperadElement a n t -> [OperadElement a n t] -> OperadElement a n t
-- | Reduce all terms of op with respect to gbn.
reduceCompletely :: (Ord a, Show a, TreeOrdering t, Fractional n) => OperadElement a n t -> [OperadElement a n t] -> OperadElement a n t
-- | Perform one iteration of the Buchberger algorithm: generate all
-- S-polynomials. Reduce all S-polynomials. Return anything that survived
-- the reduction.
stepOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
stepNSOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
-- | Perform one iteration of the Buchberger algorithm: generate all
-- S-polynomials. Reduce all S-polynomials. Return anything that survived
-- the reduction. Keep the occurring operation degrees bounded.
stepInitialOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
-- | Non-symmetric version of stepInitialOperadicBuchberger.
stepNSInitialOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
-- | Perform the entire Buchberger algorithm for a given list of
-- generators. Iteratively run the single iteration from
-- stepOperadicBuchberger until no new elements are generated.
--
-- DO NOTE: This is entirely possible to get stuck in an infinite loop.
-- It is not difficult to write down generators such that the resulting
-- Groebner basis is infinite. No checking is performed to catch this
-- kind of condition.
operadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t]
-- | Non-symmetric version of operadicBuchberger.
nsOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t]
-- | Perform the entire Buchberger algorithm for a given list of
-- generators. This iteratively runs single iterations from
-- stepOperadicBuchberger until no new elements are generated.
streamOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t]
-- | Non-symmetric version of streamOperadicBuchberger.
streamNSOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t]
-- | Reduces a list of elements with respect to all other elements
-- occurring in that same list.
reduceBasis :: (Fractional n, TreeOrdering t, Show a, Ord a) => [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
-- | All trees composed from the given generators of operation degree n.
allTrees :: (Ord a, Show a) => [DecoratedTree a] -> Int -> [DecoratedTree a]
-- | Generate basis trees for a given Groebner basis for degree
-- maxDegree. divisors is expected to contain the
-- leading monomials in the Groebner basis.
basisElements :: (Ord a, Show a) => [DecoratedTree a] -> [DecoratedTree a] -> Int -> [DecoratedTree a]
-- | Change the monomial order used for a specific tree. Use this in
-- conjunction with mapMonomials in order to change monomial order for an
-- entire operad element.
changeOrder :: (Ord a, Show a, TreeOrdering s, TreeOrdering t) => t -> OrderedTree a s -> OrderedTree a t
-- | The element m2(m2(1,2),3)
m12_3 :: DecoratedTree Integer
-- | The element m2(m2(1,3),2)
m13_2 :: DecoratedTree Integer
-- | The element m2(1,m2(2,3))
m1_23 :: DecoratedTree Integer
-- | The element m2(1,2)
m2 :: DecoratedTree Integer
-- | The element m3(1,2,3)
m3 :: DecoratedTree Integer
-- | The element m2(m2(1,2),m2(3,4))
yTree :: DecoratedTree Integer
-- | The list of operad elements consisting of 'm12_3'-'m13_2'-'m1_23'.
-- This generates the ideal of relations for the operad Lie.
lgb :: [OperadElement Integer Rational PathPerm]
type Tree = DecoratedTree Integer
type FreeOperad a = OperadElement a Rational PathPerm