On 6 July 2012 15:42, Warren Lynn <wrn.l...@gmail.com> wrote: > Can someone help me figure out how I can have two data structures to refer > to each other in functional programing style? I mean something like double > linked list, or in a tree where each node keeps a reference to its parent > and children. What puzzles me is, as soon as you update the reference in one > node (more precisely, a new node with the updated reference is created), the > reverse reference in the other node is invalid. Thanks.
Hi Warren, That's a really interesting question. I'll give it my best shot: Suppose you have a data structure in mind consisting of (among other things) two components A and B which mutually refer to each other. As you say, if you are dealing entirely with purely functional data structures, you cannot set this up, because before you create B you must create A, and before you create A you must create B. On the other hand, if you have a constructor function which is internally impure and mutates the references of A and B to point to one another, then this is absolutely fine. The external interface of this function is still entirely pure, even if there is impure mutation happening within. (This is the same argument which justifies the use of transients -- they enable the creation of pure functions which internally mutate state for efficiency reasons.) However, there is another problem with mutual references -- they limit structural sharing. As a quick refresher, structural sharing is where two different composite values share part of their internal structure: (def tail '(b c d)) (def list-1 (conj tail 'a)) ; (a b c d) (def list-2 (conj tail 'e)) ; (e b c d) These lists have different heads, but identical tails -- the '(b c d) portion never had to be copied. In the mutual reference case, let's say you had a value with parts A and B referring to one another, and that you wanted to create a new value with a different A (say, A') but the same B. You cannot use the original B, because it refers to A and not A'; and of course you cannot mutate it to point to A' because then the original value will be affected. So you have to copy both A and B in the new value. This means that for a doubly-linked list, you cannot create a persistent version which uses structual sharing to improve performance, because any part of the list is reachable from any other. As a result, an immutable doubly-linked list must implement copy-on-write semantics. So in short, mutual references can be used in an immutable data structure, but they will not be able to achieve the efficiency of a persistent data structure. Depending on your use case for mutually-referring data structures, there are some alternatives: * If you want a list traversable in either direction, you can use a vector. Vectors support seq and rseq. * If you want an infinite data structure (say, if you were planning to join a doubly-linked list's head and tail to one another) you can use cycle to create an infinite lazy sequence instead. If you have any other use-cases, perhaps you could mention them and we could see if there are alternatives that can be found with persistent data structures. Phil -- 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
