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]

What I meant by infinite sets is that a type can be considered a set of its values. Then "subtype" means "subset", and "are disjoint" means "do not intersect". Two sets may intersect each other without either being a subset of the other.