Ralf Hemmecke wrote:
>
> > 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?
Well, theoretically that would be quite nice. On practical level
I am not sure if it solves any problem.
> >> 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.
Just some remark about optimization. Compilers normally do essentially
_no_ optimization of data structures. Problem is that data can
flow between various part of program and all parts must agree on
representation. Given separate compilation decision about
representation is made using incomplete information and compiler
must assume that most general things can happen. That kills
most possibilities of optimization. More precisely, for given
type compiler always must to use the same representation.
There is some possibility for cheating, for example same languages
give you flexible array when you say that you want a list.
But cheating can not go too far, as the type has to provide
_all_ operations which are logically present. In case
of flexible array, 'rest' either is not provided or is
horribly expensive. One could also try some clever scheme
where 'rest' just creates an alternative view of an array.
But the mere possiblity of alternative views (even if given
program does not use them) slows down all operations. And
smart 'rest' makes problematic to implement smart 'cons'.
So common wisdom is to avoid clever schems and just use
very strightforward mappings from types to representation.
--
Waldek Hebisch
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
