home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / interpre / proxy / h4.hlp < prev    next >
Encoding:
Text File  |  1992-12-05  |  4.4 KB  |  124 lines
  1.                               SETS
  2.  
  3. { e1, e2, ..., en}             set enumeration
  4. { e1 .. ek}                    set of integers from e1 to ek
  5. {}                             empty set
  6. { e : x <- s }                 set comprehension
  7. { e : x <- s ; b }             set comprehension with boolean
  8. { e : x <- s1 , y <- s2 }         s1, s2 are sets
  9. { e : x <- s1 , y <- s2 ; b }     b is a boolean
  10. e in s                         set membership
  11. e notin s                      set nonmembership
  12. s1 inter s2                    set intersection
  13. s1 U s2                        set union
  14. s1 diff s2                     set difference
  15. s1 subset s2                   subset
  16. union s                        distributed union
  17. card s                         cardinality of a set
  18. s1 == s2                       set equality
  19. the s                          element of singleton set
  20. oneof s                        arbitrary member of set
  21. (all x in s ; b )              universal quantifier
  22. (exists x in s ; b )           existential quantifier
  23.  
  24. A mathematical set is, of course, an unordered collection of elements.
  25. From a formal point of view, each element should have the same type.
  26. However, since Proxy has latent types, i.e. types are not declared by
  27. the programmer, set elements are not restricted to have the same type.
  28.  
  29. The simplest operation is to enumerate a set by delimiting its elements
  30. by curly brackets:
  31.  
  32. {1,2,3,4,5}
  33.  
  34. This same set can be constructed by using the range notation
  35. (not to be confused with the range of a map to be defined later)
  36.  
  37. {1..5}
  38.  
  39. Ranges can only be used when the elements are consecutive. Another
  40. example of enumeration would be
  41.  
  42. smallprimes = {2,3,5,7};
  43.  
  44. To find the number of elements in the set smallprimes, we use the
  45. cardinality operator card:
  46.  
  47. card smallprimes;      returns 4
  48.  
  49. Two sets can be tested for equality using the equality operator ==.
  50.  
  51. Another simple operation is membership:
  52.  
  53. 3 in smallprimes;      returns true
  54.  
  55. 3 notin smallprimes:   returns false
  56.  
  57. To illustrate the standard operations of union, intersection, difference
  58. subset and equality, we assume two sets s1 and s2 to have the values
  59.  
  60. s1={1,2,4,6};
  61.  
  62. s2={1,2,3,4,5};
  63.  
  64. s1 U s2;               returns {1,2,3,4,5,6}
  65. s1 inter s2;           returns {1,2,4}
  66. s1 diff s2;            returns {6}
  67. s1 subset s2;          returns false
  68. s1 == s2;              returns false
  69.  
  70. The distributed union is the union of a set of sets. For example,
  71.  
  72. union {s1,s2,{6,7,8}};       returns {1,2,3,4,5,6,7,8}
  73.  
  74. The 'the' operator returns the only element of a singleton set. If
  75. the argument is not a singleton set, an error message is returned.
  76.  
  77. the {13};              returns 13
  78.  
  79. The oneof operator applied to a set returns an 'arbitrary' element
  80. of the set. However, Proxy always returns the 'first' element.
  81.  
  82. oneof smallprimes;    returns 2
  83.  
  84. The existential quantifier applied to a set and a predicate returns
  85. true if there is at least one element of the set that satisfies the
  86. predicate, and false otherwise. The universal quantitifer applied
  87. to a set and a predicate returns true only if all elements of the set
  88. satify the predicate.
  89.  
  90. (exists x in {2,3,5,7};even(x));  returns true
  91.  
  92. (all x in {2,3,5,7};even(x));     returns false
  93.  
  94. where the function even(x) returns true if x is even. The existential
  95. quantifier above returns true because 2 satisfies even(2) and the
  96. universal quantifier returns false because only even(2) is satisfied.
  97.  
  98. A more general way of constructing sets is given by the form:
  99.  
  100. { f(x): x<- expr ; pred(x) }
  101.  
  102. where the syntax x<- expr is called a generator, and the syntax
  103. ; pred(x) is optional. The expression expr is evaluated to
  104. yield a set. The values of the set are successively assigned to x
  105. and a new set is formed from elements obtained by applying the function
  106. f to the successive values of x which satisfy pred(x) (if pred(x) occurs).
  107. Several examples will make this clearer.
  108.  
  109. { x: x<- {1,2,3,4,5}};           returns {1,2,3,4,5}
  110.  
  111. This is the simplest case where f(x) is just x and a predicate does
  112. not appear.
  113.  
  114. { x: x <- {1,2,3,4,5};x>2};      returns {3,4,5}
  115.  
  116. { x*x: x <- {1,2,3,4,5}};        returns {1,4,9,16,25}
  117.  
  118. It is possible to have two generators in which case an example is:
  119.  
  120. { x+y: x <- {1,2}, y <- {3,4}}   returns  {4,5,6}
  121.  
  122. Only three elements are returned because two additions (1+4) and (2+3)
  123. yield duplicate values.
  124.