The general technique in lisp is called hash consing (a.k.a. flyweight
pattern, a.k.a. interning). Java strings, clojure symbols, and keywords
are interned. And small integers, apparently.
The basic idea is to create memoized versions of all the data constructors
and only use them. This is basically what you did in your example and what
Gary suggested. So, if you truly wanted something general, you'd probably
have to reimplement a lot of clojure.core, or restrict yourself to a small
number of constructor fns.
If the vectors in your example are the only composite structure that needs
sharing, and they represent points, say:
(def mk-point (memoize (fn [x y] [x y]))) ; obviously lots of options here
(caching strategy, weak refs)
(def m1 {:a (mk-point 1 2)})
(def m2 (assoc m1 :b (mk-point 1 2)))
(identical? (m2 :a) (m2 :b)) ; => true
If the maps themselves need to be shared, you'll have to make your own
version of assoc, dissoc, maybe conj & into, etc etc, and remember to
always use them. It could get complicated.
--Leif
On Saturday, May 3, 2014 10:27:29 PM UTC-4, Mike Fikes wrote:
>
> Are there common techniques or idioms for achieving structural sharing
> when composing data where equivalences exist?
>
> (My motivation is to reduce heap usage for a particular problem I'm
> working on that involves a lot of repeated data.)
>
> As a specific example, consider sharing equivalent map values:
>
> (def m1 {:a [1 2]})
>
> (def m2 (assoc m1 :b [1 2]))
>
>
> (identical? (m2 :a) (m2 :b))
>
> ;; => false
>
>
> For this simple example, I can force sharing by introducing a variant of
> assoc which looks at existing values:
>
>
> (defn assoc-id [map key val] (assoc map key (get (apply hash-set (vals
> map)) val val)))
>
>
> And using it results in a map with two identical values:
>
>
> (def m3 (assoc-id m1 :b [1 2]))
>
>
> (identical? (m3 :a) (m3 :b))
>
> ;; => true
>
>
> But, of course, this approach could get to be expensive and/or unwieldy if
> not done carefully.
>
>
> So, I was wondering if there are general techniques in this area. I'm sure
> I'm not the first to come across it. We already get this automatically
> for boxing of small integers:
>
>
> (identical? 5 5)
>
> ;; => true
>
>
> (identical? 500 500)
>
> ;; => false
>
>
> So I suppose I'm essentially looking for the same idea but for larger
> non-primitive "values".
>
>
>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
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 [email protected].
For more options, visit https://groups.google.com/d/optout.
