I don't know if assoc-in etc. work on the clojure.data.priority-map data structures, but your questions at least reminded me of the implementation of that data structure, which uses two maps internally to maintain the priority map, and keeps their contents consistent with each other [1]. It also implements all of the methods that regular Clojure maps do, so all normal map operations work on priority-maps, too. Its implementation may give you some ideas for one way to do what you are hoping for.
Andy [1] https://github.com/clojure/data.priority-map On Wed, Apr 20, 2016 at 10:18 AM, JvJ <kfjwhee...@gmail.com> wrote: > I had a bit of trouble fully understanding the EAV concept or the pldb > code. There's not a good overview of EAV architecture that doesn't focus > on databases. I'm not much of a DB guy. So, I'm not sure if I got the > essence of the EAV pattern with my new implementation, but here it is > anyway: > > I think the legacy of object-orientation was so embedded in my brain that > I failed to see the simple solution: rows and columns. I was thinking of > items in the map as "containers" of items, when I could have been thinking > of them as rows in a table. The table is effectively a sparse matrix. > > The implementation's main map is of type { [row col]->Item }. It also > uses two other maps: row-idx:{row->{col item}} and > col-idx:{col->{row->item}}. > > Whenever an assoc occurs on key [r c] and item i, here is how the values > are updated: > main-map<-(assoc main-map [r c] i) > row-idx<-(assoc-in row-idx [r c] i) > col-idx<-(assoc-in col-idx [c r] i) > > This way, we efficiently maintain row-idx and col-idx, two complementary > nested maps that mirror each others' structure. > > Did I get close to the EAV pattern here? Also, I wonder if this approach > is scalable to higher-dimensional tables, for instance where each item is > associated with a 3-tuple. > > On Monday, 18 April 2016 17:18:45 UTC-7, tbc++ wrote: >> >> Core.logic has one such implementation: >> https://github.com/clojure/core.logic/blob/master/src/main/clojure/clojure/core/logic/pldb.clj >> <https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fclojure%2Fcore.logic%2Fblob%2Fmaster%2Fsrc%2Fmain%2Fclojure%2Fclojure%2Fcore%2Flogic%2Fpldb.clj&sa=D&sntz=1&usg=AFQjCNGjJWdatQscPmDIx3xpBMuwPmOH7A> >> might be a place to start. >> >> On Mon, Apr 18, 2016 at 5:35 PM, JvJ <kfjwh...@gmail.com> wrote: >> >>> Can you point me to a working example of one of these structures? >>> >>> On Monday, 18 April 2016 16:30:17 UTC-7, tbc++ wrote: >>>> >>>> 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 <tbald...@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 <kfjwh...@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 clo...@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+u...@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+u...@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 clo...@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+u...@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+u...@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) >> > -- > 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. > -- 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.
