This implementation of countably infinite sets is purely algebraic in approach. It is also based on a number of other ideas which dont get a high profile: lambda and types. I tend to use types for some things instead of namespaces. The idea behind types is that they are all known at a global level. They can be implemented using the space character rather than the colon. They also fit together with lambda and currying.
To implement countably infinite sets I need to have a lambda
package provide lambda
I also need to provide my own version of finite set procedures because there is a bit of interplay between the two so here are some procs of type listset. The arguments for these are all ordinary Tcl lists.
package provide listset 0.2
proc listset {cmd args} {
if { [info proc "listset $cmd" ] == {} } {
global errorInfo
error "No proc: listset $cmd" $errorInfo
return
}
uplevel 1 [linsert $args 0 "listset $cmd" ]
}
# listdiff returns a list of 3 sorted lists of unique elements
# { {stuff in a not in b } {stuff in both a and b } {stuff in b not in a } }
# the lists a and b are treated as sets
proc "listset diff" { a b } {
set a [ lsort -unique $a ]
set b [ lsort -unique $b ]
set l1 {} ; set l2 {}
foreach i $a {
set j [ lsearch $b $i ]
if { $j < 0 } {
lappend l1 $i
} else {
lappend l2 $i
set b [ lreplace $b $j $j ]
}
}
return [ list $l1 $l2 $b ]
}
proc "listset or" args { return [ lsort -unique [ eval concat $args ] ] }
proc "listset and" args {
if { [ llength $args ] == 0 } { return {} }
if { [ llength $args ] == 1 } { return [lindex $args 0]}
set a [ lindex [ "listset diff" [lindex $args 0] [lindex $args 1] ] 1]
return [ eval "listset and" [lreplace $args 0 1 $a ]]
}
proc "listset xor" args {
if { [ llength $args ] == 0 } { return {} }
if { [ llength $args ] == 1 } { return [lindex $args 0] }
set a [eval {"listset or"} $args]
set b {}
for {set i 0} {$i < [llength $args]} {incr i} {
for {set j [expr $i+1]} {$j < [llength $args]} {incr j} {
set c ["listset and" [lindex $args $i] [lindex $args $j]]
set b ["listset or" $b $c ]
}}
return [lindex ["listset diff" $a $b] 0 ]
}This is a basic algebraic solution where all the arguments can be ordinary Tcl lists.
The odd man out in this collection is "listset and". The above version is fine if you only ever work with finite lists, but there is a better version that works with finite or countably infinite sets whoch replaces the one above.
Now for the countably infinite set version which is just called "set". To make countably infinite sets as values in Tcl I use lambdas. This means that every countably infinite set is held as a lambda value. To help things along I provide a couple of constructs as well as allowing lambda expressions themselves. These constructs provide lambdas that are well-behaved. Allowing any old lmbda expression into the mix is not very cool but probably unavoidable. No different to expr a I guess.
if 0 { this is a package which provides algebra for infinte as well as finite sets
all functions and values are typed. They are in the form {type func} or {type value}
because most of the functions (procs in this package return sets most of the proc names are of the form {set func}
this package provides type conversion from list, listset, regexp and lambda to set
a list type is the normal form of finite list
a listset type is the normal form of finite list with the restriction that no values are repeated, however this is never assumed
a lambda type is a lambda expression, however, depending on the value supplied to the lambda expression it may evaluate to 0, 1 or some other value or generate an error. Values other than 0 or 1 are trapped if they occur and 0 returned instead.
the fundamental property of a set is that you can tell if a candidate value is an element of the set or not. That is the basic functionality which this package provides.
Because the sets managed by this package are infinite by default it is not possible to enumerate the elements in any set. However a {listset and} procedure is provided which allows for the intersection of a set with a listset (or list) and returns the finite list representation of the intersection of the two.
proc {set make} value - returns a value of type set
Sample Invocations
{set make} $a - where the variable a has a typed valued as in the next examples
{set make} {list { a s d f g}}
{set make} [list regexp $regexp_pattern]
{set make} {regexp x.*}
{set make} {lambda i {expr{$i%6}==0}}
{set and} ?set1? ?set2? ... - returns the set which represnts the intersection of the sets
Sample Invocations
{set and} $a $b $c - where the variables a b and c are of type set - of not an error is signalled
{set and} {lambda i {expr{$i%6}==0} {lambda i {expr{$i%10}==0}
Example of use:
% set a [{set make} {lambda i {expr {($i%6)==0}}}]
% set b [{set make} {lambda i {expr {($i%10)==0}}}]
% set c [{set and} $a $b]
% $c 2580
1
% $c 31
0
% $c 3.2
can't use floating-point value as operand of "%"
Thats what comes of allowing wild lambdas!
}
proc {set make} a {
set ob \[
set cb \]
set d \$
set oc \{
set cc \}
switch [lindex $a 0] {
"list" -
"listset" { # convert list to listset
# check that a has exactly 2 elements in its list
if { [llength $a] != 2 } {
bgerror "value of arg a = \"$a\" is not of proper list type"
return {}
}
set b [lsort -unique [lindex $a 1]]
return "lambda i ${oc}expr $oc ${ob}lsearch ${ob}list $b $cb ${d}i $cb >= 0 $cc$cc "
}
"regexp" {
# check that a has exactly 2 elements in its list
if { [llength $a] != 2 } {
bgerror "value of arg a = \"$a\" is not of proper regexp type"
return {}
}
# check that the pattern is a valid regexp
set pattern [lindex $a 1]
if { [catch { regsub $pattern x {} } msg ] } {
set c errorInfo
bgerror "\"$pattern\" is not a valid regexp pattern \n $c"
return {}
}
return "lambda i $oc expr $oc $ob regsub $pattern ${d}i {} $cb == {} $cc $cc "
}
"lambda" {
# check that a has exactly 3 elements in its list
if { [llength $a] != 3 } {
bgerror "value of arg a = \"$a\" is not of proper lambda type"
return {}
}
# MAYBE LATER check that 2nd element is proper simple (not array or arrya element) tcl variable name
return $a
}
default { bgerror "\"[lindex $a 0]\" is an unrecognised type and cannot be made into a set."
return {}
}
}
}
if 0 {
# test data
set a [{set make} {list { 3 4 5 6 33 44 55 66}}]
set b [{set make} {regexp 6*}]
set c [{set make} {lambda i {expr {[string length $i] %2 == 0}}}]
}
Here are the "set" procedures. I used a small "s" and have left out the curry routine.
I HAVE GOT SOME MORE TO FINISH ON THIS TOMORROW