RE: [boost] discrete_set class

From: David Bergman (davidb_at_[hidden])
Date: 2002-08-27 14:10:02

Rich,

I am not saying that you have a "bad" set. In fact, your type is a very
versatile and useful one. And, admittedly, the Pascal Set type was not
the best example, since that too is bounded... 

And, you hit the point:

        "Neither std::set<>, no Pascal's set of, implement a "universal
set." "

Exactly! But yours do, which is good. But programmers have to realize
that they are dealing with selections (or constraints) with regards to a
finite domain. And, that realization could lead to further useful
operations, such as (pardon the syntax bending...)

        typedef domain<1, 9> digits;

        constraint<digits> evenNumbers(2,4,6,8);
        constraint<digits> prime(2);
        constraint_variable<digits> n;
        for_each((evenNumbers & !prime) -> n)
                std::cout << n; // For each even number not being a
prime...

There is syntax to be borrowed from the FP community, as done in other
Boost libraries. Such as the list comprehensions from Haskell:

        [ exp | cond1, ..., condn]

Or

        n <- exp.

As suggested elsewhere, one would need to replace the "<-" by "<" or the
reverse, "->", which could then alternatively be interpreted as "set
membership" or "generated by". I tend to view your sets as constraints
or generators...

One would then have (I reverse the arrow):

        (evenNumbers & prime) -> n
         
Again, your type is not less in any aspect than the Pascal Set. Neither
is it less powerful than STL set for the kind of applications where
"small sets" are wanted, in which case the generic traversal proposed by
the iterator pattern might not be the preferred variant.

I.e., I am actually defending your type against "STL comparisons", by
trying to lure the programmers out of the "programmers' set" mindset.

What I could do is to detail a possible extension of your set to a
Finite Domain Constraint system, but that is probably totally
uninteresting as a development tool, and might not meet the low-level
efficiency demands of Boost.

Regards,

David

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of spamjunk_at_[hidden]
Sent: Tuesday, August 27, 2002 2:29 PM
To: boost_at_[hidden]
Subject: RE: [boost] discrete_set class

There is no order requirement to discrete_set, ie Set(e1, e2, e3, e4) ==
Set(e3, e4, e2, e1) is true.  The discrete set is just as versatile as
the Pascal Set. 
Pascal's set is only allowed for ordinal (integral) types.  As with the
Pascal Set, mine will work correctly with int, char, enums.  You can
define a set of {'A'..'Z'} if you want to.  Neither std::set<>, no
Pascal's set of, implement a "universal set."  I cannot make a
std::set<int> and ask about membership of a float or some class X.  As
with discrete_set, std::set and the Pascal set are restricted to
elements in the domain it was defined for.

> Rich,
> 
> Mathematically it is obviously a set (although ordered), I was more 
> worried about programmer's conception of a set, such as the STL set 
> (which is not an unstructured set..), Pascal's set etc. All those 
> concepts are open, in that any element of the correct type (where type

> is different from a simple, often short, enumeration) can be added. 
> Thus, there is no "universal set" embedding all possible sets.
> 
> Your construct does have a universal superset, and is in that case 
> bounded (more than discrete, which holds for most (or all if you are
> bit-inclined) computer set concepts).
> 
> Thus, your "discrete_set" type is more aligned with the "domain" and 
> "constraint" concepts found in (Finite Domain) Constraint Programming.
> 
> I do not want people to expect the common set properties from your 
> type, since your set is more of a "selection" (or constraint, if one 
> prefers that nomenclature) of/on a finite "domain". If programmers get

> the right mindset, your type is an extremely valuable addition to 
> Bosst.
> 
> /David
> 
> -----Original Message-----
> From: boost-bounces_at_[hidden] 
> [mailto:boost-bounces_at_[hidden]] On Behalf Of 
> spamjunk_at_[hidden]
> Sent: Tuesday, August 27, 2002 1:07 PM
> To: boost_at_[hidden]
> Subject: RE: [boost] discrete_set class
> 
> 
> David:
> 
> Pardon my ignorance, as my degrees are not in math.  Other than a 
> restriction on the element type, in what ways is this not a set.
> 
> 
> Regards,
> 
> Rich Herrick
> 
> 
> > People are thinking about your construct as a set, which is "open" 
> > in
> > its nature.
> > 
> > I suggested to borrow some terms and ideas from the area of Finite
> > Domain Constraint-solving. That proposal was apparently ignored, due

> > to the introduction of unknowns and overall whimsical appearance ;-)
> > 
> > I think that using terms like "domain" or "finite_domain" with the
> > semantics from Constraint solving would clarify that this construct,

> > although being extremely useful, is not a regular "set".
> > 
> > /David
> > 
> > -----Original Message-----
> > From: boost-bounces_at_[hidden]
> > [mailto:boost-bounces_at_[hidden]] On Behalf Of 
> > spamjunk_at_[hidden]
> > Sent: Tuesday, August 27, 2002 8:47 AM
> > To: boost_at_[hidden]
> > Subject: RE: [boost] discrete_set class
> > 
> > 
> > Ok, this is my fault.  As Joel has pointed out, I neglected to 
> > provide
> 
> > documentation.  I apologize and will upload some as soon as I can.
> > For now, the problem with your examples is the class expects the 
> > values of the elements to be in the range [LO, HI].  You are trying
to
> 
> > use values outside the range.  My understanding of C++ is that it is
> > undefined behavior to convert an int to an enum when it is outside
the
> 
> > enum's range.
> > 
> > pop-server.stny.rr.com
> > 
> > _______________________________________________
> > Unsubscribe & other changes:
> > http://lists.boost.org/mailman/listinfo.cgi/boost
> > 
> > _______________________________________________
> > Unsubscribe & other changes:
> > http://lists.boost.org/mailman/listinfo.cgi/boost
> 
> pop-server.stny.rr.com
> 
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
> 
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost

pop-server.stny.rr.com

_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost