Core.logic has one such implementation: https://github.com/clojure/core.logic/blob/master/src/main/clojure/clojure/core/logic/pldb.clj might be a place to start.
On Mon, Apr 18, 2016 at 5:35 PM, JvJ <kfjwhee...@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 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) -- 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.
