On Thu, 19 Feb 2009, Carl Mäsak wrote:
Timothy (>), Moritz (>>):
Speaking of Tree, let me quote from IRC:
09:23 < masak> it's a bit unfortunate that the identifier 'Tree' is now
squatted by an internal class in Perl 6, which is not
general
enough to reprenest an arbitrary tree data structure.
I fully agree with that. If it's not the most general tree, don't name
it Tree.
Hmm. I'm wanting the API for this tree structure to be able to
represent arbitrary general trees. I'm limited by the fact that the main
trees I'm familiar with are filesystems and XML, and a little with LDAP.
Can you give examples of types of tree that aren't representable with what
I'm doing?
I'll give it a shot. As previously seen in S16:
role Tree does Tree::Node {
has Tree::Node $root; # The root directory
has Tree::Node $cwn; # The current working directory (node)
has Bool $can_multiple_parent; # Nodes can have multiple parents
has Bool $can_link; # Unix links, Windows shortcuts, etc
}
A tree is a graph without cycles.
Ok, maybe I should call this Graph then, but that would *really*
confuse people.
The concept of a "root" is very common in computer representations, but in
no way necessary for a general tree. In fact, in phylogenetics, it's
business as usual to handle unrooted trees. This makes the $root attribute
meaningless in at least some cases.
Interesting. I'm happy to assume that $root is allowed to be
Undefined, I think. But let me ask a question; were you to represent an
unrooted tree in a computer, how would you do it so that, if you had to look
around the tree, you could do it? You'd need some node that was an
entry-point into the tree. That's the purpose I'm trying to get at here.
Also, I have a suspicion that the problem we have here is that the
term "node" is being used slightly differently by the computer science
community and the phylogenetic community. When I look at the unrooted tree
on:
http://en.wikipedia.org/wiki/Phylogenetic_tree
...it looks to me like they don't call anything a node unless it has a
dot at it. But if I were building a data structure to represent that tree
(eg. so that I could auto-generate the image on the Wikipedia page), I'd make
a root node for it, but somehow label it an "invisible" node, and when the
image was generated, while there would be a node for it inside the computer,
there'd be no dot on the graph. So in Computer Science terms, there'd be a
root node, but in Phylogenetic terms, there wouldn't. And I think I'd do
things that way whether I was using Perl6 or not.
(incidentally, my knowledge of phylogenetics is entirely drawn from
that Wikipedia page).
Of course, I could be wrong, so I encourage you to keep prodding :).
The $cwn is meaningless in most tree implementations I can think of.
Agreed, as in XML. But assuming that that can be Undefined is also
not a problem.
As to $can_multiple_parent, a structure which allows nodes with
multiple parents is not a tree, it's a directed graph.
Right, in mathematical/computer science terms, but how often to you
hear people refer to a file tree/filesystem tree vs. file graph :).
Hmm. I've also seen it called Plex. Would it make everyone happier
if I called the whole thing "Plex" instead? Admittedly I've never heard
anyone refer to a filesystem plex, but at least that has no semantic
conflicts, and is short enough that it could catch on :).
Whether symlinks are allowed is (1) fairly filesystem-specific, and (2) not
very pertinent to the tree object itself.
Hmm. I agree. I think what we have here is a miscommunication
(probably my fault :) ) about what I'm trying to achieve.
What I want to do is make an API which has many features that the IETF
community would call MAY instead of MUST; ie. "You don't have to do X, but
if you do, call it Y". I agree it's filesystem-specific; it should probably
be a private attribute or something. I was wanting the info stored somewhere
so that it could be looked up, but maybe the thing to do is to let people try
to link, and catch exceptions :).
What's left is, in effect, this:
role Tree does Tree::Node {
}
While an empty role _does_ indeed have potential, and could be made to
work with most tree implementations out there, it's also a bit of a
shame to pretend to provide four attributes with Tree, neither of
which is actually an attribute of a general graph-theoretical tree.
Just sayin'.
Depends on what you're trying to achieve; see above :).
Another thing I found myself saying yesterday was that "designing a
language also involves knowing when not to decide things for the
programmer." I wish there was a way to say this, while also
emphasizing my appreciation for the many good changes to S16. Files
and I/O are obviously areas where the bikeshedding tendency grows
extra strong, so I'm glad someone actually goes in and does things to
the spec.
But I do believe that creating a general tree role of the above kind
would be unfortunate in at least two ways: it'd limit the possible
implementations of trees (while not giving much back in terms of an
advantage), and it'd use up the perfectly good name "Tree". I'd say
keep it simple, keep directory structures and XML DOM trees separate,
and don't let Perl second-guess what you want to implement.
Would s/Tree/Plex/ make you happier?
:)
---------------------------------------------------------------------
| Name: Tim Nelson | Because the Creator is, |
| E-mail: wayl...@wayland.id.au | I am |
---------------------------------------------------------------------
----BEGIN GEEK CODE BLOCK----
Version 3.12
GCS d+++ s+: a- C++$ U+++$ P+++$ L+++ E- W+ N+ w--- V-
PE(+) Y+>++ PGP->+++ R(+) !tv b++ DI++++ D G+ e++>++++ h! y-
-----END GEEK CODE BLOCK-----
