And by "fairly common these days", I mean that I run into this sort of structure a lot in clojure with anything that is trying to logic or query operations. Probably isn't that common outside of projects in that domain.
On Mon, Apr 18, 2016 at 5:28 PM, Timothy Baldridge <tbaldri...@gmail.com> wrote: > assoc-in is defined in terms of assoc: > https://github.com/clojure/clojure/blob/clojure-1.7.0/src/clj/clojure/core.clj#L5901 > > And this structure is fairly common these days, it's basically a index of > tuples [e a v], and you're creating a eav index and then an av index. > Datomic does this same sort of thing, for the datom [e a v t] it creates > indices for :eavt :avet and a few others that escape my memory at the > moment. > > On Mon, Apr 18, 2016 at 5:08 PM, JvJ <kfjwhee...@gmail.com> wrote: > >> I'm implementing a map data structure where most of the values are maps >> or sets, and these values can be cross-indexed by the keys they contain. I >> don't know if it already has a name, but I'm calling it a cross-map. It's >> similar to a two-way map, but they're not the same thing. >> >> For instance, a common operation would be something like "give me all >> values of this map that contain the key :a." >> >> In order to do this efficiently, I'm maintaining a second map that maps >> keys in the values of the main map to keys of the main map whose values >> contain that key. >> >> If that sounds confusing, consider this: >> main-map: >> {:foo {:a 1 :b 2} :bar {:a 2 :c 4} :baz {:b 3 :c 5}} >> >> Corresponding cross-indices: >> {:a #{:foo :bar} :b #{:foo :baz} :c #{:bar :baz}} >> >> As you can see, each key maintains references to those entries where it >> is found. >> >> When a nested update occurs that adds an entry to one of the main map's >> values, the efficient thing to do would be to simply conj that new key onto >> its corresponding cross-index set. >> >> However, I am trying to implement this as a clojure IPersistentMap, and >> the only method I can override is assoc, not assoc-in. >> >> Using regular assoc, I would have to compare the old value's keys to the >> new value's keys and find the set difference of the two, which is not an >> O(1) operation. >> >> Is there any way to override the behaviour of nested associations or >> updates? >> >> Thanks >> >> -- >> 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/d/optout. >> > > > > -- > “One of the main causes of the fall of the Roman Empire was that–lacking > zero–they had no way to indicate successful termination of their C > programs.” > (Robert Firth) > -- “One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.” (Robert Firth) -- 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/d/optout.
