On 12/11/18 1:55 PM, Ralf Hemmecke wrote:
>> Another way to look at this "use NIL to represent empty tree"
>> problem:
>
>> We disallow the existence of empty tree.
>>
>> 1. Empty tree is not required by the definition of tree.
>> 2. You can not construct an empty tree from existing
>> and future operations of Tree:
>>
>> For example, "delete a node from tree" is not well defined:
>> you can not delete the root node (you can delete a child though).
>>
>> So for the domain Tree, we can avoid this problem by
>>
>> empty() == error "There is no empty aggregate in domain Tree"
>> empty? t == false
>>
>> Can I commit the patch that uses this approach?
>
> Somehow I have the tendency to believe that the empty tree is a tree,
> but on the other hand, there is also the problem whether 0 is a natural
> number or not.
Yes, it is debatable, as we can see in
https://en.wikipedia.org/wiki/Tree_(data_structure)
But I think it is enough for us to have empty tree in BinaryTree
and do not have empty tree in Tree. We state it clearly in
documentation should be fine, no need to change the name of domain.
> The empty tree does indeed look very special. An empty doubly linked
> list is probably more common.
Yes, empty doubly linked is unavoidable. One way to work around
is to have sentinel node, so that empty list is a list that has
only sentinel node. But it makes traverse operation like "rest"
difficult.
Another way to work around is to actually define an empty
list in domain:
empty_list :=
node := [NIL pretend S, NIL pretend %, NIL pretend %]
node.prev := node.next := node
node
empty() == empty_list
empty? l == EQ(l, empty_list)
This is essentially the same as using NIL, but it should make
compiler happy.
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
