Link Search Menu Expand Document

Funcons-beta : Trees.cbs | PRETTY | PDF


Trees

Meta-variables
  T <: values
Datatype
  trees(T) ::= tree( _:T, _:(trees(T))*)

trees(T) consists of finitely-branching trees with elements of type T. When V:T, tree(V) is a leaf, and tree(V,B_1,...,B_n) is a tree with branches B_1, …, B_n.

Funcon
  tree-root-value(_:trees(T)) : =>(T)?
Rule
  tree-root-value tree(V:T, _*:(trees(T))*) ~> V
Funcon
  tree-branch-sequence(_:trees(T)) : =>(trees(T))*
Rule
  tree-branch-sequence tree(_:T, B*:(trees(T))*) ~> B*
Funcon
  single-branching-sequence(_:trees(T)) : =>T+

single-branching-sequence B extracts the values in B starting from the root, provided that B is at most single-branching; otherwise it fails.

A sequence of trees corresponds to a forest, and the selector funcons on trees B extend to forests B*:

Funcon
  forest-root-value-sequence(_:(trees(T))*) : =>T*
Rule
  forest-root-value-sequence(B:trees(T), B*:(trees(T))*)
   ~>(tree-root-value B , forest-root-value-sequence B*)
Rule
  forest-root-value-sequence( ) ~>( )
Funcon
  forest-branch-sequence(_:(trees(T))*) : =>T*
Rule
  forest-branch-sequence(B:trees(T), B*:(trees(T))*)
   ~>(tree-branch-sequence B , forest-branch-sequence B*)
Rule
  forest-branch-sequence( ) ~>( )
Funcon
  forest-value-sequence(_:(trees(T))*) : =>T*

forest-value-sequence B* provides the values from a left-to-right pre-order depth-first traversal.

Other linearizations of trees can be added: breadth-first, right-to-left, C3, etc.