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
