Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>In Mathematica, most of what you do is based on expressions. Expressions naturally have the tree structure. For depth-first traversals (which are probably most common), you can then use functions like <code>Scan</code>,<code>Map</code>, <code>Cases</code> etc. The difference w.r.t the more traditional languages is that there is no simple way to preserve the identity of individual node in an expression tree, since there are no pointers in Mathematica. Also, many operations on expressions that are idiomatic in Mathematica would copy the entire expression when you only need to modify it in a few places, because expressions are immutable.</p> <p>Using immutable Mathematica expressions as trees still has several advantages. One is that, because they are immutable, it is easy to understand what they store by just looking at them (state and behavior are not mixed). Another is that there are efficient and generic functions such as <code>Map</code>, <code>MapIndexed</code> or <code>Scan</code>, that traverse them. For example, the visitor design pattern is <a href="http://norvig.com/design-patterns/" rel="nofollow noreferrer">invisible</a> - it is just <code>Map[f,tree,Infinity]</code>, built into the langauge. Also, there are built-in functions such as <code>Cases</code>, <code>Replace</code>, <code>ReplaceAll</code>, etc, which allow one to write very concise and declarative code to destructure trees, find pieces of trees with certain syntax or satisfying some condition, etc. Since trees are not restricted to only be built from lists and be built from different heads, one can effectively use this to write very concise tree-processing code. Finally, a freedom to very easily build any tree structure you want makes it much easier to perform experiments and prototype things, in the spirit of <a href="http://www.paulgraham.com/progbot.html" rel="nofollow noreferrer">exploratory and bottom-up programming</a>, which shortens the development cycle and ultimately leads to better designs.</p> <p>That said, you can certainly implement "stateful" (mutable) tree data structure. The real reason it has not been done yet generally is, I suspect, the performance hit associated with building, modifying and traversing such a tree, since it will undergo a full symbolic evaluation process at every step (see <a href="https://stackoverflow.com/questions/4721171/performance-tuning-in-mathematica/4723969">this</a> post for more details on that). For 2 examples of how, for example, a binary search tree can be used in Mathematica context for pretty efficient code, see my posts <a href="https://stackoverflow.com/questions/5018252/a-variation-of-integerpartition/5019949#5019949">here</a> (generic symbolic setting) and <a href="https://stackoverflow.com/questions/5246330/delete-repeating-list-elements-preserving-order-of-appearance/5251034#5251034">here</a> (in the context of Compiled code). For general ways to construct data structures idiomatically in Mathematica, I recommend books of Roman Maeder: "Programming in Mathematica", "Mathematica programmer I&amp;II", and especially "Computer Science in Mathematica". In the latter he has a detailed discussion of how to implement binary search tree in Mathematica. <em>EDIT</em> As @Simon mentioned, the talk of @Daniel Lichtblau is also a great resource, which shows how to build data structures and make them efficient.</p> <p>Regarding general ways to implement data structures in Mathematica which would incorporate some state, here is a simple example extracted from my post in <a href="http://groups.google.com/group/comp.soft-sys.math.mathematica/browse_thread/thread/ec4958c35f99758d/" rel="nofollow noreferrer">this</a> Mathgroup thread - it implements a "pair" data structure.</p> <pre><code>Unprotect[pair, setFirst, getFirst, setSecond, getSecond, new, delete]; ClearAll[pair, setFirst, getFirst, setSecond, getSecond, new, delete]; Module[{first, second}, first[_] := {}; second[_] := {}; pair /: new[pair[]] := pair[Unique[]]; pair /: pair[tag_].delete[] := (first[tag] =.; second[tag] =.); pair /: pair[tag_].setFirst[value_] := first[tag] = value; pair /: pair[tag_].getFirst[] := first[tag]; pair /: pair[tag_].setSecond[value_] := second[tag] = value; pair /: pair[tag_].getSecond[] := second[tag]; Format[pair[x_Symbol]] := "pair[" &lt;&gt; ToString[Hash[x]] &lt;&gt; "]"; ]; Protect[pair, setFirst, getFirst, setSecond, getSecond, new, delete]; </code></pre> <p>Here is how you could use it:</p> <pre><code>pr = new[pair[]]; pr.setFirst[10]; pr.setSecond[20]; {pr.getFirst[], pr.getSecond[]} {10, 20} </code></pre> <p>Creating a list of new pair objects :</p> <pre><code>pairs = Table[new[pair[]], {10}] {"pair[430427975]", "pair[430428059]", "pair[430428060]", "pair[430428057]", "pair[430428058]", "pair[430428063]", "pair[430428064]", "pair[430428061]", "pair[430428062]", "pair[430428051]"} </code></pre> <p>Setting the fields :</p> <pre><code>Module[{i}, For[i = 1, i &lt;= 10, i++, pairs[[i]].setFirst[10*i]; pairs[[i]].setSecond[20*i];]] </code></pre> <p>Checking the fields :</p> <pre><code>#.getFirst[] &amp; /@ pairs {10, 20, 30, 40, 50, 60, 70, 80, 90, 100} #.getSecond[] &amp; /@ pairs {20, 40, 60, 80, 100, 120, 140, 160, 180, 200} </code></pre> <p>In the post I mentioned there is a more detailed discussion. One big problem for "objects" created in this way is that there is no automatic garbage collection for them, which may be one of the major reasons why OOP extensions implemented in top-level Mathematica itself did not really take off.</p> <p>There are several OOP extensions for Mathematica, such as the <code>classes.m</code> package by Roman Maeder (the source is in his "Mathematica Programmer" book), the <code>Objectica</code> commercial package, and several others. But until Mathematica itself would provide efficient mechanisms (perhaps based on some kind of pointer or reference mechanism) for building mutable data structures (if this ever happens), there will probably be a large performance hit associated with top-level implementations of such data structures in mma. Also, since mma is based on immutability as one of the core ideas, it is not very easy to make mutable data structures fit well with other idioms of Mathematica programming.</p> <p><strong>EDIT</strong> </p> <p>Here is a bare-bones stateful tree implementation along the lines of the example above:</p> <pre><code>Module[{parent, children, value}, children[_] := {}; value[_] := Null; node /: new[node[]] := node[Unique[]]; node /: node[tag_].getChildren[] := children[tag]; node /: node[tag_].addChild[child_node, index_] := children[tag] = Insert[children[tag], child, index]; node /: node[tag_].removeChild[index_] := children[tag] = Delete[children[tag], index]; node /: node[tag_].getChild[index_] := children[tag][[index]]; node /: node[tag_].getValue[] := value[tag]; node /: node[tag_].setValue[val_] := value[tag] = val; ]; </code></pre> <p>Some examples of use:</p> <pre><code>In[68]:= root = new[node[]] Out[68]= node[$7] In[69]:= root.addChild[new[node[]], 1] Out[69]= {node[$8]} In[70]:= root.addChild[new[node[]], 2] Out[70]= {node[$8], node[$9]} In[71]:= root.getChild[1].addChild[new[node[]], 1] Out[71]= {node[$10]} In[72]:= root.getChild[1].getChild[1].setValue[10] Out[72]= 10 In[73]:= root.getChild[1].getChild[1].getValue[] Out[73]= 10 </code></pre> <p>For one non-trivial example of use of this mutable tree data structure, see <a href="https://stackoverflow.com/questions/6138540/code-manipulation-via-interactive-tree-for-mathematica/6140400#6140400">this</a> post of mine. It also confronts this method with the one more heavily reusing Mathematica native data structures and functions, and illustrates well the points discussed at the beginning of this post.</p>
    singulars
    1. This table or related slice is empty.
    1. POTree data structure in Mathematica
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USLeonid Shifrin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POTree data structure in Mathematica
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you, Leonid for this fast and extensive answer. I will try to get the literature you mentioned. I have played with Roman Maeder's OO package last year but for now that is off-topic.
      singulars
      1. PO
      1. USnilo de roock
    2. COThank you, Leonid for this fast and extensive answer. I will try to get the literature you mentioned. I have played with Roman Maeder's OO package last year but for now that is off-topic. Anyway: Sofar I have functions for NewTree NewNode AddAsChild AddAsSibling Traverse A node is then a list with {Id, Object, Previous, Parent}. I go through the literature first.
      singulars
      1. PO
      1. USnilo de roock
    3. COI added a bare-bones implementation of stateful tree in the edit, along the lines of my <pair> example - may be you may find this useful.
      singulars
      1. PO
      1. USLeonid Shifrin
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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