RE: [boost] discrete_set class

From: spamjunk_at_[hidden]
Date: 2002-08-27 14:39:42

I'm sorry.  Friends tell me my correspondence always sounds defensive, though I
rarely take offense and I welcome constructive criticism.  I'm just trying to
get a handle on what you are saying.  You obviously have a better background in
this area than I.  I took mostly Calculus in college, with some courses in such
things as Discrete Logic and First Order Predicate Calculus.

Actually, my set is stored internally the same way Pascal's set is usually
stored (for better or worse).

I get the impression that you think the class requires a "small" set of
elements, such as maybe the number of bits in a machine word (if I'm wrong, skip
over my blather).  This is not the case.  You are only limited by memory and the
limits of the int type (2^31 - 1 elements possible on a 32-bit machine).

I also get the impression that you think adding iterators to the class (a
project for later) would be ill-advised.  I would love to hear you thoughts on this.

Thanks,

Rich Herrick

> 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
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

pop-server.stny.rr.com