archive/share/unknown/sets.dmo

   1 /*-*-macsyma-*-*/
   2
   3 SETUP_AUTOLOAD(SETS,MAKE_UNIVERSE)$
   4
   5 KILL(LABELS)$
   6
   7 /* Get a fresh UNIVERSE */
   8
   9 UNIVERSE:MAKE_UNIVERSE();
  10
  11 X:{1,2,3,4,5,6,7};
  12 Y:{2,3,4,10,20};
  13
  14 UNION(X,Y);
  15
  16 INTERSECTION(X,Y);
  17
  18 SETDIFF(Y,X);
  19
  20 /* to get the elements of the universe */
  21 SETDIFF();
  22
  23 /* to get the complement */
  24
  25 SETDIFF(X);
  26
  27 IZ:{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}$
  28
  29 /* A standard set thing to do, the set of all elements of
  30    a set such that a predicate is true. */
  31
  32 PREDSET(LAMBDA([ELEM],IS(ABS(ELEM-12)<4)),IZ);
  33
  34 ELEMENTP(3,IZ);
  35
  36 Z:{2,3,4};
  37
  38 SUBSETP(X,Y);
  39
  40 SUBSETP(Z,X);
  41
  42 /* representation conversion */
  43
  44 ELEMENTS(X);
  45
  46 MAPSET(LAMBDA([ELEM],ELEM^2),{1,2,3});
  47
  48 CARDINAL({A,B,C,D});
  49
  50 /* To each expression ever interned in a set there is a associated
  51    Goedel number. (On a per-universe basis) */
  52
  53 ORDINAL('A);
  54
  55 ORDINAL('FOOBAR);
  56
  57 /*
  58   Sets are represented as BOOLEAN arrays, (bit-vectors to the machine),
  59   with element indices given by the Goedel number. Pure-set operations
  60   only work on the bit-vectors, and are very fast.
  61 */
  62
  63 /* An example, implementing POWERSET. This is not a useful example,
  64    how many elements does the powerset of
  65   {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,0,1,2,3,4,5,6,7,8,9}
  66   contain? More than can fit on any system around. */
  67
  68
  69 ADJOIN(X,S) ::= BUILDQ([X,S], UNION({X},S) )$
  70
  71 POWERSET(S):=
  72  IF EMPTYP(S) THEN {{}}
  73  ELSE BLOCK([AN_ELEMENT:ELEMENTOF(S), POWER_REST],
  74             POWER_REST:POWERSET(SETDIFF(S,{AN_ELEMENT})),
  75             UNION(POWER_REST,
  76                   MAPSET(LAMBDA([X],ADJOIN(AN_ELEMENT,X)),
  77                          POWER_REST)))$
  78
  79
  80 POWERSET({});
  81 POWERSET({A,B,C});
  82
  83 /* TRANSLATE before we try this on a big set. */
  84 (TRANSLATE(POWERSET), /* twice for good recursion */ TRANSLATE(POWERSET))$
  85 X8:{1,2,3,4,5,6,7,8};
  86
  87 POWERSET(X8);