Contents Pretty printing Handling polynomials in the free operad Decorated and ordered trees Monomial orderings on the free operad Utility functions on trees Shuffles Fundamental data types and instances Free operad Operadic compositions Divisibility among trees Groebner basis methods Low degree bases
Synopsis
class PPrint a where
 pp :: a -> String pP :: a -> IO ()
newtype (Ord a, Show a, TreeOrdering t) => OperadElement a n t = OE (Map a t n)
extractMap :: (Ord a, Show a, TreeOrdering t) => OperadElement a n t -> Map a t n
(.*.) :: (Ord a, Show a, Eq n, Show n, Num n, TreeOrdering t) => n -> OperadElement a n t -> OperadElement a n t
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
foldMonomials :: (Show a, Ord a, Num n, TreeOrdering t) => ((OrderedTree a t, n) -> [b] -> [b]) -> OperadElement a n t -> [b]
fromList :: (TreeOrdering t, Show a, Ord a, Num n) => [(OrderedTree a t, n)] -> OperadElement a n t
toList :: (TreeOrdering t, Show a, Ord a) => OperadElement a n t -> [(OrderedTree a t, n)]
oe :: (Ord a, Show a, TreeOrdering t, Num n) => [(OrderedTree a t, n)] -> OperadElement a n t
oet :: (Ord a, Show a, TreeOrdering t, Num n) => DecoratedTree a -> OperadElement a n t
oek :: (Ord a, Show a, TreeOrdering t, Num n) => DecoratedTree a -> n -> OperadElement a n t
zero :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t
isZero :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Bool
leadingTerm :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> (OrderedTree a t, n)
leadingOMonomial :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> OrderedTree a t
leadingMonomial :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> DecoratedTree a
leadingCoefficient :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> n
getTrees :: (TreeOrdering t, Show a, Ord a) => OperadElement a n t -> [OrderedTree a t]
data (Ord a, Show a) => PreDecoratedTree a b
= DTLeaf !b
| DTVertex {
 vertexType :: !a subTrees :: ![PreDecoratedTree a b]
}
vertexArity :: (Ord a, Show a) => PreDecoratedTree a b -> Int
glueTrees :: (Ord a, Show a) => PreDecoratedTree a (PreDecoratedTree a b) -> PreDecoratedTree a b
type DecoratedTree a = PreDecoratedTree a Int
data (Ord a, Show a, TreeOrdering t) => OrderedTree a t = OT (DecoratedTree a) t
ot :: (Ord a, Show a, TreeOrdering t) => DecoratedTree a -> OrderedTree a t
dt :: (Ord a, Show a, TreeOrdering t) => OrderedTree a t -> DecoratedTree a
class (Eq t, Show t) => TreeOrdering t where
 treeCompare :: (Ord a, Show a) => t -> DecoratedTree a -> DecoratedTree a -> Ordering comparePathSequence :: (Ord a, Show a) => t -> ([[a]], Shuffle) -> ([[a]], Shuffle) -> Ordering ordering :: t
pathSequence :: (Ord a, Show a) => DecoratedTree a -> ([[a]], Shuffle)
orderedPathSequence :: (Ord a, Show a) => DecoratedTree a -> ([[a]], Shuffle)
data RPathLex = RPathLex
reverseOrder :: Ordering -> Ordering
data PathLex = PathLex
data ForestLex = ForestLex
corolla :: (Ord a, Show a) => a -> [Int] -> DecoratedTree a
leaf :: (Ord a, Show a) => Int -> DecoratedTree a
isLeaf :: (Ord a, Show a) => DecoratedTree a -> Bool
isCorolla :: (Ord a, Show a) => DecoratedTree a -> Bool
relabelLeaves :: (Ord a, Show a) => DecoratedTree a -> [b] -> PreDecoratedTree a b
leafOrder :: (Ord a, Show a) => DecoratedTree a -> [Int]
minimalLeaf :: (Ord a, Show a, Ord b) => PreDecoratedTree a b -> b
nLeaves :: (Ord a, Show a) => DecoratedTree a -> Int
arityDegree :: (Ord a, Show a) => DecoratedTree a -> Int
type Shuffle = [Int]
isSorted :: (Ord a, Show a) => [a] -> Bool
isShuffle :: Shuffle -> Bool
isShuffleIJ :: Shuffle -> Int -> Int -> Bool
isShuffleIPQ :: Shuffle -> Int -> Int -> Bool
applyPerm :: Show a => Shuffle -> [a] -> [a]
invApplyPerm :: Shuffle -> [a] -> [a]
kSubsets :: Int -> [Int] -> [[Int]]
allShuffles :: Int -> Int -> Int -> [Shuffle]
operationDegree :: (Ord a, Show a) => DecoratedTree a -> Int
operationDegrees :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> [Int]
maxOperationDegree :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Int
isHomogenous :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Bool
shuffleCompose :: (Ord a, Show a) => Int -> Shuffle -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a
nsCompose :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a
symmetricCompose :: (Ord a, Show a) => Int -> Shuffle -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a
nsComposeAll :: (Ord a, Show a) => DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a
checkShuffleAll :: Shuffle -> [Int] -> Bool
isPermutation :: Shuffle -> Bool
shuffleComposeAll :: (Ord a, Show a) => Shuffle -> DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a
symmetricComposeAll :: (Ord a, Show a) => Shuffle -> DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a
type Embedding a = DecoratedTree (Maybe a)
divides :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Bool
findAllEmbeddings :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [Embedding a]
findRootedEmbedding :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Maybe (Embedding a)
findRootedDecoratedGCD :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Maybe (PreDecoratedTree a (DecoratedTree a, DecoratedTree a))
findRootedLCM :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [DecoratedTree a]
accumulateTrees :: (Ord a, Show a) => [(DecoratedTree a, DecoratedTree a)] -> [DecoratedTree a] -> [DecoratedTree a]
planarTree :: (Ord a, Show a) => DecoratedTree a -> Bool
findSmallBoundedLCM :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> [DecoratedTree a]
findAllLCM :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [DecoratedTree a]
findAllBoundedLCM :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> [DecoratedTree a]
rePackLabels :: (Ord a, Show a, Ord b) => PreDecoratedTree a b -> DecoratedTree a
fromJustTree :: (Ord a, Show a) => DecoratedTree (Maybe a) -> Maybe (DecoratedTree a)
toJustTree :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree (Maybe a)
equivalentOrders :: [Int] -> [Int] -> Bool
subTreeHasNothing :: (Ord a, Show a) => DecoratedTree (Maybe a) -> Bool
reconstructNode :: (Ord a, Show a) => DecoratedTree a -> Embedding a -> Maybe (DecoratedTree a)
reconstructTree :: (Ord a, Show a) => DecoratedTree a -> Embedding a -> Maybe (DecoratedTree a)
applyReconstruction :: (Ord a, Show a, TreeOrdering t, Num n) => Embedding a -> OperadElement a n t -> OperadElement a n t
findAllSPolynomials :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
findInitialSPolynomials :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
reduceOE :: (Ord a, Show a, TreeOrdering t, Fractional n) => Embedding a -> OperadElement a n t -> OperadElement a n t -> OperadElement a n t
reduceCompletely :: (Ord a, Show a, TreeOrdering t, Fractional n) => OperadElement a n t -> [OperadElement a n t] -> OperadElement a n t
stepOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
stepInitialOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]
operadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t]
initialOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t]
reduceBasis :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t]
allTrees :: (Ord a, Show a) => [DecoratedTree a] -> Int -> [DecoratedTree a]
basisElements :: (Ord a, Show a) => [DecoratedTree a] -> [DecoratedTree a] -> Int -> [DecoratedTree a]
basisElements' :: (Ord a, Show a) => [DecoratedTree a] -> [DecoratedTree a] -> Int -> [DecoratedTree a]
changeOrder :: (Ord a, Show a, TreeOrdering s, TreeOrdering t) => t -> OrderedTree a s -> OrderedTree a t
m12_3 :: DecoratedTree Integer
m13_2 :: DecoratedTree Integer
m1_23 :: DecoratedTree Integer
m2 :: DecoratedTree Integer
m3 :: DecoratedTree Integer
yTree :: DecoratedTree Integer
lgb :: [OperadElement Integer Rational PathLex]
type Tree = DecoratedTree Integer
Pretty printing
 class PPrint a where Source
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.
Methods
 pp :: a -> String Source
 pP :: a -> IO () Source
Instances
 PPrint a => PPrint ([] a) (PPrint a, PPrint b) => PPrint ((,) a b) (Ord a, Show a, TreeOrdering t) => PPrint (OrderedTree a t) (Ord a, Show a, Show b) => PPrint (PreDecoratedTree a b) (Ord a, Show a, Num n, TreeOrdering t) => PPrint (OperadElement a n t) (Ord a, Show a, Show n, TreeOrdering t) => PPrint (OperadElement a n t)
 newtype (Ord a, Show a, TreeOrdering t) => OperadElement a n t Source
The type carrying operadic elements. An element in an operad is an associative array with keys being labeled trees and values being their coefficients.
Constructors
 OE (Map a t n)
Instances
 (Eq n, Ord a, Show a, TreeOrdering t) => Eq (OperadElement a n t) (Ord a, Show a, Num n, TreeOrdering t) => Num (OperadElement a n t) (Ord a, Ord n, Show a, TreeOrdering t) => Ord (OperadElement a n t) (Ord a, Read a, Read n, Read t, Show a, TreeOrdering t) => Read (OperadElement a n t) (Ord a, Show a, Show n, TreeOrdering t) => Show (OperadElement a n t) (Ord a, Show a, Show n, TreeOrdering t) => PPrint (OperadElement a n t)
 extractMap :: (Ord a, Show a, TreeOrdering t) => OperadElement a n t -> Map a t n Source
Extracting the internal structure of the an element of the free operad.
 (.*.) :: (Ord a, Show a, Eq n, Show n, Num n, TreeOrdering t) => n -> OperadElement a n t -> OperadElement a n t Source
 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 Source
Apply a function to each monomial tree in the operad element.
 foldMonomials :: (Show a, Ord a, Num n, TreeOrdering t) => ((OrderedTree a t, n) -> [b] -> [b]) -> OperadElement a n t -> [b] Source
Fold a function over all monomial trees in an operad element, collating the results in a list.
 fromList :: (TreeOrdering t, Show a, Ord a, Num n) => [(OrderedTree a t, n)] -> OperadElement a n t Source
Given a list of (tree,coefficient)-pairs, reconstruct the corresponding operad element.
 toList :: (TreeOrdering t, Show a, Ord a) => OperadElement a n t -> [(OrderedTree a t, n)] Source
Given an operad element, extract a list of (tree, coefficient) pairs.
Handling polynomials in the free operad
 oe :: (Ord a, Show a, TreeOrdering t, Num n) => [(OrderedTree a t, n)] -> OperadElement a n t Source
Construct an element in the free operad from its internal structure. Use this instead of the constructor.
 oet :: (Ord a, Show a, TreeOrdering t, Num n) => DecoratedTree a -> OperadElement a n t Source
Construct a monomial in the free operad from a tree and a tree ordering. It's coefficient will be 1.
 oek :: (Ord a, Show a, TreeOrdering t, Num n) => DecoratedTree a -> n -> OperadElement a n t Source
Construct a monomial in the free operad from a tree, a tree ordering and a coefficient.
 zero :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t Source
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.
 isZero :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Bool Source
Check whether an element is equal to 0.
 leadingTerm :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> (OrderedTree a t, n) Source
 leadingOMonomial :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> OrderedTree a t Source
Extract the ordered tree for the leading term of an operad element.
 leadingMonomial :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> DecoratedTree a Source
 leadingCoefficient :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> n Source
 getTrees :: (TreeOrdering t, Show a, Ord a) => OperadElement a n t -> [OrderedTree a t] Source
Extract all occurring monomial trees from an operad element.
Decorated and ordered trees
 data (Ord a, Show a) => PreDecoratedTree a b Source
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.
Constructors
DTLeaf !b
DTVertex
 vertexType :: !a subTrees :: ![PreDecoratedTree a b]
Instances
 (Ord a, Show a) => Monad (PreDecoratedTree a) (Ord a, Show a) => Functor (PreDecoratedTree a) (Ord a, Show a) => Traversable (PreDecoratedTree a) (Ord a, Show a) => Foldable (PreDecoratedTree a) (Eq b, Ord a, Show a) => Eq (PreDecoratedTree a b) (Ord a, Ord b, Show a) => Ord (PreDecoratedTree a b) (Ord a, Read a, Read b, Show a) => Read (PreDecoratedTree a b) (Ord a, Show a, Show b) => Show (PreDecoratedTree a b) (Ord a, Show a, Show b) => PPrint (PreDecoratedTree a b)
 vertexArity :: (Ord a, Show a) => PreDecoratedTree a b -> Int Source
The arity of a corolla
 glueTrees :: (Ord a, Show a) => PreDecoratedTree a (PreDecoratedTree a b) -> PreDecoratedTree a b Source
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.
 type DecoratedTree a = PreDecoratedTree a Int Source
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.
 data (Ord a, Show a, TreeOrdering t) => OrderedTree a t Source
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.
Constructors
 OT (DecoratedTree a) t
Instances
 (Ord a, Show a, TreeOrdering t) => Eq (OrderedTree a t) (Ord a, Show a, TreeOrdering t) => Ord (OrderedTree a t) (Ord a, Read a, Read t, Show a, TreeOrdering t) => Read (OrderedTree a t) (Ord a, Show a, TreeOrdering t) => Show (OrderedTree a t) (Ord a, Show a, TreeOrdering t) => PPrint (OrderedTree a t)
 ot :: (Ord a, Show a, TreeOrdering t) => DecoratedTree a -> OrderedTree a t Source
Building an ordered tree with PathLex ordering from a decorated tree.
 dt :: (Ord a, Show a, TreeOrdering t) => OrderedTree a t -> DecoratedTree a Source
Extracting the underlying tree from an ordered tree.
Monomial orderings on the free operad
 class (Eq t, Show t) => TreeOrdering t where Source
The type class that parametrizes types implementing tree orderings.
Methods
 treeCompare :: (Ord a, Show a) => t -> DecoratedTree a -> DecoratedTree a -> Ordering Source
 comparePathSequence :: (Ord a, Show a) => t -> ([[a]], Shuffle) -> ([[a]], Shuffle) -> Ordering Source
 ordering :: t Source
Instances
 TreeOrdering ForestLex TreeOrdering PathLex TreeOrdering RPathLex
 pathSequence :: (Ord a, Show a) => DecoratedTree a -> ([[a]], Shuffle) Source
Finding the path sequences. cf. Dotsenko-Khoroshkin.
 orderedPathSequence :: (Ord a, Show a) => DecoratedTree a -> ([[a]], Shuffle) Source
Reordering the path sequences to mirror the actual leaf ordering.
 data RPathLex Source
Degree reverse lexicographic path sequence ordering.
Constructors
 RPathLex
Instances
 Eq RPathLex Ord RPathLex Read RPathLex Show RPathLex TreeOrdering RPathLex
 reverseOrder :: Ordering -> Ordering Source
Changes direction of an ordering.
 data PathLex Source
Path lexicographic ordering. Orders trees first by lexicographic comparison on the ordered path sequence, and then by lexicographic comparison on the leaf orderings.
Constructors
 PathLex
Instances
 Eq PathLex Ord PathLex Read PathLex Show PathLex TreeOrdering PathLex
 data ForestLex Source
Forest lexicographic ordering. Currently not implemented.
Constructors
 ForestLex
Instances
 Eq ForestLex Ord ForestLex Show ForestLex TreeOrdering ForestLex
Utility functions on trees
 corolla :: (Ord a, Show a) => a -> [Int] -> DecoratedTree a Source
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.
 leaf :: (Ord a, Show a) => Int -> DecoratedTree a Source
Build a single leaf.
 isLeaf :: (Ord a, Show a) => DecoratedTree a -> Bool Source
Check whether a given root is a leaf.
 isCorolla :: (Ord a, Show a) => DecoratedTree a -> Bool Source
Check whether a given root is a corolla.
 relabelLeaves :: (Ord a, Show a) => DecoratedTree a -> [b] -> PreDecoratedTree a b Source
Change the leaves of a tree to take their values from a given list.
 leafOrder :: (Ord a, Show a) => DecoratedTree a -> [Int] Source
Find the permutation the leaf labeling ordains for inputs.
 minimalLeaf :: (Ord a, Show a, Ord b) => PreDecoratedTree a b -> b Source
Find the minimal leaf covering any given vertex.
 nLeaves :: (Ord a, Show a) => DecoratedTree a -> Int Source
Compute the number of leaves of the entire tree covering a given vertex.
 arityDegree :: (Ord a, Show a) => DecoratedTree a -> Int Source
arityDegree is one less than nLeaves.
Shuffles
 type Shuffle = [Int] Source
A shuffle is a special kind of sequence of integers.
 isSorted :: (Ord a, Show a) => [a] -> Bool Source
We need to recognize sorted sequences of integers.
 isShuffle :: Shuffle -> Bool Source
This tests whether a given sequence of integers really is a shuffle.
 isShuffleIJ :: Shuffle -> Int -> Int -> Bool Source
This tests whether a given sequence of integers is an (i,j)-shuffle
 isShuffleIPQ :: Shuffle -> Int -> Int -> Bool Source
This tests whether a given sequence of integers is admissible for a specific composition operation.
 applyPerm :: Show a => Shuffle -> [a] -> [a] Source
This applies the resulting permutation from a shuffle to a set of elements
 invApplyPerm :: Shuffle -> [a] -> [a] Source
Apply the permutation inversely to applyPerm.
 kSubsets :: Int -> [Int] -> [[Int]] Source
Generate all subsets of length k from a given list.
 allShuffles :: Int -> Int -> Int -> [Shuffle] Source
Generates all shuffles from Sh_i(p,q).
Fundamental data types and instances
 operationDegree :: (Ord a, Show a) => DecoratedTree a -> Int Source
The number of internal vertices of a tree.
 operationDegrees :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> [Int] Source
A list of operation degrees occurring in the terms of the operad element
 maxOperationDegree :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Int Source
The maximal operation degree of an operadic element
 isHomogenous :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Bool Source
Check that an element of a free operad is homogenous
 shuffleCompose :: (Ord a, Show a) => Int -> Shuffle -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a Source
 nsCompose :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a Source
Composition in the non-symmetric operad. We compose s o_i t.
 symmetricCompose :: (Ord a, Show a) => Int -> Shuffle -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a Source
 nsComposeAll :: (Ord a, Show a) => DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a Source
Non-symmetric composition in the g(s;t1,...,tk) style.
 checkShuffleAll :: Shuffle -> [Int] -> Bool Source
Verification for a shuffle used for the g(s;t1,..,tk) style composition in the shuffle operad.
 isPermutation :: Shuffle -> Bool Source
Sanity check for permutations.
 shuffleComposeAll :: (Ord a, Show a) => Shuffle -> DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a Source
Shuffle composition in the g(s;t1,...,tk) style.
 symmetricComposeAll :: (Ord a, Show a) => Shuffle -> DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a Source
Symmetric composition in the g(s;t1,...,tk) style.
Divisibility among trees
 type Embedding a = DecoratedTree (Maybe a) Source
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.
 divides :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Bool Source
Returns True if there is a subtree of t isomorphic to s, respecting leaf orders.
 findAllEmbeddings :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [Embedding a] Source
Finds all ways to embed s into t respecting leaf orders.
 findRootedEmbedding :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Maybe (Embedding a) Source
Finds all ways to embed s into t, respecting leaf orders and mapping the root of s to the root of t.
 findRootedDecoratedGCD :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Maybe (PreDecoratedTree a (DecoratedTree a, DecoratedTree a)) Source
Finds a large common divisor of two trees, such that it embeds into both trees, mapping its root to the roots of the trees, respectively.
 findRootedLCM :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [DecoratedTree a] Source
Finds all small common multiples of trees s and t, under the assumption that the common multiples shares root with both trees.
 accumulateTrees :: (Ord a, Show a) => [(DecoratedTree a, DecoratedTree a)] -> [DecoratedTree a] -> [DecoratedTree a] Source
Internal utility function. Reassembles a tree according to a building recipe, and gives the orbit of the resulting tree under the symmetric group action back.
 planarTree :: (Ord a, Show a) => DecoratedTree a -> Bool Source
Checks a tree for planarity.
 findSmallBoundedLCM :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> [DecoratedTree a] Source
Finds all small common multiples of s and t such that t glues into s from above, bounded in total operation degree.
 findAllLCM :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [DecoratedTree a] Source
Finds all small common multiples of s and t.
 findAllBoundedLCM :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> [DecoratedTree a] Source
Finds all small common multiples of s and t, bounded in total operation degree.
 rePackLabels :: (Ord a, Show a, Ord b) => PreDecoratedTree a b -> DecoratedTree a Source
Relabels a tree in the right order, but with entries from [1..]
 fromJustTree :: (Ord a, Show a) => DecoratedTree (Maybe a) -> Maybe (DecoratedTree a) Source
Removes vertex type encapsulations.
 toJustTree :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree (Maybe a) Source
 equivalentOrders :: [Int] -> [Int] -> Bool Source
Verifies that two integer sequences correspond to the same total ordering of the entries.
 subTreeHasNothing :: (Ord a, Show a) => DecoratedTree (Maybe a) -> Bool Source
Returns True if any of the vertices in the given tree has been tagged.
 reconstructNode :: (Ord a, Show a) => DecoratedTree a -> Embedding a -> Maybe (DecoratedTree a) Source
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.
 reconstructTree :: (Ord a, Show a) => DecoratedTree a -> Embedding a -> Maybe (DecoratedTree a) Source
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.
Groebner basis methods
 applyReconstruction :: (Ord a, Show a, TreeOrdering t, Num n) => Embedding a -> OperadElement a n t -> OperadElement a n t Source
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.
 findAllSPolynomials :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t] Source
Finds all S polynomials for a given list of operad elements.
 findInitialSPolynomials :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t] Source
Finds all S polynomials for which the operationdegree stays bounded.
 reduceOE :: (Ord a, Show a, TreeOrdering t, Fractional n) => Embedding a -> OperadElement a n t -> OperadElement a n t -> OperadElement a n t Source
Reduce g with respect to f and the embedding em: lt f -> lt g.
 reduceCompletely :: (Ord a, Show a, TreeOrdering t, Fractional n) => OperadElement a n t -> [OperadElement a n t] -> OperadElement a n t Source
 stepOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t] Source
Perform one iteration of the Buchberger algorithm: generate all S-polynomials. Reduce all S-polynomials. Return anything that survived the reduction.
 stepInitialOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t] Source
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.
 operadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t] Source

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.

 initialOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t] Source
Perform the entire Buchberger algorithm for a given list of generators. Iteratively run the single iteration from stepOperadicBuchberger until no new elements are generated. While doing this, maintain an upper bound on the operation degree of any elements occurring.
 reduceBasis :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t] Source
Reduces a list of elements with respect to all other elements occurring in that same list.
Low degree bases
 allTrees :: (Ord a, Show a) => [DecoratedTree a] -> Int -> [DecoratedTree a] Source
All trees composed from the given generators of operation degree n.
 basisElements :: (Ord a, Show a) => [DecoratedTree a] -> [DecoratedTree a] -> Int -> [DecoratedTree a] Source
Generate basis trees for a given Groebner basis up through 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] Source
 changeOrder :: (Ord a, Show a, TreeOrdering s, TreeOrdering t) => t -> OrderedTree a s -> OrderedTree a t Source
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.
 m12_3 :: DecoratedTree Integer Source
The element m2(m2(1,2),3)
 m13_2 :: DecoratedTree Integer Source
The element m2(m2(1,3),2)
 m1_23 :: DecoratedTree Integer Source
The element m2(1,m2(2,3))
 m2 :: DecoratedTree Integer Source
The element m2(1,2)
 m3 :: DecoratedTree Integer Source
The element m3(1,2,3)
 yTree :: DecoratedTree Integer Source
The element m2(m2(1,2),m2(3,4))
 lgb :: [OperadElement Integer Rational PathLex] Source
The list of operad elements consisting of 'm12_3'-'m13_2'-'m1_23'. This generates the ideal of relations for the operad Lie.
 type Tree = DecoratedTree Integer Source