Florent Hivert <florent.hiv...@univ-rouen.fr> writes: > Do I understand that you can't help me with choosing good names :-) ?
I'm not sure whether it will help you ... but you may want to look at the files fricas/src/algebra/aggcat.spad.pamphlet and fricas/src/algebra/tree.spad.pamphlet where "categories" (in quotation marks, because probably not mathematical in any way) and "domains" for trees are defined. (and I admit that I have no idea how much of this is already in sage.) (in some cases I just *had* to copy the author tag, too. algebraic combinatorics forever :-) Martin ++ A recursive aggregate over a type S is a model for a ++ a directed graph containing values of type S. ++ Recursively, a recursive aggregate is a {\em node} ++ consisting of a \spadfun{value} from S and 0 or more \spadfun{children} ++ which are recursive aggregates. ++ A node with no children is called a \spadfun{leaf} node. ++ A recursive aggregate may be cyclic for which some operations as noted ++ may go into an infinite loop. RecursiveAggregate(S:Type): Category == HomogeneousAggregate(S) with ++ A binary-recursive aggregate has 0, 1 or 2 children and ++ serves as a model for a binary tree or a doubly-linked aggregate structure BinaryRecursiveAggregate(S:Type):Category == RecursiveAggregate S with ++ Description: ++ A unary-recursive aggregate is a one where nodes may have either ++ 0 or 1 children. ++ This aggregate models, though not precisely, a linked ++ list possibly with a single cycle. ++ A node with one children models a non-empty list, with the ++ \spadfun{value} of the list designating the head, or \spadfun{first}, of the ++ list, and the child designating the tail, or \spadfun{rest}, of the list. ++ A node with no child then designates the empty list. ++ Since these aggregates are recursive aggregates, they may be cyclic. UnaryRecursiveAggregate(S:Type): Category == RecursiveAggregate S with ++ Author:W. H. Burge ++ Description: \spadtype{Tree(S)} is a basic domains of tree structures. ++ Each tree is either empty or else is a {\it node} consisting of a value and ++ a list of (sub)trees. Tree(S: SetCategory): T==C where T== Join(RecursiveAggregate(S), finiteAggregate, shallowlyMutable) with ++ Author:W. H. Burge ++ Description: \spadtype{BinaryTreeCategory(S)} is the category of ++ binary trees: a tree which is either empty or else is a \spadfun{node} consisting ++ of a value and a \spadfun{left} and \spadfun{right}, both binary trees. BinaryTreeCategory(S: SetCategory): Category ==_ Join(BinaryRecursiveAggregate(S), shallowlyMutable, finiteAggregate) with ++ Description: \spadtype{BinaryTree(S)} is the domain of all ++ binary trees. A binary tree over \spad{S} is either empty or has ++ a \spadfun{value} which is an S and a \spadfun{right} ++ and \spadfun{left} which are both binary trees. BinaryTree(S: SetCategory): Exports == Implementation where Exports == BinaryTreeCategory(S) with ++ Description: BinarySearchTree(S) is the domain of ++ a binary trees where elements are ordered across the tree. ++ A binary search tree is either empty or has ++ a value which is an S, and a ++ right and left which are both BinaryTree(S) ++ Elements are ordered across the tree. BinarySearchTree(S: OrderedSet): Exports == Implementation where Exports == BinaryTreeCategory(S) with ++ Description: \spadtype{BinaryTournament(S)} is the domain of ++ binary trees where elements are ordered down the tree. ++ A binary search tree is either empty or is a node containing a ++ \spadfun{value} of type \spad{S}, and a \spadfun{right} ++ and a \spadfun{left} which are both \spadtype{BinaryTree(S)} BinaryTournament(S: OrderedSet): Exports == Implementation where Exports == BinaryTreeCategory(S) with ++ Description: \spadtype{BalancedBinaryTree(S)} is the domain of balanced ++ binary trees (bbtree). A balanced binary tree of \spad{2^k} leaves, ++ for some \spad{k > 0}, is symmetric, that is, the left and right ++ subtree of each interior node have identical shape. ++ In general, the left and right subtree of a given node can differ ++ by at most leaf node. BalancedBinaryTree(S: SetCategory): Exports == Implementation where Exports == BinaryTreeCategory(S) with ++ A PendantTree(S)is either a leaf? and is an S or has ++ a left and a right both PendantTree(S)'s PendantTree(S: SetCategory): T == C where T == BinaryRecursiveAggregate(S) with -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org