Purpose: Definition of set functionality for an official extension.
This is a part of the Chart of proposed list functionality.
See also A set of Set operations.
See also Tcllib's module struct, package struct::set
Sometimes intersection and both onesided differences are required. A procedure computing them in parallel should be more efficient than doing it separately.
[AK] (Mar 20, 1999): The timing of the possible implementations proved me wrong, this procedure is not necessary.
Implementation:
General features:
Functions:
Code:
Testcases:
Discussion area.
LV: Are there other list oriented languages from whom we can 'borrow' set functionality ? Perl's idea of adopting concepts found in other languages, done in the spirit of perl, is one that could really work in Tcl as well. Mar 20, 1999
Edrx: Icon has a built-in "set" type, with at least these built-in operators and functions (see [L2 ] and [L3 ]):
S1 ++ S2 set union; returns a set S1 ** S2 set intersection S1 -- S2 set difference *S1 the number of elements in S1 ?S returns a random element from S set(L) makes a set from a list member(S,x) fails if x is not a member of S, else returns x insert(S,x,...) insert x,... in S; return the new set delete(S,x,...) delete x,... from S; return the new set
There's also "!S", that "generates" each element of S, in no predictable order, but the concept of "generators" is too Icon-specific. If it's a matter of borrowing syntax, I would suggest using something like S++, ..., Smember... or like Set::++, ... . Nov 19, 1999
DKF: Membership test should be a boolean operator, and not something with a failure semantics (given correctly typed input.)
escargo 11/11/2002: Failure is not a bad thing in Icon. Icon has no boolean type! Expressions either success and return a value or fail. This is key to making backtracking work. It is not failure in the same sense as other languages might throw an exception. Languages that do not implement backtracking need failure less, but for Icon it is very much central.
AK: The contains command as defined above returns a boolean. Wrappers could be provided to make porting Icon apps easier.
DKF: Hmm. Reading comprehension is obviously not my strong point!
-- AK
http://web.uvic.ca/~erempel/tcl/sets/sets.html is another Tcl extension that provides set operations.
Obviously, a lot more has been done about set operations than I thought. But there will probably one subject left: infinite sets. I wrote a fairly lengthy page on finite sets and countably infinite sets (that part still has to be finished). Look for the page: Manipulating sets in Tcl. Arjen Markus
Category suggestions Category Command Category Data Structure