> Yes, it is debatable, as we can see in > https://en.wikipedia.org/wiki/Tree_(data_structure)
Since you refer to wikipedia... why not using this definition: https://en.wikipedia.org/wiki/Tree_(data_structure)#Type_theory In orther words, we introduce forests. Shouldn't it be possible to define Forest and Tree as mutually recursive data types? >> 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. When you first wrote about improving the datastructure by avoiding Union, I thought it is a good idea. However, although I don't like that the compiler assumes that a record is not NIL, that is a reasonable assumption. And more importantly, the use of Union in the definition of some data type (maybe for Tree it's debatable, since one can have Forest) can be closer to the mindset of the programmer/mathematician. If possible, optimization should be left to the compiler. OK, we all know that compilers are not always that good. And although I personally like to think about good datastrucutres, I think that it is of high value for the future that programmers can simply write down the most natural mathematical definition that comes to their mind and have the compiler making efficient code out of it. Ralf -- 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.
