[Solved]: What are the applications of Rose trees?

Problem Detail: 

I recently found out about the Rose tree data structure, but just going off of a Haskell data definition and the tiny Wikipedia description of it, I've got some trouble understanding what applications a Rose tree might have.

For reference, the Haskell data definition:

data RoseTree = RoseTree a [RoseTree a] 

For those unfamiliar with Haskell -- it's a recursive data type definition with an arbitrary type a, where the type constructor is provided with a literal of type a followed by an optionally empty list of type RoseTree on the same type a.

The way I see it:

• This data structure is unordered by default (although I assume most practical applications do implement some form of ordering for searching)

• The data structure doesn't enforce a fixed number of nodes per layer at any point, except the global root, which must have a single node

Given that minimal amount of information, I'm having trouble figuring out when one might use this type of tree.

In addition to the question in the title, if search is indeed implemented in most applications of a Rose tree, how is this done?

Asked By : Jules

Answered By : Derek Elkins

You seem to have an overly "data structures and algorithms" mindset. Not every tree is some kind of search tree. Data structures are often designed to correspond to or capture aspects of a domain model.

S-expressions are almost exactly rose trees. (Or rather, I would say how they are typically thought of is as rose trees. Wikipedia is correct in saying they are more like binary trees, but what you might call "proper" S-expressions are only slightly different from rose trees.) At any rate, you can use them as a generic representation for an abstract syntax tree. The benefit of doing this is that you can easily write generic operations, e.g. "find all variables" or "swap parameters" or "rename this symbol". It's also extensible in that adding a new type of node to your abstract syntax often doesn't require really changing anything. The downsides are there aren't really any constraints, so it doesn't a priori prevent you from writing nonsense. This can be mitigated for users by standard abstract data type techniques, but the implementer of transforms and such must deal with the unstructured representation even though they "know" that the input is structured via a data type invariant. Of course, when that certainty is misplaced (possibly because things have changed), the errors tend to be unpredictable and hard to debug.

In practice, while the Data.Tree module in the standard libraries provides a rose tree, almost no one uses it in the Haskell community. Defining custom data types that explicitly capture the constraints is so easy that there is little reason to use a generic library type. Further, there has been an enormous amount of research and practice around performing generic operations over custom types which eliminates many of the benefits of using a generic representation. Finally, Haskellers tend to be very much in favor of explicit, enforced constraints and are willing to pay to get it.

To answer your last question, oftentimes searching an AST is unimportant and/or the ASTs are generally assumed to be small enough that just walking the whole thing is acceptable. Admittedly, it's not uncommon to collect definitions in a separate data structure with references into the AST which could be viewed as a sort of index. Similarly, some optimization passes will (usually locally and temporarily) build up indexes to simplify and speed up their operation. The structure of the AST corresponds to the input and so it can't be "rebalanced" or anything like that. As such, it's uncommon for the AST itself to contain indexing information or information to help "searching".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56081