Math.Operad

Pretty printing

class PPrint a where

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

pP :: a -> IO ()

Instances

PPrint Int

PPrint Integer

PPrint a => PPrint [a]

PPrint a => PPrint (Maybe a)

(PPrint a, PPrint b) => PPrint (Either a b)

(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)

(PPrint a, PPrint b, PPrint c) => PPrint (a, b, c)

(Ord a, Show a, Show n, TreeOrdering t) => PPrint (OperadElement a n t)

(PPrint a, PPrint b, PPrint c, PPrint d) => PPrint (a, b, c, d)

(PPrint a, PPrint b, PPrint c, PPrint d, PPrint e) => PPrint (a, b, c, d, e)

type MonomialMap a t n = Map a t n

newtype (Ord a, Show a, TreeOrdering t) => 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

OE (MonomialMap 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)

Arithmetic in the operad.

(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 -> MonomialMap a t n

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

Scalar multiplication in the operad.

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

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]

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

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)]

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

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

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

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

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

Check whether an element is equal to 0.

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 as an operad element.

leadingTerm :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> (OrderedTree a t, n)

Extract 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 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

Extract the tree for the leading term of an operad element.

leadingCoefficient :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> n

Extract the leading coefficient of an operad element.

getTrees :: (TreeOrdering t, Show a, Ord a) => OperadElement a n t -> [OrderedTree a t]

Extract all occurring monomial trees from an operad element.

Decorated and ordered trees

data (Ord a, Show a) => PreDecoratedTree a b

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

Fields

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) => Foldable (PreDecoratedTree a)

(Ord a, Show a) => Traversable (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

The arity of a corolla

vertexMap :: (Ord a, Show a, Ord b, Show b) => (a -> b) -> PreDecoratedTree a c -> PreDecoratedTree b c

Apply a function f to all the internal vertex labels of a PreDecoratedTree.

glueTrees :: (Ord a, Show a) => PreDecoratedTree a (PreDecoratedTree a b) -> PreDecoratedTree a b

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

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

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)

Monomial ordering for trees. We require this to be a total well-ordering, compatible with the operadic compositions.

(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

Building an ordered tree with PathLex ordering from a decorated tree.

dt :: (Ord a, Show a, TreeOrdering t) => OrderedTree a t -> DecoratedTree a

Extracting the underlying tree from an ordered tree.

Monomial orderings on the free operad

class (Eq t, Show t) => TreeOrdering t where

The type class that parametrizes types implementing tree orderings.

Methods

treeCompare :: (Ord a, Show a) => t -> DecoratedTree a -> DecoratedTree a -> Ordering

comparePathSequence :: (Ord a, Show a) => t -> DecoratedTree a -> ([[a]], Shuffle) -> DecoratedTree a -> ([[a]], Shuffle) -> Ordering

ordering :: t

Instances

TreeOrdering RPermRPath

TreeOrdering RPermPath

TreeOrdering PermRPath

TreeOrdering PermPath

TreeOrdering RPathRPerm

TreeOrdering PathRPerm

TreeOrdering RPathPerm

TreeOrdering PathPerm

pathSequence :: (Ord a, Show a) => DecoratedTree a -> ([[a]], Shuffle)

Finding the path sequences. cf. Dotsenko-Khoroshkin.

orderedPathSequence :: (Ord a, Show a) => DecoratedTree a -> ([[a]], Shuffle)

Reordering the path sequences to mirror the actual leaf ordering.

reverseOrder :: Ordering -> Ordering

Changes direction of an ordering.

data PathPerm

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.

Constructors

PathPerm

Instances

Eq PathPerm

Ord PathPerm

Read PathPerm

Show PathPerm

TreeOrdering PathPerm

data RPathPerm

Constructors

RPathPerm

Instances

Eq RPathPerm

Ord RPathPerm

Read RPathPerm

Show RPathPerm

TreeOrdering RPathPerm

data PathRPerm

Constructors

PathRPerm

Instances

Eq PathRPerm

Ord PathRPerm

Read PathRPerm

Show PathRPerm

TreeOrdering PathRPerm

data RPathRPerm

Constructors

RPathRPerm

Instances

Eq RPathRPerm

Ord RPathRPerm

Read RPathRPerm

Show RPathRPerm

TreeOrdering RPathRPerm

data PermPath

Constructors

PermPath

Instances

Eq PermPath

Ord PermPath

Read PermPath

Show PermPath

TreeOrdering PermPath

data PermRPath

Constructors

PermRPath

Instances

Eq PermRPath

Ord PermRPath

Read PermRPath

Show PermRPath

TreeOrdering PermRPath

data RPermPath

Constructors

RPermPath

Instances

Eq RPermPath

Ord RPermPath

Read RPermPath

Show RPermPath

TreeOrdering RPermPath

data RPermRPath

Constructors

RPermRPath

Instances

Eq RPermRPath

Ord RPermRPath

Read RPermRPath

Show RPermRPath

TreeOrdering RPermRPath

Utility functions on trees

corolla :: (Ord a, Show a) => a -> [Int] -> DecoratedTree a

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

Build a single leaf.

isLeaf :: (Ord a, Show a) => DecoratedTree a -> Bool

Check whether a given root is a leaf.

isCorolla :: (Ord a, Show a) => DecoratedTree a -> Bool

Check whether a given root is a corolla.

relabelLeaves :: (Ord a, Show a) => DecoratedTree a -> [b] -> PreDecoratedTree a b

Change the leaves of a tree to take their values from a given list.

leafOrder :: (Ord a, Show a) => DecoratedTree a -> [Int]

Find the permutation the leaf labeling ordains for inputs.

minimalLeaf :: (Ord a, Show a, Ord b) => PreDecoratedTree a b -> b

Find the minimal leaf covering any given vertex.

nLeaves :: (Ord a, Show a) => DecoratedTree a -> Int

Compute the number of leaves of the entire tree covering a given vertex.

arityDegree :: (Ord a, Show a) => DecoratedTree a -> Int

arityDegree is one less than nLeaves.

Shuffles

type Shuffle = [Int]

A shuffle is a special kind of sequence of integers.

isSorted :: (Ord a, Show a) => [a] -> Bool

We need to recognize sorted sequences of integers.

isShuffle :: Shuffle -> Bool

This tests whether a given sequence of integers really is a shuffle.

isShuffleIJ :: Shuffle -> Int -> Int -> Bool

This tests whether a given sequence of integers is an (i,j)-shuffle

isShuffleIPQ :: Shuffle -> Int -> Int -> Bool

This tests whether a given sequence of integers is admissible for a specific composition operation.

applyPerm :: Show a => Shuffle -> [a] -> [a]

This applies the resulting permutation from a shuffle to a set of elements

invApplyPerm :: Shuffle -> [a] -> [a]

Apply the permutation inversely to applyPerm.

kSubsets :: Int -> [Int] -> [[Int]]

Generate all subsets of length k from a given list.

applyAt :: (a -> a) -> Int -> [a] -> [a]

Applies f only at the nth place in a list.

lastNonzero :: Num a => [a] -> Int

Picks out the last nonzero entry in a list.

allShPerm :: Int -> [Int] -> [[[Int]]]

Generates shuffle permutations by filling buckets.

allShuffles :: Int -> Int -> Int -> [Shuffle]

Generates all shuffles from Sh_i(p,q).

Fundamental data types and instances

operationDegree :: (Ord a, Show a) => DecoratedTree a -> Int

The number of internal vertices of a tree.

operationDegrees :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> [Int]

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

The maximal operation degree of an operadic element

isHomogenous :: (Ord a, Show a, TreeOrdering t, Num n) => OperadElement a n t -> Bool

Check that an element of a free operad is homogenous

Free operad

Operadic compositions

shuffleCompose :: (Ord a, Show a) => Int -> Shuffle -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a

Composition in the shuffle operad

nsCompose :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> DecoratedTree a

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

Composition in the symmetric operad

nsComposeAll :: (Ord a, Show a) => DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a

Non-symmetric composition in the g(s;t1,...,tk) style.

checkShuffleAll :: Shuffle -> [Int] -> Bool

Verification for a shuffle used for the g(s;t1,..,tk) style composition in the shuffle operad.

isPermutation :: Shuffle -> Bool

Sanity check for permutations.

shuffleComposeAll :: (Ord a, Show a) => Shuffle -> DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a

Shuffle composition in the g(s;t1,...,tk) style.

symmetricComposeAll :: (Ord a, Show a) => Shuffle -> DecoratedTree a -> [DecoratedTree a] -> DecoratedTree a

Symmetric composition in the g(s;t1,...,tk) style.

Divisibility among trees

type Embedding a = DecoratedTree (Maybe 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.

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.

dividesHigh :: (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.

dividesRooted :: (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.

findAllEmbeddings :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [Embedding a]

Finds all ways to embed s into t respecting leaf orders.

findUnsortedRootedEmbedding :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Maybe (Embedding a)

Helper function for findRootedEmbedding.

findRootedEmbedding :: (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.

planarTree :: (Ord a, Show a) => DecoratedTree a -> Bool

Checks a tree for planarity.

dividesDifferent :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> DecoratedTree a -> Bool

Returns True if s and t divide u, with different embeddings and t sharing root with u.

flipEither :: Either a a -> Either a a

Interchanges Left to Right and Right to Left for types Either a a

stripEither :: Either a a -> a

Projects the type Either a a onto the type a in the obvious manner.

flipEitherRoot :: (Ord a, Show a) => PreDecoratedTree (Either a a) b -> PreDecoratedTree (Either a a) b

Applies flipEither to the root vertex label of a tree.

fuseTree :: (Ord a, Show a) => DecoratedTree (Either a a) -> [Int] -> DecoratedTree (Either a a)

Projects vertex labels and applies leaf labels to a tree with internal labeling in Either a a.

stripTree :: (Ord a, Show a) => DecoratedTree (Either a a) -> DecoratedTree a

Strips the Either layer from internal vertex labels

leafOrders :: (Ord a, Show a, Ord b, Show b) => DecoratedTree a -> DecoratedTree b -> [(Int, Int)]

Acquires lists for resorting leaf labels according to the algorithm found for constructing small common multiples with minimal work.

findFirstRight :: (Ord a, Show a, Ord b, Show b) => DecoratedTree (Either a b) -> Maybe (DecoratedTree (Either a b))

Locates the first vertex tagged with a Right constructor in a tree labeled with Either a b.

maybeLast :: [a] -> Maybe a

Equivalent to listToMaybe . reverse

leafLabels :: (Ord a, Show a) => DecoratedTree a -> [Int] -> [Int] -> [[Int]]

Recursive algorithm to figure out correct leaf labels for a reconstructed small common multiple of two trees.

findRootedSCM :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> Maybe (DecoratedTree a)

Finds rooted small common multiples of two trees.

findNonSymmetricSCM :: (Ord a, Show a) => Int -> DecoratedTree (Either a a) -> DecoratedTree (Either a a) -> [DecoratedTree (Either a a)]

Finds structural small common multiples, disregarding leaf labels completely.

findBoundedSCM :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> [DecoratedTree (Either a a)]

Finds small common multiples of two trees bounding internal operation degree.

findAllSCM :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree a -> [DecoratedTree (Either a a)]

Finds all small common multiples of two trees.

findAllBoundedSCM :: (Ord a, Show a) => Int -> DecoratedTree a -> DecoratedTree a -> [DecoratedTree (Either a a)]

Finds all small common multiples of two trees, bounding the internal operation degree.

scmToEmbedding :: (Ord a, Show a) => DecoratedTree (Either a a) -> DecoratedTree a -> DecoratedTree a -> (Embedding a, Embedding a)

Constructs embeddings for s and t in SCM(s,t) and returns these.

rePackLabels :: (Ord a, Show a, Ord b) => PreDecoratedTree a b -> DecoratedTree a

Relabels a tree in the right order, but with entries from [1..]

fromJustTree :: (Ord a, Show a) => DecoratedTree (Maybe a) -> Maybe (DecoratedTree a)

Removes vertex type encapsulations.

toJustTree :: (Ord a, Show a) => DecoratedTree a -> DecoratedTree (Maybe a)

Adds vertex type encapsulations.

equivalentOrders :: [Int] -> [Int] -> Bool

Verifies that two integer sequences correspond to the same total ordering of the entries.

subTreeHasNothing :: (Ord a, Show a) => DecoratedTree (Maybe a) -> Bool

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)

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)

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

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]

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]

Finds all S polynomials for which the operationdegree stays bounded.

findSPolynomials :: (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.

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 findInitialSPolynomials.

findNSSPolynomials :: (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.

reduceOE :: (Ord a, Show a, TreeOrdering t, Fractional n) => Embedding a -> 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.

reduceInitial :: (Ord a, Show a, TreeOrdering t, Fractional n) => OperadElement a n t -> [OperadElement a n t] -> OperadElement a n t

Reduce the leading monomial of op with respect to gb.

reduceCompletely :: (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.

stepOperadicBuchberger :: (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.

stepNSOperadicBuchberger :: (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]

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.

stepNSInitialOperadicBuchberger :: (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.

operadicBuchberger :: (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. 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.

nsOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => [OperadElement a n t] -> [OperadElement a n t]

Non-symmetric version of operadicBuchberger.

streamOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [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.

streamNSOperadicBuchberger :: (Ord a, Show a, TreeOrdering t, Fractional n) => Int -> [OperadElement a n t] -> [OperadElement a n t]

Non-symmetric version of streamOperadicBuchberger.

reduceBasis :: (Fractional n, TreeOrdering t, Show a, Ord a) => [OperadElement a n t] -> [OperadElement a n t] -> [OperadElement a n t]

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]

All trees composed from the given generators of operation degree n.

basisElements :: (Ord a, Show a) => [DecoratedTree 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.

changeOrder :: (Ord a, Show a, TreeOrdering s, TreeOrdering t) => t -> OrderedTree a s -> OrderedTree a t

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

The element m2(m2(1,2),3)

m13_2 :: DecoratedTree Integer

The element m2(m2(1,3),2)

m1_23 :: DecoratedTree Integer

The element m2(1,m2(2,3))

m2 :: DecoratedTree Integer

The element m2(1,2)

m3 :: DecoratedTree Integer

The element m3(1,2,3)

yTree :: DecoratedTree Integer

The element m2(m2(1,2),m2(3,4))

lgb :: [OperadElement Integer Rational PathPerm]

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

type FreeOperad a = OperadElement a Rational PathPerm