The idea of the selection constraint is based on the
intuitive notion of selecting the Ith element out of a
sequence of values. Abstractly, we might write this as
follows:
X = <V1 ... Vn>[I]
However, this is more than just:
X = {Nth [V1 ... Vn] I}
because it is intended to function as a constraint: all of
X, V1, ..., Vn, and
I can be variables (e.g. finite set variables). In
particular, constraining X should restrict the values
that I may take to only those positions in 1..n
corresponding to elements Vk that are not yet
inconsistent with X. Conversely, if all elements that
may still be selected by I have a basic constraint in
common, the latter should be propagated to V. This
lifting of common information is a form of constructive
disjunction.
As of version 1.3, this package also provides the selection
union constraint:
S = U<S1 ... Sn>[SI]
where SI is a set variable of indices. Its declarative
semantics is that S is the union of the sets
Si for all i in SI.
As of version 1.5, this package also provides the selection
intersection constraint:
S = &<S1 ... Sn>[SI]
where SI is a set variable of indices. Its declarative
semantics is that S is the intersection of the sets
Si for all i in SI.
As of version 1.6, this package provides the sequenced union
constraint:
S = (<<U)<S1 ... Sn>
where S is the union of the sets Si which are
additionally constrained to be sequential, i.e. for
i<j all elements of Si are smaller than
elements of Sj.
Version 1.8 - added indexed union constraint:
S = IU<(I1,S1) ... (In,Sn)>[SI] which returns the union of
the Sk for Ik in SI.
This package implements the selection constraint for homogenous
vectors of finite domains or of finite sets, and the selection union
constraint. It is available as a
module that exports features fd, fs,
and union:
import Select(fd fs union) at 'x-ozlib://duchier/cp/Select.ozf'
{Select.fd L I D}
L must be a vector (list, tuple, record) of
integers and/or finite domain variables. I and
D are nestable and will be constrained to finite domain
variables if necessary.
{Select.fs L I S}
L must be a vector of finite set values or
variables. Again, I and S are nestable
and will be constrained respectively to a finite domain variable and
a finite set variable if necessary.
{Select.union L SI S}
L must be a vector of finite set values or
variables, SI a set value/variable selecting positions
in L. Both SI and S are
nestable.
{Select.inter L SI S}
L must be a vector of finite set values or
variables, SI a set value/variable selecting positions
in L. Both SI and S are
nestable.
{Select.seqUnion L S}
S is the union of the Si in
L. Furthermore the Si are constrained to
be sequential, i.e. for i<j, all elements of
Si must be smaller than elements of Sj.
{Select.indexedUnion L SI S}
L is either a list of Ik#Sk where
Ik is an integer and Sk is a FS variable,
or a record mapping features Ik to values
Sk. S is constrained to be the union of
the Sk for k in SI.
As of version 1.5, the Select module also exports
features fdom and fset to distinguish
between constraints according to the type of the sequence:
{Select.fdom.nth L I J}
{Select.fset.nth L I S}
{Select.fset.union L SI S}
{Select.fset.inter L SI S}
{Select.fset.seqUnion L S}
{Select.fset.indexedUnion L SI S}
Here is an example to help clarify what the selection constraint can
do for you. Let's import the module implementing the selection
constraint:
declare [Select]={Module.link ['x-ozlib://duchier/cp/Select.ozf']}
Now we create 3 sets S1, S2,
S3, and an index I ranging from 1 to 3 to
select one of them. S1 contains just 5, S2
contains 1 and 21, and S3 contains 1 and 77:
declare
S1 = {FS.value.make [5]}
S2 = {FS.value.make [1 21]}
S3 = {FS.value.make [1 77]}
I I::1#3
Now we define S to be the Ith element of the
sequence of finite sets [S1 S2 S3]:
declare S = {Select.fs [S1 S2 S3] I}
Using Show, here is what is currently known about
S and I:
S{{}..{1 5 21 77}}#{1#2}
I{1#3}
Thus it is already known that S can have at most as
elements integers 1, 5, 21 and 77; i.e. this information has been lifted
to S. Now let's explicitly remove element 5:
{FS.exclude 5 S}
Now, here is what is known:
S{{1}..{1 21 77}}#2
I{2 3}
In other words, it has been noticed that I=1 would be
inconsistent, thus this value has been removed from the domain of
I. Furthermore S is now known to contain 1
and maybe 21 and 77. It is known to contain 1 because only
S2 and S3 remain as possibilities and both
contain 1.
Starting 5 Oct 2001, this contribution is only distributed as an
ozmake --install --package=duchier-select.pkg
If this package was already installed on your computer and you want to
upgrade to a newer version, invoke:
ozmake --upgrade --package=duchier-select.pkg
or else