[fricas-devel] [RFC] about Rep of Tree

[oldk1331]

1. Current Rep of Tree is:

Rep := Union(node:Record(value: S, args: List %),empty:"empty")

This Rep wastes some space, a more efficient representation is:

Rep := Record(val : S, args : List %)

2. Then you may ask, how to represent empty tree under this new Rep:

We can define

empty() == NIL$Lisp
empty? t == NULL(t)$Lisp

But, in Domain Tree, "empty()" is not essential. Tree originates
from root node (unlike List originates from empty list).

From The Art of Computer Programming, vol 1, section 2.3 "Trees"
(page 312 in third edition):

A binary tree can be empty; a tree cannot.

We can define "empty()" and "empty?" to give error and
doesn't use them in the rest of code.

3. Our current implementation allows shared structure, this
doesn't satisfy the definition of tree and complicates our
implementation and currently is not used. I propose to remove
"cyclic*" from Tree, and if needed, implement them properly
in a graph data structure.


If there is no objection, I'll start making such changes.