Hi Stuart, I'll be mailing the agreement later today, and I'll work on a patch shortly. I've noticed that the unit tests file for multi-methods, where tests for derive and underive would be located, is essentially empty. So I thought I might put some tests in there for isa, parents, ancestors, etc. while I'm about it.
I take your point on preferring a simpler version. I have a feeling that: -most people are using the global hierarchy -most people are using the hierarchy essentially statically which is a bit of a shame, since the hierarchy system is quite powerful. With independent hierarchies, you can confidently juggle several hierarchy relationships, and dynamically update them. I think their uses go beyond multi-methods. But for hierarchies which are largely static, and which will rarely underive, a simpler underive in core will be good. I'll probably put my complicated version together with some other convenience functions for hierarchies in a library of my own, in case anyone has a need for it. Rob p.s. Loved the book. On Jun 16, 7:54 am, Stuart Halloway <stuart.hallo...@gmail.com> wrote: > 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-... > > > > > 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
