Let's assume for the moment that you do in fact absolutely need some sort
of "bidirectional" querying of the data. In other words, from a parent you
need to get to the child, and from the child you need to get to the
parent. There's no way to accomplish this with immutable data structures
without introducing some level of indirection.
Option 1:
Code it the way you'd code a pointer-based version, but use refs as your
"pointers". Advantage over coding in Java with raw pointers is that you
can use the STM to change a bunch of "pointers" in one transaction.
Option 2:
Store in your immutable data structure a mapping from unique names to
nodes. These names are your "pointers". Nodes refer to other parent and
children nodes by their names. For example, store the tree like so:
{"Node1" {:parent nil :children ["Node2" "Node3"]}
"Node2" {:parent "Node1" :children []}
"Node3" {:parent "Node1" :children []}}
Looking up a name in that map corresponds to the notion of dereferencing
your pointer.
In pointer-based code, you generally pass the pointers as arguments to
functions. Similarly, with this approach you'd tend to write your API to
take and return names.
The main downside versus a pointer or ref version of the code is that all
queries to find a parent or child must take as parameters not only the name
of the node in question, but the whole mapping of names to nodes. Finding
a parent, for example, is a two step process. Lookup the name in the map,
and then you have the actual structure you need to find the name of the
parent. You can encapsulate that, of course, in an api, for example:
(get-parent name-to-node-map name) -> returns name of parent.
The advantage of this representation is that you have one immutable entity
representing the whole tree, and it is therefore trivial to save different
versions and states of the tree in its entirety. This is the way I usually
do it.
Option 3:
Rather than thinking of it as a tree, think of it as a directed graph.
There is one type of link from parent to child, and another type of link
from child to parent. This way of thinking makes it easy to leverage
existing graph technologies that can be easily accessed from Clojure, for
example, http://titanium.clojurewerkz.org/.
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
