>
> 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.
The sharing only concerns data structure having the same creation
point.
As Achim explained, better than me:
user> (identical? (cons 1 nil) (cons 1 nil)) false
In some sense, it corresponds to:
user> (def hcons (memoize cons))
#'user/hcons
but is not limited to consing.
In this sense, it acts more as:
user> (def hidentity (memoize identity))
Which is a bit more generic but less good for GC (it builds a structure
and release it just after the call to hidentity).
Creating specialized functions like hcons might be interesting too.
> I'm interested in knowing how you solve garbage collection issues ?
The main difference with that is how it hanldes GC. The table is a
concurrent hash table whose keys are references to the objects and
values are Soft/Weak references to a HashConsed object.
This HashConsed has a reference to the initial object and is the thing
you want to hold too if you want sharing to work.
When it is finalized, it removes its entries from the hash table, after
some checks (to see it still owns this entry).
> 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 ...
I was thinking of doing something more coarse-grained, for list or
trees. Where these complexed structures (vectors, set, map) are thought
atomic and not hashed incrementally.
(I would be happy to do otherwise, but it seems quite complicated.)
Example of use to create, for example, a tree:
(hash-cons {:head :a :children {set of hash consed nodes}})
This hashing is done in O(num of children), and then you get back a
HashConsed structure, that is shared for all hash consed instances
of the same tree. It can be used to test equality O(1), with identical?,
and not O(size of the tree).
Hashing is done in O(1) too.
Of course, incremental hash consing of sets/map/vectors could give us
adding/removing a children in a better time than O(num of children) but
I don't have much clue on how to do that. Any ideas?
Best,
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
-~----------~----~----~----~------~----~------~--~---
