How to inherit a trait multiple times with name aliasing?

Any particular reason why you use inheritance instead of a more
functional approach?

/Jesper Nordenberg

Ken McDonald skrev 2011-04-02 23:27:
> I don't see any way to achieve the following, but thought I would ask...
> (this might more properly belong in scala-debate, but I'd really like
> some way of doing this, so I'm posting here with hopes of getting
> concrete suggestions--hope that's OK)
>
>
> I've created a TreeNode trait that defines functionality allowing
> classes that inherit it from it to be correctly maintained in a tree
> structure:
>
>
> class TreeNode[T <: TreeNode[T]] {
>
> this: T =>
>
> private var parent: Option[T]
>
> private var children = new ArrayBuffer[T]
>
>
> def append(child: T) {...}
>
> def nthChild(position: Int): T = children(position)
>
> ...and so on...
>
> }
>
>
> (I'm typing in a simplified version of what I have so some errors may
> have crept in, but hopefully you get the idea.)
>
>
> However, it turns out that I'd actually like instances of TreeNode to be
> included in two different trees. If I use {{name}} notation to denote
> "name parameterization via string substitution", I can express this
> notion easily:
>
>
> class TreeNode{{inTree}}[T <: TreeNode[T]] {
>
> this: T =>
>
> private var parent: Option[T]
>
> private var children = new ArrayBuffer[T]
>
>
> def append{{inTree}}(child: T) {...}
>
> def nthChild{{inTree}}(position: Int): T = children(position)
>
> ...and so on...
>
> }
>
>
> class Node extends TreeNode{{InModelTree}}[Node] with
> TreeNode{{InLayoutTree}}[Node] {
>
> def doLayout {
>
> nthChildInLayoutTree(...).doSomething
>
> }
>
> ...etc...
>
> }
>
>
> The primary motivation for this is to allow writing a single
> tree-related source/test codebase, while still allowing a node to be a
> member of multiple trees. My example may not be the best--perhaps a
> class that models an in-memory database record, and needs to participate
> in multiple B-tree indices, would be a better example?
>
>
> You can think of this as either code rewriting, or a special case of the
> more general case that would allow any name in an inherited trait to be
> aliased to a new name in the inheritor, similar in concept to aliasing
> in import statements. There are certainly corner cases (for example,
> what do you do if TreeNode defines a non-private apply method?), but it
> seems to me that handling multiple inheritance of the same trait via
> some sort of renaming mechanism would be useful. It would certainly be
> useful to me right now, and I'm wondering if there is some corner of
> Scala I haven't yet explored that would allow me to do something similar?
>
>
> Thanks,
>
> Ken McDonald
>

This may be subjective and judgmental, but I would suggest never to
point up the hierarchy.
Also, if you store your children in an ArrayBuffer, it means they are
enumerated in a certain order. This is not exactly a tree, if you
impose additional structure. Even more interesting is the feature that
while a tree can be a subtree of only one tree, the same subtree can
occur more than once as the child of the same tree.

So my suggestion is not to point up, and use a Set for children.

Thanks,
-Vlad

On Sat, Apr 2, 2011 at 2:27 PM, Ken McDonald wrote:
> I don't see any way to achieve the following, but thought I would ask...
> (this might more properly belong in scala-debate, but I'd really like some
> way of doing this, so I'm posting here with hopes of getting concrete
> suggestions--hope that's OK)
>
> I've created a TreeNode trait that defines functionality allowing classes
> that inherit it from it to be correctly maintained in a tree structure:
>
> class TreeNode[T <: TreeNode[T]] {
>
>     this: T =>
>
>     private var parent: Option[T]
>
>     private var children = new ArrayBuffer[T]
>
>     def append(child: T) {...}
>
>     def nthChild(position: Int): T = children(position)
>
>     ...and so on...
>
> }
>
> (I'm typing in a simplified version of what I have so some errors may have
> crept in, but hopefully you get the idea.)
>
> However, it turns out that I'd actually like instances of TreeNode to be
> included in two different trees. If I use {{name}} notation to denote "name
> parameterization via string substitution", I can express this notion easily:
>
> class TreeNode{{inTree}}[T <: TreeNode[T]] {
>
>     this: T =>
>
>     private var parent: Option[T]
>
>     private var children = new ArrayBuffer[T]
>
>     def append{{inTree}}(child: T) {...}
>
>     def nthChild{{inTree}}(position: Int): T = children(position)
>
>     ...and so on...
>
> }
>
> class Node extends TreeNode{{InModelTree}}[Node] with
> TreeNode{{InLayoutTree}}[Node] {
>
>     def doLayout {
>
>         nthChildInLayoutTree(...).doSomething
>
>     }
>
>     ...etc...
>
> }
>
> The primary motivation for this is to allow writing a single tree-related
> source/test codebase, while still allowing a node to be a member of multiple
> trees. My example may not be the best--perhaps a class that models an
> in-memory database record, and needs to participate in multiple B-tree
> indices, would be a better example?
>
> You can think of this as either code rewriting, or a special case of the
> more general case that would allow any name in an inherited trait to be
> aliased to a new name in the inheritor, similar in concept to aliasing in
> import statements. There are certainly corner cases (for example, what do
> you do if TreeNode defines a non-private apply method?), but it seems to me
> that handling multiple inheritance of the same trait via some sort of
> renaming mechanism would be useful. It would certainly be useful to me right
> now, and I'm wondering if there is some corner of Scala I haven't yet
> explored that would allow me to do something similar?
>
> Thanks,
>
> Ken McDonald

You can think of this as either code rewriting, or a special case of the more general case that would allow any name in an inherited trait to be aliased to a new name in the inheritor, similar in concept to aliasing in import statements. There are certainly corner cases (for example, what do you do if TreeNode defines a non-private apply method?), but it seems to me that handling multiple inheritance of the same trait via some sort of renaming mechanism would be useful. It would certainly be useful to me right now, and I'm wondering if there is some corner of Scala I haven't yet explored that would allow me to do something similar?

This is related to a question I had:
if you define two methods with the same name in two different traits and you want to inherit from the two traits:- what would happen?- if the two traits are defined in different packages, what would happen?

Nicolas.

Hi Nicolas!
Did you know that scala distribution comes with a REPL? Here a random
session related to your question:
scala> trait t1 { def hello ="hi"}
defined trait t1

scala> trait t2 { def hello = "hohho"}
defined trait t2

scala> class A{}
defined class A

scala> new A() with t1 with t2
:9: error: overriding method hello in trait t1 of type =>
java.lang.String;
method hello in trait t2 of type => java.lang.String needs `override'
modifier
new A() with t1 with t2
^

scala> new A() with t1
res1: A with t1 = $anon$1@9b964

scala> new A() with t2
res2: A with t2 = $anon$1@d4bef8

hth andreas

On 3 Apr., 18:49, "nicolas.o...@gmail.com"
wrote:
> > You can think of this as either code rewriting, or a special case of the
> > more general case that would allow any name in an inherited trait to be
> > aliased to a new name in the inheritor, similar in concept to aliasing in
> > import statements. There are certainly corner cases (for example, what do
> > you do if TreeNode defines a non-private apply method?), but it seems to me
> > that handling multiple inheritance of the same trait via some sort of
> > renaming mechanism would be useful. It would certainly be useful to me right
> > now, and I'm wondering if there is some corner of Scala I haven't yet
> > explored that would allow me to do something similar?
>
> This is related to a question I had:
>
> if you define two methods with the same name in two different traits and you
> want to inherit from the two traits:
> - what would happen?
> - if the two traits are defined in different packages, what would happen?
>
> Nicolas.

The data structure will be playing a role similar to a DOM in a browser, and needs to respond to events and update very quickly in the event dispatch thread. A mutable structure that updates in response to events seems to fit the bill for this more than a purely functional approach. I am trying to keep things as functional as possible, and haven't discarded a purely functional approach, but because the tree nodes are really nodes in a fairly complex graph (the model and view structures are interleaved, and maintain parent backpointers for efficient navigation), it's hard for me to see how this could be done in a simple, functional, efficient manner.
However, I'd really love to hear suggestions...
Thanks,Ken

Hi Vlad,
On Sunday, April 3, 2011 9:41:45 AM UTC-5, Vlad Patryshev wrote:

This may be subjective and judgmental, but I would suggest never to
point up the hierarchy.

Could you be more specific about the reasons for this? I'm doing it to permit efficient navigation of a DOM-style structure, and am trying to encapsulate the logic necessary to maintain tree consistency entirely in a single, small class that will be thoroughly tested. Basically, given a node, I need to be able to quickly find the path from the tree root to it. 

Also, if you store your children in an ArrayBuffer, it means they are
enumerated in a certain order. This is not exactly a tree, if you
impose additional structure.

I've always thought of trees as having ordered children--binary trees have "left" and "right", 2-3 trees have left-middle-right, etc. But you are quite correct in that I didn't specify in the original post that I wanted ordered children--hence the use of ArrayBuffer 

Even more interesting is the feature that
while a tree can be a subtree of only one tree, the same subtree can
occur more than once as the child of the same tree.

 For simplicity I didn't show all of the code logic in my original post; whenever a node is inserted, it is first removed from any tree it might be contained in, this would include the case of being inserted back into the same tree. And all insertion/deletion is ultimately handled by a single "replace" method, which is subject to a lot of testing.
However, your note did make me realize that a single insertion might potentially cause two calls to "replace" on the same parent tree, which is important because "replace" will fire an optional update event when a tree is mutated--and it should probably be fired only once in this case. My, my, corner cases...
Your feedback is much appreciated, it makes me think :-)Ken

On Sunday April 3 2011, Vlad Patryshev wrote:
> This may be subjective and judgmental, but I would suggest never to
> point up the hierarchy.
> Also, if you store your children in an ArrayBuffer, it means they are
> enumerated in a certain order. This is not exactly a tree, if you
> impose additional structure. Even more interesting is the feature
> that while a tree can be a subtree of only one tree, the same subtree
> can occur more than once as the child of the same tree.
>
> So my suggestion is not to point up, and use a Set for children.

That's entirely infeasible for some trees. And I can add sequencing and
uniqueness to the properties that must be parameterized to create a
generic tree.

As to the linking direction, if you're implementing a search tree in
which you expand the tree at its frontier as you search for a target,
you want the tree to be linked upward so that as you abandon branches
of the tree no longer suitable to the search (because they produce no
more children), their parents are freed through ordinary GC and that
freeing is transitive up the tree.

I repeat: There are too many parameters on the characteristics of a tree
to implement a universal one.

> Thanks,
> -Vlad

Randall Schulz

On Sun, Apr 3, 2011 at 1:35 PM, Ken McDonald <ykkenmcd@gmail.com> wrote:

Hi Vlad,
On Sunday, April 3, 2011 9:41:45 AM UTC-5, Vlad Patryshev wrote:

This may be subjective and judgmental, but I would suggest never to
point up the hierarchy.

Could you be more specific about the reasons for this? I'm doing it to permit efficient navigation of a DOM-style structure, and am trying to encapsulate the logic necessary to maintain tree consistency entirely in a single, small class that will be thoroughly tested. Basically, given a node, I need to be able to quickly find the path from the tree root to it.

My view on it is this: if you are given a tree, you are given the root (or a head, if you are in Australia); navigating, you can easily store the trace in a stack and go back accordingly. A path to an element in a tree starts with its root.

If you rely on a node being at a specific position, I guess you mix the node as an object and the node's position. Nobody thinks about storing an index of a list element with that element ("for easier navigation"). What if a set could be an element of only one set, and had to point to that containing set? Set theory would be useless.
 
A well-known use case is menu item; so many times different developers found that with links back and forth they cannot share a menu item. Because it points up, and should be detached for reuse.

 

Also, if you store your children in an ArrayBuffer, it means they are
enumerated in a certain order. This is not exactly a tree, if you
impose additional structure.

I've always thought of trees as having ordered children--binary trees have "left" and "right", 2-3 trees have left-middle-right, etc. But you are quite correct in that I didn't specify in the original post that I wanted ordered children--hence the use of ArrayBuffer

But do you agree that this imposes additional structure? See, one thing is to describe a tree axiomatically, and the other is to describe it the way you build it. Then 2-3 trees are not exactly trees.
 

 

Even more interesting is the feature that
while a tree can be a subtree of only one tree, the same subtree can
occur more than once as the child of the same tree.

 For simplicity I didn't show all of the code logic in my original post; whenever a node is inserted, it is first removed from any tree it might be contained in, this would include the case of being inserted back into the same tree. And all insertion/deletion is ultimately handled by a single "replace" method, which is subject to a lot of testing.

Imagine this logic applied to a collection. An element has to be removed from a TreeSet if it is being inserted into another TreeSet.
 -Vlad