home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
HomeWare 14
/
HOMEWARE14.bin
/
prog
/
proxy14.arj
/
H4.HLP
< prev
next >
Wrap
Text File
|
1992-12-05
|
4KB
|
124 lines
SETS
{ e1, e2, ..., en} set enumeration
{ e1 .. ek} set of integers from e1 to ek
{} empty set
{ e : x <- s } set comprehension
{ e : x <- s ; b } set comprehension with boolean
{ e : x <- s1 , y <- s2 } s1, s2 are sets
{ e : x <- s1 , y <- s2 ; b } b is a boolean
e in s set membership
e notin s set nonmembership
s1 inter s2 set intersection
s1 U s2 set union
s1 diff s2 set difference
s1 subset s2 subset
union s distributed union
card s cardinality of a set
s1 == s2 set equality
the s element of singleton set
oneof s arbitrary member of set
(all x in s ; b ) universal quantifier
(exists x in s ; b ) existential quantifier
A mathematical set is, of course, an unordered collection of elements.
From a formal point of view, each element should have the same type.
However, since Proxy has latent types, i.e. types are not declared by
the programmer, set elements are not restricted to have the same type.
The simplest operation is to enumerate a set by delimiting its elements
by curly brackets:
{1,2,3,4,5}
This same set can be constructed by using the range notation
(not to be confused with the range of a map to be defined later)
{1..5}
Ranges can only be used when the elements are consecutive. Another
example of enumeration would be
smallprimes = {2,3,5,7};
To find the number of elements in the set smallprimes, we use the
cardinality operator card:
card smallprimes; returns 4
Two sets can be tested for equality using the equality operator ==.
Another simple operation is membership:
3 in smallprimes; returns true
3 notin smallprimes: returns false
To illustrate the standard operations of union, intersection, difference
subset and equality, we assume two sets s1 and s2 to have the values
s1={1,2,4,6};
s2={1,2,3,4,5};
s1 U s2; returns {1,2,3,4,5,6}
s1 inter s2; returns {1,2,4}
s1 diff s2; returns {6}
s1 subset s2; returns false
s1 == s2; returns false
The distributed union is the union of a set of sets. For example,
union {s1,s2,{6,7,8}}; returns {1,2,3,4,5,6,7,8}
The 'the' operator returns the only element of a singleton set. If
the argument is not a singleton set, an error message is returned.
the {13}; returns 13
The oneof operator applied to a set returns an 'arbitrary' element
of the set. However, Proxy always returns the 'first' element.
oneof smallprimes; returns 2
The existential quantifier applied to a set and a predicate returns
true if there is at least one element of the set that satisfies the
predicate, and false otherwise. The universal quantitifer applied
to a set and a predicate returns true only if all elements of the set
satify the predicate.
(exists x in {2,3,5,7};even(x)); returns true
(all x in {2,3,5,7};even(x)); returns false
where the function even(x) returns true if x is even. The existential
quantifier above returns true because 2 satisfies even(2) and the
universal quantifier returns false because only even(2) is satisfied.
A more general way of constructing sets is given by the form:
{ f(x): x<- expr ; pred(x) }
where the syntax x<- expr is called a generator, and the syntax
; pred(x) is optional. The expression expr is evaluated to
yield a set. The values of the set are successively assigned to x
and a new set is formed from elements obtained by applying the function
f to the successive values of x which satisfy pred(x) (if pred(x) occurs).
Several examples will make this clearer.
{ x: x<- {1,2,3,4,5}}; returns {1,2,3,4,5}
This is the simplest case where f(x) is just x and a predicate does
not appear.
{ x: x <- {1,2,3,4,5};x>2}; returns {3,4,5}
{ x*x: x <- {1,2,3,4,5}}; returns {1,4,9,16,25}
It is possible to have two generators in which case an example is:
{ x+y: x <- {1,2}, y <- {3,4}} returns {4,5,6}
Only three elements are returned because two additions (1+4) and (2+3)
yield duplicate values.