úÎ ÂZšPz      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyMThis yields user interface functions for human readable printing of objects.  The idea is to use z( instances for marshalling of data, and  for  user interaction.  5A shuffle is a special kind of sequence of integers. :Forest lexicographic ordering. Currently not implemented. OPath lexicographic ordering. Orders trees first by lexicographic comparison on X the ordered path sequence, and then by lexicographic comparison on the leaf orderings. 5Degree reverse lexicographic path sequence ordering. DThe type class that parametrizes types implementing tree orderings. PMonomial orderings on the free operad requires us to choose an ordering for the D trees. These are parametrized by types implementing the type class , Q and this is a data type for a tree carrying its comparison type. We call these   ordered trees. RThis is the fundamental datatype of the whole project. Monomials in a free operad T are decorated trees, and we build a type for decorated trees here. We require our M trees to have Int labels, limiting us to at most 2 147 483 647 leaf labels. QThe 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. X The vertices carry labels, used for the ordering on trees and to distinguish different $ basis corollas of the same arity. The arity of a corolla ZIf a tree has trees as labels for its leaves, we can replace the leaves with the roots of V those label trees. Thus we may glue together trees, as required by the compositions. Building an ordered tree with   ! ordering from a decorated tree. 5Extracting the underlying tree from an ordered tree. 5Finding the path sequences. cf. Dotsenko-Khoroshkin. BReordering the path sequences to mirror the actual leaf ordering. "Changes direction of an ordering. !`Build a single corolla in a decorated tree. Takes a list for labels for the leaves, and derives e 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. %DChange the leaves of a tree to take their values from a given list. &;Find the permutation the leaf labeling ordains for inputs. '1Find the minimal leaf covering any given vertex. (ICompute the number of leaves of the entire tree covering a given vertex. )) is one less than (. *3We need to recognize sorted sequences of integers. +EThis tests whether a given sequence of integers really is a shuffle. ,DThis tests whether a given sequence of integers is an (i,j)-shuffle -dThis tests whether a given sequence of integers is admissible for a specific composition operation. .KThis applies the resulting permutation from a shuffle to a set of elements /#Apply the permutation inversely to .. 05Generate all subsets of length k from a given list. 1(Generates all shuffles from Sh_i(p,q). /  !"#$%&'()*+,-./01/    !"#$%&'()*+,-./01{lThe type carrying operadic elements. An element in an operad is the leading monomial tree, its coefficient, H and a list of all other elements stored as (tree, coefficient) pairs. |ZCollapse the storage, removing duplicates from the list carrying the tail of the element. }XGiven a list of (tree,coefficient)-pairs, reconstruct the corresponding operad element. ~GGiven an operad element, extract a list of (tree, coefficient) pairs. >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. =Extract all occurring monomial trees from an operad element. ‚Scalar multiplication. ƒjConstruct an element in the free operad from its internal structure. Use this instead of the constructor. „KConstruct a monomial in the free operad from a tree and a tree ordering. It's coefficient will be 1. …XConstruct a monomial in the free operad from a tree, a tree ordering and a coefficient. †YReturn the zero of the corresponding operad, with type appropriate to the given element. E Can be given an appropriately casted undefined to construct a zero. ‡)Check whether an element is equal to 0. ˆ0Extract the leading term of an operad element. ‰DExtract the ordered tree for the leading term of an operad element. Š<Extract the tree for the leading term of an operad element. ‹6Extract the leading coefficient of an operad element. {Œ|}~€‚ƒ„…†‡ˆ‰Š‹{ŒŒ|}~€‚ƒ„…†‡ˆ‰Š‹Ž‘’“”•–—˜™š›œŽŽ‘’“”•–—˜™š›œ2VThe type carrying operadic elements. An element in an operad is an associative array E with keys being labeled trees and values being their coefficients. 5HExtracting the internal structure of the an element of the free operad. 6%Scalar multiplication in the operad. 7>Apply a function to each monomial tree in the operad element. 8_Fold a function over all monomial trees in an operad element, collating the results in a list. 9XGiven a list of (tree,coefficient)-pairs, reconstruct the corresponding operad element. :GGiven an operad element, extract a list of (tree, coefficient) pairs. ;jConstruct an element in the free operad from its internal structure. Use this instead of the constructor. <KConstruct a monomial in the free operad from a tree and a tree ordering. It's coefficient will be 1. =XConstruct a monomial in the free operad from a tree, a tree ordering and a coefficient. >YReturn the zero of the corresponding operad, with type appropriate to the given element. E Can be given an appropriately casted undefined to construct a zero. ?)Check whether an element is equal to 0. @0Extract the leading term of an operad element. ADExtract the ordered tree for the leading term of an operad element. B<Extract the tree for the leading term of an operad element. C6Extract the leading coefficient of an operad element. D=Extract all occurring monomial trees from an operad element. 23456789:;<=>?@ABCD233456789:;<=>?@ABCD *E[Data type to move the results of finding an embedding point for a subtree in a larger tree c around. The tree is guaranteed to have exactly one corolla tagged Nothing, the subtrees on top of f that corolla sorted by minimal covering leaf in the original setting, and the shuffle carried around F is guaranteed to restore the original leaf labels before the search. F+The number of internal vertices of a tree. GIA list of operation degrees occurring in the terms of the operad element H4The maximal operation degree of an operadic element I5Check that an element of a free operad is homogenous J"Composition in the shuffle operad K>Composition in the non-symmetric operad. We compose s o_i t. L$Composition in the symmetric operad M8Non-symmetric composition in the g(s;t1,...,tk) style. N_Verification for a shuffle used for the g(s;t1,..,tk) style composition in the shuffle operad. O Sanity check for permutations. P2Shuffle composition in the g(s;t1,...,tk) style. Q4Symmetric composition in the g(s;t1,...,tk) style. R&Returns True if there is a subtree of t+ isomorphic to s, respecting leaf orders. S9Finds all ways to embed s into t respecting leaf orders. TeFinds all ways to embed s into t, respecting leaf orders and mapping the root of s to the root of t. UbFinds a large common divisor of two trees, such that it embeds into both trees, mapping its root + to the roots of the trees, respectively. ViFinds all small common multiples of trees s and t, under the assumption that the common multiples shares  root with both trees. W=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. XChecks a tree for planarity. YtFinds all small common multiples of s and t such that t glues into s from above, bounded in total operation degree. Z-Finds all small common multiples of s and t. [QFinds 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. _ZVerifies that two integer sequences correspond to the same total ordering of the entries. `GReturns True if any of the vertices in the given tree has been tagged. a_The function that mimics resubstitution of a new tree into the hole left by finding embedding,  called m_alpha,bPeta in Dotsenko-Khoroshkin. This version only attempts to resubstitute the tree + at the root, bailing out if not possible. b_The function that mimics resubstitution of a new tree into the hole left by finding embedding,  called m_alpha,bLeta in Dotsenko-Khoroshkin. This version recurses down in the tree in order @ to find exactly one hole, and substitute the tree sub into it. cqApplies the reconstruction map represented by em to all trees in the operad element op. Any operad element that q 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. d>Finds all S polynomials for a given list of operad elements. eEFinds all S polynomials for which the operationdegree stays bounded. f?Reduce g with respect to f and the embedding em: lt f -> lt g. hiPerform one iteration of the Buchberger algorithm: generate all S-polynomials. Reduce all S-polynomials. . Return anything that survived the reduction. iiPerform 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. jmPerform the entire Buchberger algorithm for a given list of generators. Iteratively run the single iteration  from h& until no new elements are generated. rDO NOTE: This is entirely possible to get stuck in an infinite loop. It is not difficult to write down generators o such that the resulting Groebner basis is infinite. No checking is performed to catch this kind of condition. kmPerform the entire Buchberger algorithm for a given list of generators. Iteratively run the single iteration  from hP until no new elements are generated. While doing this, maintain an upper bound 4 on the operation degree of any elements occurring. l[Reduces a list of elements with respect to all other elements occurring in that same list. mDAll trees composed from the given generators of operation degree n. nBGenerate basis trees for a given Groebner basis up through degree  maxDegree. divisors is expected 9 to contain the leading monomials in the Groebner basis. p^Change the monomial order used for a specific tree. Use this in conjunction with mapMonomials B in order to change monomial order for an entire operad element. ,EFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnop,EFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopsThe element m2(m2(1,2),3) tThe element m2(m2(1,3),2) uThe element m2(1,m2(2,3)) vThe element m2(1,2) wThe element m3(1,2,3) x The element m2(m2(1,2),m2(3,4)) y*The list of operad elements consisting of 'm12_3'-'m13_2'-'m1_23'. This generates the ( ideal of relations for the operad Lie. z  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz42356789:;<=>?@ABCD  !"#$%&'()*+,-./01FGHIJKLMNOPQERSTUVWXYZ[\]^_`abcdefghijklmnopstuvwxyrq qrstuvwxyž     !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHI J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t uvwxyz{|}~€7>?<=I;@ABCDEFGH‚ƒ„…†‡ˆ‰Š‹ŒŽ‘?’“ Operads-0.7 Math.OperadMath.Operad.PPrintbase Text.ShowMath.Operad.OrderedTreeMath.Operad.PolyBagMath.Operad.MapMath.Operad.MapOperadMath.Operad.OperadGBPPrintpppPShuffle ForestLex RPathRLexPathRLexPathLexRPathLex TreeOrdering treeComparecomparePathSequenceordering OrderedTreeOT DecoratedTreePreDecoratedTreeDTVertex vertexTypesubTreesDTLeaf vertexArity glueTreesotdt pathSequenceorderedPathSequence reverseOrdercorollaleafisLeaf isCorolla relabelLeaves leafOrder minimalLeafnLeaves arityDegreeisSorted isShuffle isShuffleIJ isShuffleIPQ applyPerm invApplyPermkSubsets allShuffles OperadElementOE MonomialMap extractMap.*. mapMonomials foldMonomialsfromListtoListoeoetoekzeroisZero leadingTermleadingOMonomialleadingMonomialleadingCoefficientgetTrees EmbeddingoperationDegreeoperationDegreesmaxOperationDegree isHomogenousshuffleCompose nsComposesymmetricCompose nsComposeAllcheckShuffleAll isPermutationshuffleComposeAllsymmetricComposeAlldividesfindAllEmbeddingsfindRootedEmbeddingfindRootedDecoratedGCD findRootedLCMaccumulateTrees planarTreefindSmallBoundedLCM findAllLCMfindAllBoundedLCM rePackLabels fromJustTree toJustTreeequivalentOrderssubTreeHasNothingreconstructNodereconstructTreeapplyReconstructionfindAllSPolynomialsfindInitialSPolynomialsreduceOEreduceCompletelystepOperadicBuchbergerstepInitialOperadicBuchbergeroperadicBuchbergerinitialOperadicBuchberger reduceBasisallTrees basisElementsbasisElements' changeOrder FreeOperadTreem12_3m13_2m1_23m2m3yTreelgbGHC.ShowShowcollatePBMapTM StoredTreeSTsotdotfilter foldWithKey fromListWithintersectionWithkeysmap mapKeysWithmaxViewWithKeynull unionWith