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]

Also: "disjoint?" is not transitive, it's symmetric. But subtypes of disjoint types are also disjoint. (I think you already came to the same conclusion.)