Hi! I think it’s basically a generalized version of this:
user> (def hcons (memoize cons)) #'user/hcons user> (identical? (cons 1 nil) (cons 1 nil)) false user> (identical? (hcons 1 nil) (hcons 1 nil)) true In the case of cons, every two equal (value-wise) data structes have the same "construction history", thus memoizing cons would make them object-identical. I wonder how this can be leveraged for the remaining data structures though. Vectors, sets and maps don't have construction histories unique to their values ... Kind regards, Achim Am 29.06.2009 um 13:11 schrieb Parth: > On Jun 29, 3:09 pm, Nicolas Oury <nicolas.o...@gmail.com> wrote: >> Dear all, >> >> I am coding a (very) small hash consing library for clojure. >> >> For those we don't happen to know what hash consing is, it is a way >> of >> allowing equal data structures to be shared in memory. >> This leverages the purity (as in "immutability") of data structures >> to >> reduce memory footprint (no duplication of data for just a constant >> overhead per allocation) and makes hashing and equality tests faster. >> (You can use java non overloaded hashCode, and == to test equality, >> because of the sharing. So both operations are O(1), with a very >> small >> constant, whatever is the complexity of the hash consed data >> structures.) > > I don't know anything about hash consing. Based on my > limited understanding of the description I am just wondering > if this is different from structural sharing that Clojure collections > have. > > Quoting the docs[1]: > " > In particular, the Clojure collections support efficient creation of > 'modified' > versions, by utilizing structural sharing, and make all of their > performance > bound guarantees for persistent use. > " > > Do you have something different in mind with hash consing? > > Regards, > Parth > > [1] http://clojure.org/data_structures#toc12 > >> This can then be used, in combination with referential transparency >> to >> make memoized function faster. >> >> I have a java file and a clojure interface that seem to work, at >> least >> on my example. I plan to put something somewhere someday, but before >> spending too much time in making this releasable, i Have a few >> questions: >> >> - does something already exists in contrib that I have missed? >> - is someone else working on that? >> - are there any "features that I need and that you must implement" >> that >> you think of? >> >> My current plans are: >> - using a java concurrent hash map to soft referenced objects for the >> hash consing table. >> - only two fields in an hash consed object: the value it represents, >> and a generic field called "cached_data" used to store anything you >> want to memoize about this data structure. (Keeping this cached >> data a >> bit longer is the reason I plan to use soft references and not weak >> references) >> >> I am not a clojure expert and I am not a java coder at all, so don't >> hesitate to tell me if my plans are somehow wrong. >> >> Bets regards, >> >> Nicolas. > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
