Cat::TreesClass

Cat::TreesClass represents the category of combinatorial classes of tree-like objects that can be described by a grammar.

We create a combinatorial class for unlabelled unordered trees. To this end, we inherit the data structure from the domain combinat::trees and the counting and generating methods from the category Cat::TreesClass:

domain unorderedTrees

inherits combinat::trees;

category Cat::TreesClass(Ordered=FALSE);

end_domain:

unorderedTrees::list(5)

-- o, o , o , o , o , o , o , o , o --

| | | | | / \ / \ / \ /|\ // \\ |

| | | / \ /|\ | /\ | | | |

| | / \ | | |

-- | --

This is the most common use case, where the data structure is either inherited from combinat::trees or from combinat::binaryTrees. As a syntactic sugar, there is a wrapper domain combinat::treesGeneric that achieves concisely the same effect:

unorderedTrees := combinat::treesGeneric(Ordered = FALSE):

unorderedTrees::list(5)

-- o, o , o , o , o , o , o , o , o --

| | | | | / \ / \ / \ /|\ // \\ |

| | | / \ /|\ | /\ | | | |

| | / \ | | |

-- | --

See combinat::treesGeneric for more examples.

We now illustrate how to use Cat::TreesClass to implement combinatorial classes of tree-like objects whose data structure is not given by combinat::trees. We start with unordered trees with nodes of arity at least two and labels on the leaves only, represented using sets:

domain treesAsSets

inherits Dom::BaseDomain;

category Cat::TreesClass([Leaf = Atom(id),

NodeLabel=Epsilon,

ChildList=Powerset(Tree, MinLength=2)],

Labelled);

new := l -> { op(l,2..nops(l)) };

end_domain:

treesAsSets::list(3)

Now, we construct all the expressions that can be built from one unary predicate f, and two binary commutative predicates g and h:

domain expressions

inherits Dom::BaseDomain;

category Cat::TreesClass([Leaf = Atom(f),

NodeLabel=Union(Atom(g), Atom(h))],

CompleteBinary, Ordered=FALSE);

new := l -> op(l,1)(op(l,2..nops(l)));

end_domain:

expressions::list(5)

At this point, we are reaching the limits of this category. It is almost as simple to use directly combinat::decomposableObjects:

expressions :=

combinat::decomposableObjects

([Tree = Union(Leaf, Node),

Leaf = Atom(f),

NodeLabel = Union(Atom(g), Atom(h)),

Node = Alias(Prod(NodeLabel, Multiset(Tree, Length=2)),

x -> op(x, 1) (op(op(x, 2))))]):

expressions::list(5)

Labelled, Labelled = g:	Selects whether the trees are labeled or not. b must be TRUE or FALSE. The default value is FALSE.
Binary, Binary = b:	Selects whether the trees are binary or not. b must be TRUE or FALSE. The default value is FALSE.
CompleteBinary, CompleteBinary = b:	Selects whether the trees are complete binary trees. b must be TRUE or FALSE. The default value is FALSE.
Ordered, Ordered = b:	Selects whether trees are ordered or not. b must be TRUE or FALSE. The default value is TRUE.
MainNonTerminal = T:	Specifies the main non terminal in the specification. The default value is Tree.