Programming puzzle: disjoint types

[dougo]

I'm having some sort of mental block. I need to implement these procedures:

(declare-subtype type1 type2) ;; declares that type1 is a subtype of type2
(declare-disjoint types) ;; declares that all types in the list are disjoint
(disjoint? type1 type2) ;; true iff type1 and type2 are disjoint

For example, if I call these:
(declare-subtype A B)
(declare-subtype B C)
(declare-subtype D E)
(declare-subtype E F)
(declare-disjoint (list C F))

then these should all return true:
(disjoint? A D)
(disjoint? A F)
(disjoint? C D)
(disjoint? B E)
etc.

Anyone want to give this a shot? I'm implementing it in Scheme (if you couldn't tell from the syntax), but I'll take anything, even pseudo-code. When I say efficient, I don't mean it should compute the whole disjointness matrix after each declaration, just that it shouldn't make more table lookups than it needs to. This should be pretty easy, but like I said I have some sort of mental block today and can't figure out a reasonable solution.

If you want to take up the challenge, thanks! Let me know if any part of this is unclear.

Comments

[dougo.livejournal.com]

That's right.

[dougo.livejournal.com]

Dude, you rule! Thanks. I'm deep into something else right now, but I'll look into this in more detail tomorrow. Two quick comments:

(descendent-type? X X) should be true also. This is probably obvious, but I can't immediately tell if your pseudo-code accounts for this.

DFS isn't any more expensive than walking up parent pointers, they're both O(E) where E is the number of subtype declarations (E because they're edges in the dag). (Well, DFS needs a mark table, but that's a negligible amount of space compared to the other optimizations you mention.)