|
|
|
|
|
|
| Synopsis |
|
| class PPrint a where | | | | 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] | | | | | 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 | | | | 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 | | | type FreeOperad a = OperadElement a Rational PathLex |
|
|
|
| Pretty printing
|
|
|
| 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 | | |  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) |
|
|
|
|
| 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 | | | 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) |
|
|
|
|
| Extracting the internal structure of the an element of the free operad.
|
|
|
| Scalar multiplication in the operad.
|
|
|
| Apply a function to each monomial tree in the operad element.
|
|
|
| Fold a function over all monomial trees in an operad element, collating the results in a list.
|
|
|
| Given a list of (tree,coefficient)-pairs, reconstruct the corresponding operad element.
|
|
|
| Given an operad element, extract a list of (tree, coefficient) pairs.
|
|
| Handling polynomials in the free operad
|
|
|
| Construct an element in the free operad from its internal structure. Use this instead of the constructor.
|
|
|
| Construct a monomial in the free operad from a tree and a tree ordering. It's coefficient will be 1.
|
|
|
| Construct a monomial in the free operad from a tree, a tree ordering and a coefficient.
|
|
|
| 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.
|
|
|
| Check whether an element is equal to 0.
|
|
|
| Extract the leading term of an operad element.
|
|
|
| Extract the ordered tree for the leading term of an operad element.
|
|
|
| Extract the tree for the leading term of an operad element.
|
|
|
| Extract the leading coefficient of an operad element.
|
|
|
| Extract all occurring monomial trees from an operad element.
|
|
| Decorated and ordered trees
|
|
|
| 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 | | | 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) |
|
|
|
|
| The arity of a corolla
|
|
|
| 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.
|
|
|
| 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.
|
|
|
| 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 | | | 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) |
|
|
|
|
| Building an ordered tree with PathLex ordering from a decorated tree.
|
|
|
| Extracting the underlying tree from an ordered tree.
|
|
| Monomial orderings on the free operad
|
|
|
| The type class that parametrizes types implementing tree orderings.
| | | Methods | | | | Instances | |
|
|
|
| Finding the path sequences. cf. Dotsenko-Khoroshkin.
|
|
|
| Reordering the path sequences to mirror the actual leaf ordering.
|
|
|
| Degree reverse lexicographic path sequence ordering.
| | Constructors | | | Instances | |
|
|
|
| Changes direction of an ordering.
|
|
|
| Path lexicographic ordering. Orders trees first by lexicographic comparison on
the ordered path sequence, and then by lexicographic comparison on the leaf orderings.
| | Constructors | | | Instances | |
|
|
|
| Forest lexicographic ordering. Currently not implemented.
| | Constructors | | | Instances | |
|
|
| Utility functions on trees
|
|
|
| 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.
|
|
|
| Build a single leaf.
|
|
|
| Check whether a given root is a leaf.
|
|
|
| Check whether a given root is a corolla.
|
|
|
| Change the leaves of a tree to take their values from a given list.
|
|
|
| Find the permutation the leaf labeling ordains for inputs.
|
|
|
| Find the minimal leaf covering any given vertex.
|
|
|
| Compute the number of leaves of the entire tree covering a given vertex.
|
|
|
| arityDegree is one less than nLeaves.
|
|
| Shuffles
|
|
|
| A shuffle is a special kind of sequence of integers.
|
|
|
| We need to recognize sorted sequences of integers.
|
|
|
| This tests whether a given sequence of integers really is a shuffle.
|
|
|
| This tests whether a given sequence of integers is an (i,j)-shuffle
|
|
|
| This tests whether a given sequence of integers is admissible for a specific composition operation.
|
|
|
| This applies the resulting permutation from a shuffle to a set of elements
|
|
|
| Apply the permutation inversely to applyPerm.
|
|
|
| Generate all subsets of length k from a given list.
|
|
|
| Generates all shuffles from Sh_i(p,q).
|
|
| Fundamental data types and instances
|
|
|
| The number of internal vertices of a tree.
|
|
|
| A list of operation degrees occurring in the terms of the operad element
|
|
|
| The maximal operation degree of an operadic element
|
|
|
| Check that an element of a free operad is homogenous
|
|
| Free operad
|
|
| Operadic compositions
|
|
|
| Composition in the shuffle operad
|
|
|
| Composition in the non-symmetric operad. We compose s o_i t.
|
|
|
| Composition in the symmetric operad
|
|
|
| Non-symmetric composition in the g(s;t1,...,tk) style.
|
|
|
| Verification for a shuffle used for the g(s;t1,..,tk) style composition in the shuffle operad.
|
|
|
| Sanity check for permutations.
|
|
|
| Shuffle composition in the g(s;t1,...,tk) style.
|
|
|
| Symmetric composition in the g(s;t1,...,tk) style.
|
|
| Divisibility among trees
|
|
|
| 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.
|
|
|
| Returns True if there is a subtree of t isomorphic to s, respecting leaf orders.
|
|
|
| Finds all ways to embed s into t respecting leaf orders.
|
|
|
| Finds all ways to embed s into t, respecting leaf orders and mapping the root of s to the root of t.
|
|
|
| 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.
|
|
|
| Finds all small common multiples of trees s and t, under the assumption that the common multiples shares
root with both trees.
|
|
|
| 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.
|
|
|
| Checks a tree for planarity.
|
|
|
| Finds all small common multiples of s and t such that t glues into s from above, bounded in total operation degree.
|
|
|
| Finds all small common multiples of s and t.
|
|
|
| Finds all small common multiples of s and t, bounded in total operation degree.
|
|
|
| Relabels a tree in the right order, but with entries from [1..]
|
|
|
| Removes vertex type encapsulations.
|
|
|
| Adds vertex type encapsulations.
|
|
|
| Verifies that two integer sequences correspond to the same total ordering of the entries.
|
|
|
| Returns True if any of the vertices in the given tree has been tagged.
|
|
|
| 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.
|
|
|
| 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
|
|
|
| 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.
|
|
|
| Finds all S polynomials for a given list of operad elements.
|
|
|
| Finds all S polynomials for which the operationdegree stays bounded.
|
|
|
| Reduce g with respect to f and the embedding em: lt f -> lt g.
|
|
|
|
|
| Perform one iteration of the Buchberger algorithm: generate all S-polynomials. Reduce all S-polynomials.
Return anything that survived the reduction.
|
|
|
| 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.
|
|
|
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.
|
|
|
| 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.
|
|
|
| Reduces a list of elements with respect to all other elements occurring in that same list.
|
|
| Low degree bases
|
|
|
| All trees composed from the given generators of operation degree n.
|
|
|
| Generate basis trees for a given Groebner basis up through degree maxDegree. divisors is expected
to contain the leading monomials in the Groebner basis.
|
|
|
|
|
| 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.
|
|
|
| The element m2(m2(1,2),3)
|
|
|
| The element m2(m2(1,3),2)
|
|
|
| The element m2(1,m2(2,3))
|
|
|
| The element m2(1,2)
|
|
|
| The element m3(1,2,3)
|
|
|
| The element m2(m2(1,2),m2(3,4))
|
|
|
| The list of operad elements consisting of 'm12_3'-'m13_2'-'m1_23'. This generates the
ideal of relations for the operad Lie.
|
|
|
|
|
|
| Produced by Haddock version 2.4.2 |
