🚀 go-pugleaf

I need to represent sets of constants (from some small, known domain)
as terms in such a way that unification of two such terms yields the
intersection of their corresponding sets.

Chris Mellish told me of a trick attributed, in Prolog folklore, to
Colmerauer, whereby a subset of N values is denoted by a list of N+1
variables, each adjacent pair corresponding to one possible element.
Iff a pair share, that element is not in the subset.

It is necessary to maintain a mapping between domain values and list
positions, but the whole affair can/should be packaged as an abstract
data type.  Further folklore: if you bind the first variable to 0,
and the last to 1; then disjoint subsets will fail to unify.

No doubt this is in "The Craft of Prolog", which I _still_ haven't
bought, or even read much of, but can anyone cite an original or early
appearance of this trick?

I have generalised it to domains which may grow after some
subsets have already been denoted: one way is to leave each list
somewhat unbound at its tail, and a more ambitious variation uses
sparse binary trees which should be more efficient for small subsets
of large domains.  Dare I claim originality for these in my thesis?

Sorry if this description is only intelligible to those who already
know what I am writing about.  If there is interest, I will post some
code (unless someone else gets in first :-).
----
  __   __    Paul Singleton (Mr)           JANET: paul@uk.ac.keele.cs
 |__) (__    Computer Science Dept.        other: paul@cs.keele.ac.uk
 |  .  __).  Keele University, Newcastle,    tel: +44 (0)782 621111 x7355
             Staffs ST5 5BG, ENGLAND         fax: +44 (0)782 713082