There's an overview of several approaches to the problem here:
http://okmij.org/ftp/Scheme/parent-pointers.txt
On Mon, Sep 9, 2013 at 4:37 PM, Mark Engelberg <mark.engelb...@gmail.com>wrote:
> 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.
>
--
Ben Wolfson
"Human kind has used its intelligence to vary the flavour of drinks, which
may be sweet, aromatic, fermented or spirit-based. ... Family and social
life also offer numerous other occasions to consume drinks for pleasure."
[Larousse, "Drink" entry]
--
--
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.
