Databases
StackOverflow2013
Postsdbo
POHow to implement a generic hierarchy of structures with injected functionality
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to implement a generic hierarchy of structures with injected functionality
    text
    copied!<p>I want to implement a generic hierarchy for tree structures, which can later be used in an implementation-independent way to describe generic algorithms over trees.</p> <p>I started with this hierarchy:</p> <pre><code>interface BinaryTree&lt;Node&gt; { Node left(Node); bool hasLeft(Node); Node right(Node); bool hasRight(Node); } interface BinaryTreeWithRoot&lt;Node&gt; : BinaryTree&lt;Node&gt; { Node root(); } interface BinaryTreeWithParent&lt;Node&gt; : BinaryTree&lt;Node&gt; { Node parent(Node); bool hasParent(Node); } </code></pre> <p>Now, basically I want to be able to implement the concept of a subtree in a universal way: For each class T : BinaryTree, I want a 'class' Subtree(T) which provides the same functionality of T (so it must derive from it), and also rewrites the root() functionality.</p> <p>Something like this:</p> <pre><code>class Subtree&lt;T, Node&gt; : T, BinaryTreeWithRoot&lt;Node&gt; where T : BinaryTree&lt;Node&gt; { T reference; Node root; void setRoot(Node root) { this.root = root; } override Node BinaryTreeWithRoot&lt;Node&gt;::root() { return this.root; } // Now, inherit all the functionality of T, so an instance of this class can be used anywhere where T can. forall method(arguments) return reference.method(arguments); } </code></pre> <p>Now with this code I'm not sure how to create an object of type subtree, since the tree object should in some way be injected.</p> <p>One approach is to create a subtree class for each tree class i create, but this means code duplication, and, after all, its the same thing.</p> <p>So, one approach to this is mixins, which allow a generic class to derive from its template parameter.</p> <p>I'm also interested how such a hierarchy can be implemented in Haskell, since Haskell has a great type system and I think it will be easier to inject such functionality.</p> <p>For example in Haskell it may be something like:</p> <pre><code>class BinaryTree tree node where left :: tree -&gt; node -&gt; node right :: tree -&gt; node -&gt; node class BinaryTreeWithRoot node where left :: tree -&gt; node -&gt; node right :: tree -&gt; node -&gt; node -- but this is a duplication of the code of BinaryTree root :: tree -&gt; node instance BinaryTree (BinaryTreeWithRoot node) where left = left right = right data (BinaryTree tree node) =&gt; Subtree tree node = ... instance BinaryTreeWithRoot (Subtree tree node) where ... </code></pre> <p>I'm interested if and how this can be done in within an oop language (c++,c#,d,java), as c++ and d provide mixins out of the box (and i'm not sure for d), and out of curiosity with the Haskell type system.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload