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
