Hi Rob, Thanks for tracking this down. If you will execute a CA [1], I would love to get a patch (with tests) that fixes this. I have created a ticket at [2] to track it.
I would prefer something along the lines of the simpler fix shown below, unless anybody pops up on this thread with a real-world use case for performance-critical underive. Stu [1] http://clojure.org/contributing [2] https://www.assembla.com/spaces/clojure/tickets/382-fix-underive-for-multiple-inheritance > As an alternative, if we're willing to rebuild the entire hierarchy, > not just the subgraph that's affected by the underivation, > we can just do this: > > (defn easy-underive [h child parent] > (let [oldParents (:parents h) > childsParents (disj (clojure.set/union #{} (child oldParents)) > parent) > newParents (if (not-empty childsParents) > (assoc oldParents child childsParents) > (dissoc oldParents child)) > derivation-seq (flatten (map #(cons (key %) (interpose (key %) (val > %))) > (seq newParents)))] > (reduce #(apply derive (cons %1 %2)) (make-hierarchy) > (partition 2 derivation-seq)))) > > It's less efficient, because it tosses out all of the information in > the ancestor and descendant sets. But it is a good deal simpler -- 10 > lines of code instead of 60 or so. For small hierarchies this would > be fine. If anyone were to make large > hierarchies which had to be modified efficiently, though, I think > something like in the first message would be required. > > On Jun 15, 4:29 pm, Rob Lachlan <robertlach...@gmail.com> wrote: >> Oh God. What broken formatting. Sorry about that. >> >> On Jun 15, 4:24 pm, Rob Lachlan <robertlach...@gmail.com> wrote: >> >> >> >>> I think that the underive function for removing hierarchy >>> relationships between keywords is broken. I'll illustrate with an >>> example and describe what I think the problems are. I've got some >>> code for a function which (I hope!) performs underive correctly, and >>> I'd love it if people had a look. >> >>> Consider a hierarchy with child-parent relationships: >> >>> :c -> :p1, :c -> :p2, :p1 -> :a1, :p1 -> :a2, :p2 -> :a2 >> >>> Which I'll illustrate with the world's worst ascii art: >> >>> a1 a2 >>> | / | >>> | / | >>> | / | >>> p1 p2 >>> | / >>> | / >>> | / >>> c >> >>> ; creating this hierarchy: >>> user> (def h (reduce #(apply derive (cons %1 %2)) (make-hierarchy) >>> [[:p1 :a1] [:p1 :a2] [:p2 :a2] [:c :p2] [:c :p1]])) >>> #'user/h >>> user> h >>> {:parents {:c #{:p1 :p2}, :p2 #{:a2}, :p1 #{:a2 :a1}}, :ancestors {:c >>> #{:p1 :p2 :a2 :a1}, :p2 #{:a2}, :p1 #{:a2 :a1}}, :descendants {:p1 >>> #{:c}, :p2 #{:c}, :a2 #{:p1 :p2 :c}, :a1 #{:p1 :c}}} >> >>> Now the underive: >> >>> user> (underive h :c :p1) >>> {:parent {:c #{:p2}, :p2 #{:a2}, :p1 #{:a2 :a1}}, :ancestors {:c >>> #{:p2}, :p2 #{:a2}, :p1 #{:a2 :a1}}, :descendants {:p1 #{}, :p2 >>> #{:c}, :a2 #{:p1 :p2}, :a1 #{:p1}}} >> >>> Problems: >> >>> Most seriously, it is incorrect: :c should still show up as a >>> descendant of >>> :a2, since :c is a child of :p2, and :p2 a child of :a2. Note that >>> the >>> parent map is correct, so it is the ancestor and descendant maps which >>> are >>> inconsistent. >> >>> Also, notice that the key for the parent map has changed from :parents >>> to >>> :parent, which causes calls to the parents function to return nil. >> >>> Also, keys which map to empty sets are left in each of the maps >>> (parents, >>> descendants and ancestors), with the result that equality tests could >>> fail >>> in some cases in which they would be true. >> >>> Potential fix, and request for code review: >> >>> I've written an underive-new function which appears to fix these >>> problems, >>> at least in the tests that I've done. >> >>> http://pastebin.com/eRiz5ihw >> >>> My approach is to identify the sets of tags in the hierarchy whose >>> ancestors >>> or descendants may be affected, remove their ancestor or descendant >>> mappings, >>> then rebuild them. In a call (underive h child parent), the child and >>> all >>> the child's descendants will need to have their ancestor mappings >>> fixed. >>> Similarly, the parent and all of the parent's ancestors will need to >>> have >>> their descendant mappings rebuilt. >> >>> (As an aside, the problem here is that our hierarchy can be a DAG >>> rather >>> a tree, because multiple inheritance is allowed. And therefore, for >>> any >>> ancestor/descendant relationship it's comparatively expensive to >>> determine >>> whether a particular parent-child edge is essential or not.) >> >>> Next, the two sets of interest (child + child's descendants, and >>> parent + >>> parent's ancestors) are sorted topologically. For the child + >>> child's >>> descendants, we can now rebuild the ancestor mappings by taking a tag >>> from >>> the top of the set, setting its ancestors to the union of tag's >>> parents and >>> parents' ancestors, and repeating the process on the next tag in >>> topologically >>> sorted order until all tags are consumed. The parent + parent's >>> ancestors >>> can be done in a similar way, except that a children function is >>> required, and >>> the tags must be topologically sorted in the reverse direction. >> >>> Some remarks: >> >>> An alternative approach would be to just recompute the whole ancestor >>> and >>> descendant maps for the whole hierarchy. This would be simpler, but >>> for >>> large hierarchies would be unnecessarily expensive. >> >>> The topological sort function which I wrote avoids recursion. If we >>> wanted >>> to allow multiple recursion, it could be simplified a bit, but I >>> wanted to >>> avoid stack consumption. >> >>> Anyway, I'd appreciate any suggestions and criticisms, since this is >>> the >>> first clojure code of mine that anyone has looked at. > > -- > 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 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
